What are the states of this NFA?

Question

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.

Answer 1

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.

Answer 2

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?.]