What's the language of the NFA? Given is the NFA N:



What's the language of this NFA? What's its complement?



I'm learning for a test and I'd like to know if I solved this task correctly.

The language L of the NFA N should look like this:

L(N) = {x ∈ Σ* | x mustn't include 'aba' and x mustn't end with 'ab'}


I have tried several different words and I couldn't find any word that breaks my language L(N).

Assuming this is correct, how would the complement of L(N) look like?

It needs to be the opposite, right? So something like that (~ stands for complement):

~L(N) = {x ∈ Σ* | x must include 'aba' and x must end with 'ab'}
I tried expanding my comment to a proper answer. It was easier for me to write down the automata and the whole transformation process rather than using some software to generate it, thus I hope my handwriting is legible enough ;) (elsewise let me know)



The resulting Regular Expression is $[[b^*ba^*b]^*\cup[b^*aa^*ab^*b]^*]^*$

So the language accepted by your NFA ought to be something of the form $L = \{((b^lba^hb)^*(b^iba^jab^kb)^*)^*|i,j,k,l,h\ge 0\}^*$ (I've given a quasi-final form of the language).

The opposite of this language is $\sim L = \mathtt{REG} - L$

PS: Fortunately, a kind sir named Hendrik Jan observed that my conversion omits the fact that 2 is also a starting point. The solution is still holds for starting point 1. Now that you got an idea about NFA to REG conversions, I'll leave the REG determined by starting point 2 to you. :)