1
$\begingroup$

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:

the process, step-by-step

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

$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$ May 10, 2022 at 14:43
  • 2
    $\begingroup$ @user253751 3 states is the number of states necessary for the regular expression $ab$, not the final one. $\endgroup$
    – Nathaniel
    May 10, 2022 at 14:49
  • $\begingroup$ What's the context? Is the point not just to prove that an NFA for it exists? $\endgroup$ May 10, 2022 at 17:11
  • $\begingroup$ @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. $\endgroup$
    – csmathhc
    May 11, 2022 at 2:16

2 Answers 2

2
$\begingroup$

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.

Note that as stated by Sipser, the method is not optimal, but it is easy to apply.

$\endgroup$
1
$\begingroup$

The procedure described in the text is a systematic method for converting a regular expression to an NFA. It’s a recipe that works, and so you don’t have to think much to prove that the language of every regular expression is accepted by some DFA. However, the machine obtained in this manner would generally not have the minimal number of states.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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