Given is the NFA N:

enter image description here

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'}
  • 2
    $\begingroup$ You didn't use De Morgan's law correctly. $\endgroup$
    – Raphael
    Nov 2, 2017 at 20:40
  • $\begingroup$ @Raphael Oh, then I need to replace the "and" with an "or" in ~L(N) ? $\endgroup$
    – cnmesr
    Nov 2, 2017 at 20:41
  • $\begingroup$ Try transforming it to a regular expression. This should give you immediately the language of the NFA. $\endgroup$ Nov 2, 2017 at 21:00
  • 1
    $\begingroup$ @cnmesr ~(a&b) == ~a | ~b and ~(a|b) == ~a & ~b $\endgroup$ Nov 2, 2017 at 21:37
  • $\begingroup$ Yes, your $L(N)$ is correct. It is somewhat easier to see what happens if you transform the automaton in an equivalent deterministic one. $\endgroup$ Nov 3, 2017 at 0:06

1 Answer 1


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. :)

  • $\begingroup$ Thank you very much for writing all that on an extra sheet of paper and posting it here! :) We just had regular expression in our reading today and this will help me a lot when I go through it (tomorrow because I need to sleep now). Maybe you can quickly tell me if my L(N) is correct, too? $\endgroup$
    – cnmesr
    Nov 2, 2017 at 21:40
  • 1
    $\begingroup$ Note the original automaton is very undeterministic in that it has two initial states. $\endgroup$ Nov 3, 2017 at 0:07
  • $\begingroup$ Also, I do not sponsor the notation $\{\dots (a^lba^hb)^* \dots \mid j,h\ge 0\}$ for two reasons. (1) the regular expression is within set brackets. By itself the star-thing is already a set/language. (2) If you fix $l,h$ and then perform the star operation (as the notation suggests) you cannot repeatedly choose different values for $l,h$ when iterating. $\endgroup$ Nov 3, 2017 at 0:12
  • 1
    $\begingroup$ eurmph. Also, the loop on node 1 is a $b$ in the original. Sorry, but it was not my intention to sound grumpy. $\endgroup$ Nov 3, 2017 at 0:17
  • $\begingroup$ @HendrikJan No problem. In fact, thank you for pointing out my missinterpretations. I have taken into account only the initial state 1. $\endgroup$ Nov 3, 2017 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.