Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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?.]

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.