# NFA to recognize the language ${ab}$

In Michael Sipser's Introduction to the Theory of Computation, Example 1.56 shows how to convert $$\left(\text{ab }\cup\text{ a}\right)^*$$ to an NFA. It builds up from the smallest subexpression to larger subexpressions until the required NFA is obtained:

My question is: why is the NFA to recognize $$\text{ab}$$ not a simple 3 state DFA?

• Because this is a very simple and "dumb" method which does not even try to create a simple NFA. If you simplify this NFA, then you will get the simple DFA you are looking for. (is it 3 states? I think only 2 states are needed) May 10, 2022 at 14:43
• @user253751 3 states is the number of states necessary for the regular expression $ab$, not the final one. May 10, 2022 at 14:49
• What's the context? Is the point not just to prove that an NFA for it exists? May 10, 2022 at 17:11
• @KellyBundy That an NFA exists for every regular expression was proved in the book earlier. This example was trying to show how a regular expression can be converted into an NFA. May 11, 2022 at 2:16

It is because of the method used for the construction. The NFA that results from the concatenation of the languages of two automata $$A_1$$ and $$A_2$$ is the juxtaposition of $$A_1$$ and $$A_2$$ with $$\varepsilon$$-transitions from the final states of $$A_1$$ to the initial state of $$A_2$$.
Given the automata for the regular expressions $$a$$ and $$b$$, we obtain an automaton for $$ab$$ with 4 states with this method.