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 '17 at 20:40
  • $\begingroup$ @Raphael Oh, then I need to replace the "and" with an "or" in ~L(N) ? $\endgroup$
    – cnmesr
    Nov 2 '17 at 20:41
  • $\begingroup$ Try transforming it to a regular expression. This should give you immediately the language of the NFA. $\endgroup$ Nov 2 '17 at 21:00
  • 1
    $\begingroup$ @cnmesr ~(a&b) == ~a | ~b and ~(a|b) == ~a & ~b $\endgroup$ Nov 2 '17 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 '17 at 0:06

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 '17 at 21:40
  • 1
    $\begingroup$ Note the original automaton is very undeterministic in that it has two initial states. $\endgroup$ Nov 3 '17 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 '17 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 '17 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 '17 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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