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