Finite Automata Input Confusion

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?

• What are the respective inputs?
– Raphael
Jan 17 '14 at 18:25
• The input is the string 'abba' 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.
• Exactly. The only state having an outgoing edge annotated $a$ is $q_0$. Jan 18 '14 at 2:20