I am trying to figure out which language does the following NFA (taken from a Sipser's book "Introduction to theory of computation") recognise

enter image description here

From my understanding, this NFA accepts strings that contain at least two $1$s, but this is not precise, because, e.g., between the two ones we could have a $0$ or nothing ($\epsilon$). We can also have any number of $0$s or $1$s after these two $1$s.

My guess is that this NFA recognises a language whose strings contain the substrings $11$ or $101$, but I am not sure.

Can you help me defining the language that this NFA recognises?

In general, what is the best way to see what language is recognised by a NFA?

  • 4
    $\begingroup$ If you're not sure about your guess, try to prove it. If you fail, you can probably come up with a counterexample refuting your conjecture. $\endgroup$ – Yuval Filmus Nov 8 '15 at 15:23
  • 3
    $\begingroup$ To prove that an NFA accepts a language $L$, you typically do two things. First, you show that the NFA accepts each word $w \in L$ by presenting an accepting computation. Second, you show that every word accepted by the NFA is in $L$. Typically you state which words end up in which state, and prove that it is indeed so by induction. $\endgroup$ – Yuval Filmus Nov 8 '15 at 15:56
  • $\begingroup$ @YuvalFilmus So, in other words, I need to show that the language recognised by a certain NFA $N$, i.e. L(N), is equal to $L$, by using a typical proof that shows that two sets are equal? $\endgroup$ – nbro Nov 8 '15 at 16:04
  • 1
    $\begingroup$ You can use whichever proof pattern you wish. $\endgroup$ – Yuval Filmus Nov 8 '15 at 16:09
  • $\begingroup$ Proving this by induction is not a trivial task especially if you are having doubts with a fairly simple NFA. $\endgroup$ – Renato Sanhueza Nov 9 '15 at 3:56

Don't overthink it; your intuition is correct. The only strings that get you from the start state to the final state are $<anything>11$ or $<anything>101$. Once you're in the final state, any subsequent inputs are also accepted, so the language accepted by this FA is, as a regular expression, $(0+1)^*(11+101)(0+1)^*$, which is obviously all strings containing 11 or 101.

| cite | improve this answer | |

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.