1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You will get stuck at q_3 with "bab" or "ba"... $\endgroup$ – Juho Aug 27 '15 at 4:34
  • 1
    $\begingroup$ What do you think? This is not a "check my homework" site. $\endgroup$ – Raphael Aug 27 '15 at 12:49
  • $\begingroup$ @raphael it's not a homework problem though, its page 52 from Sipser second ed. It's an example. $\endgroup$ – Elliot Gorokhovsky Aug 27 '15 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 '15 at 15:12
4
$\begingroup$

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.

$\endgroup$

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.