0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented 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$
    – Yuval Filmus
    Commented Nov 8, 2015 at 15:56
  • 1
    $\begingroup$ You can use whichever proof pattern you wish. $\endgroup$
    – Yuval Filmus
    Commented 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$
    – Renato Sanhueza
    Commented Nov 9, 2015 at 3:56

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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