[Math] NFA for $(ab|a)^{*}$ using only 2 states

automataregular-language

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $ (ab|a)^{*}$ into an NFA. The "standard" method results in 8 states, and there's an additional challenge given to the reader to find the smallest NFA which has only 2 states.

Below is the diagram that I arrived at. It accepts $ a, aa, abab, aab, aaababaa $, etc. but fails when the string starts with $b$. How should I fix this?

NFA

Also, is there any general approach or guidelines to find such "smallest" NFA's and DFA's in the general case? (PS: I don't know if this is explained later in the book. Please ignore this additional question, if a textbook will usually explain it at a later stage.)

Best Answer

One needs at three states for a DFA, having the folowing semantics:

  1. Input is acceptable so far and $b$ may follow
  2. Input is acceptable so far and $b$ must not follow
  3. Input is not acceptable (so far)

More precisely, after input of $a$, $ab$, $abb$, the automaton must be in different states: The state after $abb$ must differ from the first two because it must not accept. The state after $a$ must differ from $ab$ because upon next input of $b$ the first is an acceptable string, the second is not.

For your NFA, just make $B$ the initial state.

Related Question