I am looking at the following non-deterministic finite automata which accepts all strings that end with at least 2 bs. I am wondering what would happen when you have the input string 'abba' with this automata:


The possible computations I have so far are

q0, q0, q0, q0, q0

q0, q0, q1, q2, ??

q0, q0, q0, q1, ??

Would anyone be able to fill in the '??'s in this automata and be able to explain why they occur?

  • $\begingroup$ What are the respective inputs? $\endgroup$
    – Raphael
    Jan 17, 2014 at 18:25
  • $\begingroup$ The input is the string 'abba' $\endgroup$ Jan 17, 2014 at 18:32

1 Answer 1


If you're at a state $q$ reading $\alpha$ and there is no outgoing edge labeled $\alpha$, then there is way to extend the computation path. In view of that, the only valid computation path upon reading $abba$ is $q_0,q_0,q_0,q_0,q_0$; in fact, the same is true for any word ending in $a$, whose computation paths are of the form $q_0,\ldots,q_0$. Words ending in $b$ have the additional computation path $q_0,\ldots,q_0,q_1$, and words ending in $bb$ have the additional computation path $q_0,\ldots,q_0,q_1,q_2$, making three in total.

  • $\begingroup$ So what you're saying is that for abba it is not possible to go beyond q0 because of the a at the end of the input string? $\endgroup$ Jan 18, 2014 at 0:45
  • $\begingroup$ Exactly. The only state having an outgoing edge annotated $a$ is $q_0$. $\endgroup$ Jan 18, 2014 at 2:20

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.