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$ Nov 8, 2015 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$ Nov 8, 2015 at 15:56
  • 1
    $\begingroup$ You can use whichever proof pattern you wish. $\endgroup$ Nov 8, 2015 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$ Nov 9, 2015 at 3:56

1 Answer 1


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.


Your Answer

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