2
$\begingroup$

I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want to focus on $a$).

But when he demonstrates how to convert the NFA to an equivalent DFA, he says: state $1$ goes to $\emptyset$ on $a$ because no $a$ arrows exit it. [...] Note that the procedure in Theorem 1.39 [on equivalence of DFAs and NFAs] specifies that we follow the $\epsilon$ arrows after each input is read.

So, if $\epsilon$-transitions happens only after some input (as the author defines), then in the initial state $1$, when $a$ is given, the NFA should 'die' as $\delta(1, a) = \emptyset$. The transition to state $3$ never happens, the NFA doesn't accept $a$. Doesn't the author contradicts himself?

I can think of couple possible explanations: 1) the very first transition of a NFA is $\delta(1, \epsilon)$ just by definition, 2) $a\epsilon=a$, so $\delta(1, a)$ = $\hat{\delta}(1, a\epsilon)$ = $\delta(1, \epsilon)\cup\delta(1, a)$, but then again the author said state $\{1\}$ goes to $\emptyset$ on $a$, not ${3}$

$\endgroup$
1
$\begingroup$

An NFA can always choose to take an $\varepsilon$-transition (if one exists) without reading any input, so your NFA would indeed accept the string $a$ by following the transitions $1 \xrightarrow{\varepsilon} 3 \xrightarrow{a} 1$ and ending up in an accepting state. This is because the NFA nondeterministically chose to follow the $\varepsilon$-transition before reading $a$ from the input.

However, when converting an NFA to a DFA we have to resolve the nondeterminism in some way. The procedure presented by Sipser in Theorem $1.39$ follows the convention that $\varepsilon$-transitions are followed after each input symbol is read, but, as he also states, a procedure based on following $\varepsilon$-transitions before each input symbol is read would work equally well. It is only a matter of the convention used to resolve the nondeterminism in the NFA.

If you look at Example $1.41$ and the DFA resulting from the conversion in Figure $1.43$, you will notice that the initial state is $\{1,3\}$ (the union of states $1$ and $3$ from the NFA) because the NFA have initial states $1$, but it can also go to $3$ with an $\varepsilon$-transition without reading any input. Therefore, the initial state in the DFA is the union of the two.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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