# What are the states of this NFA?

I have to realize an NFA that recognizes the language of strings on the alphabet {a, b} ending with: bb, ba, baa. I thought that there must be the following states:

$q_0$: the string ends with bb.

$q_1$: the string ends with ba.

$q_2$: the string ends with baa.

Is right the definition of the states? Or missing some state?

Thanks.

-

As you seem to understand, the states in a FA can be designed to correspond to having seen a particular form of input. One solution (not with the minimal number of states, but easier to understand) uses five states:

• $q_0$: Processes any input and takes special action if a $b$ is seen. (start state)
• $q_1$: Just saw input $\dots b$
• $q_2$: Just saw input $\dots ba$ (final state)
• $q_3$: just saw input $\dots bb$ (final state)
• $q_4$: Just saw input $\dots baa$ (final state)

Since we're looking for $ba, bb, baa$ at the end of the input, we'll have no moves from $q_3$ and $q_4$ and only an $a$ transition from $q_2$, to handle the possibility that the input ends after having seen $\dots baa$.

The transition table for this NFA is $$\begin{array}{ccc} & \mathbf{a} & \mathbf{b}\\ q_0 & \{q_0\} & \{q_0, q_1\}\\ q_1 & \{q_2\} & \{q_3\}\\ q_2 & \{q_4\} & \varnothing\\ q_3 & \varnothing & \varnothing\\ q_4 & \varnothing & \varnothing \end{array}$$

You might want to try designing a NFA for this language with four, rather than five states.

-
Thank you very much, this solution is very clear. You mentioned a version of the solution with four states. Could you talk about this solution, please? – Mark Feb 3 '13 at 10:36
You don't need state $q_4$. You could keep everything else the same but from $q_2$ on input $a$, go to $q_3$. In effect, you're doubling up $q_3$ to indicate that the input seen so far is either $\dots bb$ or $\dots baa$. – Rick Decker Feb 3 '13 at 18:16
In this situation (without the state q4), you can get in (q1, a) another state q3 with q2? – Mark Feb 4 '13 at 21:47
I don't understand your question. I'm suggesting that you keep the transition table I used above, but (1) eliminate $q_4$ and (2) make $\delta(q_2, a) = q_3$, instead of going to $q_4$. – Rick Decker Feb 5 '13 at 1:00
I'm sorry, I was unclear. if $q_2$: "just saw input ... ba" and $q_3$: "just saw input .. bb", then $\delta(q_2, a) = ... baa \neq q_3$. – Mark Feb 5 '13 at 10:08

You need at least a start state, which loops back on each character, An then you need states for, e.g., $q_2 \rightarrow q_2' \rightarrow q_2'' \rightarrow q_2'''$ ($q_2$ means "$baa$ still to go", $q_2'$ is "want $aa$", $q_2''$ means "need $a$", and $q_2'''$ is final). [Sorry, would put symbols over the arrows if I knew how. Perhaps some kind editor does?.]

-
I'm sorry, I did not understand. This is a very difficult issue for me. Anyway thanks for the answer. I wanted to ask you: $q_2, q_2 '$, $q_2 ''$, $q_2'''$ are the states? Why did you make this choice? – Mark Feb 2 '13 at 18:41