# What language should this NFA recognise?

I am trying to figure out which language does the following NFA (taken from a Sipser's book "Introduction to theory of computation") recognise 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?

• 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. – Yuval Filmus Nov 8 '15 at 15:23
• 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. – Yuval Filmus Nov 8 '15 at 15:56
• @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? – nbro Nov 8 '15 at 16:04
• You can use whichever proof pattern you wish. – Yuval Filmus Nov 8 '15 at 16:09
• Proving this by induction is not a trivial task especially if you are having doubts with a fairly simple NFA. – 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.