I am trying to verify that the NFA below does not accept babba. However, when I tried to do it by hand I must have made a mistake: $$\{q_1\}, \{q_2,q_3\}, \{q_1, q_2, q_3\}, \{q_2, q_3\}, \{q_3\}, \{q_1\} \rightarrow \text{Accept}$$ Where is my error?

enter image description here

  • $\begingroup$ You will get stuck at q_3 with "bab" or "ba"... $\endgroup$
    – Juho
    Aug 27, 2015 at 4:34
  • 1
    $\begingroup$ What do you think? This is not a "check my homework" site. $\endgroup$
    – Raphael
    Aug 27, 2015 at 12:49
  • $\begingroup$ @raphael it's not a homework problem though, its page 52 from Sipser second ed. It's an example. $\endgroup$ Aug 27, 2015 at 12:51
  • $\begingroup$ We discourage "please check whether my answer is correct" questions. See here and here. For the future, it is often better ask about a specific conceptual issue you're uncertain about. As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Aug 27, 2015 at 15:12

1 Answer 1


The error is that you don't distinguish when you read a letter from the input and when not. For instance, the first (closure of) state(s) is not $\{q_1\}$ but rather $\{q_1,q_3\}$ due to the epsilon move. Then, the first letter is $b$, thus $$\{q_1,q_3\} \to^{b} \{q_2\}$$ continue like this and you'll get the correct answer.


Your Answer

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

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