2
$\begingroup$

I'm reading Introduction to Computational Theory by Michael Sipser. He provides the NFA below as one that recognizes the language of the regular expression $ab$.

What is the purpose of the middle two states and the $\varepsilon$ transition between them? Could this NFA be designed without them and still work as intended?

 re

Here's another example of an NFA that recognizes the language described by $aba$. Again, I'm confused by the addition of the empty string transitions and the extra states. enter image description here

$\endgroup$

2 Answers 2

2
$\begingroup$

The example is part of the construction to obtain a finite automaton for each regular expression. This construction is known as Thompson's construction and works recursively. Given automata $A(e_1)$ and $A(e_2)$ for expressions $e_1$ and $e_2$, instructions are given to build new automata for the expressions $e_1 + e_2$, $e_1\cdot e_2$ and $e_1^*$. These new automata contain a lot of $\varepsilon$-edges to connect the original parts.

Hence the purpose of the example is not to give an efficient automaton (that is a no-brainer for $ab$) but to illustrate these constructions.

$\endgroup$
0
$\begingroup$

You are right in saying that those $\epsilon$-transition are useless. For the regular expression $ab$, a DFA with just three states (the initial state, an intermediate state, and a final state) and two transitions would suffice.

A similar reasoning applies to the second NFA, where $4$ states are enough.

I don't have the book to check, but maybe those are just examples of some of the many possible NFAs that accept the regular languages you mentioned?

$\endgroup$

Your Answer

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

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