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 '14 at 18:25
  • $\begingroup$ The input is the string 'abba' $\endgroup$ Jan 17 '14 at 18:32

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 '14 at 0:45
  • $\begingroup$ Exactly. The only state having an outgoing edge annotated $a$ is $q_0$. $\endgroup$ Jan 18 '14 at 2:20

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.