Nondeterministic Finite Automata and Subset Construction

For every $s\in S$, the length-zero $\epsilon$-chain from $s$ to itself shows $s\in \mathrm{ECl}(S)$ by [L1]. Hence $S\subseteq \mathrm{ECl}(S)$.

Assume $S\subseteq T$ and let $q\in \mathrm{ECl}(S)$. By [L1], some $\epsilon$-chain starts in a state of $S$ and ends at $q$; because that start state also lies in $T$, the same chain shows $q\in \mathrm{ECl}(T)$. Thus $\mathrm{ECl}(S)\subseteq \mathrm{ECl}(T)$.

Step 1.1 gives $\mathrm{ECl}(S)\subseteq \mathrm{ECl}(\mathrm{ECl}(S))$. For the reverse inclusion, let $q\in \mathrm{ECl}(\mathrm{ECl}(S))$. By [L1], there is an $\epsilon$-chain from some $r\in \mathrm{ECl}(S)$ to $q$, and again by [L1] there is an $\epsilon$-chain from some $s\in S$ to $r$. Concatenating the two finite chains gives an $\epsilon$-chain from $s$ to $q$, so $q\in \mathrm{ECl}(S)$. Therefore $\mathrm{ECl}(\mathrm{ECl}(S))=\mathrm{ECl}(S)$.

Define an NFA $N=(Q,\mathrm{\Sigma },\eta ,q_0,F)$ by $\eta (q,a):=\{\delta (q,a)\}$ for $a\in \mathrm{\Sigma }$ and $\eta (q,\epsilon ):=\mathrm{\varnothing }$ for every state $q$. Step [L1] makes this well-defined, and $N$ has the same states, start state, and accepting states as $D$.

We claim that for every state $q$ and every word $w$, the NFA reachable set from $q$ on $w$ is the singleton containing the DFA state reached from $q$ on $w$. This is proved by induction on $\mathrm{\mid }w\mathrm{\mid }$: for $\epsilon$ there are no $\epsilon$-moves, so the reachable set is $\{q\}$; for $wa$, the NFA applies the same one-letter transition as the DFA and then again has no $\epsilon$-moves.

By step 2.1 and [L2], a word $w$ reaches an accepting DFA state exactly when the NFA reachable set on $w$ contains an accepting state. By [L3], this is exactly the NFA acceptance condition, so $L(N)=L(D)$.

For the empty word, ${\mu }^{\ast }(S_0,\epsilon )=S_0$ by the DFA recursion, while [L1] and [L2] identify both sides with $\mathrm{ECl}(q_0)$.

Fix a successor word of the form $wa$.

Assume ${\mu }^{\ast }(S_0,w)=\widehat{\delta }(q_0,w)$. Then for the successor word from step 1.2 the DFA recursion gives ${\mu }^{\ast }(S_0,wa)=\mu ({\mu }^{\ast }(S_0,w),a)$, so [L1] turns this into $\mathrm{ECl}({\bigcup }_{q\in {\mu }^{\ast }(S_0,w)}\delta (q,a))$.

Substituting the induction hypothesis into step 2.1 yields ${\mu }^{\ast }(S_0,wa)=\mathrm{ECl}({\bigcup }_{q\in \widehat{\delta }(q_0,w)}\delta (q,a))$, and [L2] identifies that set with $\widehat{\delta }(q_0,wa)$.

Steps 1.1, 1.2, 2.1, and 3.1 prove by induction on $\mathrm{\mid }w\mathrm{\mid }$ that ${\mu }^{\ast }(S_0,w)=\widehat{\delta }(q_0,w)$ for every word $w$.

Induct on the word length to show ${\mu }^{\ast }(E(\{q_0\}),w)=\widehat{\delta }(q_0,w)$. For the empty word, both sides equal $E(\{q_0\})$. If the equality holds for $w$, the DFA recursion and [L1] give the value at $wa$ as $E({\bigcup }_{q\in \widehat{\delta }(q_0,w)}\delta (q,a))$, which is exactly $\widehat{\delta }(q_0,wa)$ by the finite-run recursion. This proves the identity for every word.

In the subset construction, a DFA state is accepting exactly when it contains an accepting NFA state. Therefore [L2] and step 1.1 show that $D_N$ accepts $w$ exactly when $\widehat{\delta }(q_0,w)$ contains an accepting state.

By [L3], the condition from step 2.1 is exactly the statement that $N$ accepts $w$. Thus $D_N$ accepts precisely the words that $N$ accepts, so $L(D_N)=L(N)$.

If $L$ is regular, then [L1] gives a DFA recognizing $L$, and [L2] turns that DFA into an epsilon-NFA recognizing the same language under [L4].

If some NFA recognizes $L$, interpret it with [L4]. Then [L3] gives a total DFA recognizing the same language, and [L1] therefore shows that $L$ is regular.

Steps 1.1 and 1.2 prove that $L$ is recognized by an NFA if and only if $L$ is regular.

Define an epsilon-free NFA $N^{\mathrm{\prime }}=(Q,\mathrm{\Sigma },{\delta }^{\mathrm{\prime }},q_0,F^{\mathrm{\prime }})$ by ${\delta }^{\mathrm{\prime }}(q,a):={\bigcup }_{r\in \mathrm{ECl}(q)}\mathrm{ECl}(\delta (r,a))$ for $q\in Q$ and $a\in \mathrm{\Sigma }$, and by $F^{\mathrm{\prime }}:=\{q\in Q:\mathrm{ECl}(q)\cap F\mathrm{\ne }\mathrm{\varnothing }\}\mathrm{.}$ Thus one $a$-move of $N^{\mathrm{\prime }}$ does exactly what $N$ can do by any number of $\epsilon$-moves, then one $a$-move, then any number of $\epsilon$-moves.

We claim that for every nonempty word $w$, the states reachable from $q_0$ in $N^{\mathrm{\prime }}$ after reading $w$ are exactly the states reachable from $q_0$ in $N$ after reading $w$. The proof is by induction on $\mathrm{\mid }w\mathrm{\mid }$: for one letter this is the definition of ${\delta }^{\mathrm{\prime }}$, and appending one more letter repeats the same closure-before-and-after simulation.

If $w=\epsilon$, then $N$ accepts $w$ exactly when $\mathrm{ECl}(q_0)\cap F\mathrm{\ne }\mathrm{\varnothing }$, which is exactly the condition $q_0\in F^{\mathrm{\prime }}$ from step 1.1. If $w\mathrm{\ne }\epsilon$, then step 2.1 and [L2] show that $N$ and $N^{\mathrm{\prime }}$ have the same reachable accepting states after reading $w$. Hence $L(N^{\mathrm{\prime }})=L(N)$.

For union, first replace $N_L$ and $N_K$ by disjoint isomorphic copies. Add a fresh start state with $\epsilon$-transitions to the copied start states, keep all copied transitions, and take the union of the two copied accepting sets as the new accepting set. By [L1] and [L2], every accepting run chooses one copy at the start and then stays inside that copy, so a word is accepted exactly when one of the two original machines accepts it. Thus the new language is $L\cup K$.

For concatenation, take disjoint copies of $N_L$ and $N_K$, use the copied start state of $N_L$ as the new start state, add an $\epsilon$-transition from each copied accepting state of $N_L$ to the copied start state of $N_K$, and designate only the copied accepting states of $N_K$ as accepting. Then [L1] and [L3] show that a successful run is exactly a decomposition of the input as $uv$ with $u\in L$ and $v\in K$, so the new machine recognizes $LK$.

For star, add a fresh start state, make it the only accepting state, add an $\epsilon$-transition from it to the old start state of $N_L$, and add $\epsilon$-transitions from each old accepting state back to the fresh start state. By [L1] and [L3], every accepting run chooses finitely many factors from $L$, and every finite concatenation of words of $L$ is accepted. Therefore the language recognized is $L^{\ast }$.

Hence NFA's can be built for union, concatenation, and Kleene star.

Let $L_n$ be the set of words over ${\mathrm{\Sigma }}_n$ for which at least one letter $a_i$ occurs an odd number of times. An NFA for $L_n$ has one start state and, for each $i$, two parity states that track whether the number of $a_i$'s seen so far is even or odd. By [L1], the machine may nondeterministically choose which letter $a_i$ to track, and then it accepts exactly when that tracked count ends odd. Thus $L_n$ has an NFA with $1+2n$ states.

For a prefix $u$, let $\pi (u)\in \{0,1{\}}^n$ be its parity vector, whose $i$th coordinate records whether $a_i$ has appeared an even or odd number of times in $u$. Distinct parity vectors are distinguishable: if $\pi (u)\mathrm{\ne }\pi (v)$, append the suffix consisting of exactly those letters whose parity is odd in $\pi (u)$. The resulting word from $u$ has all-even parity and is not in $L_n$, while the resulting word from $v$ still has at least one odd coordinate and lies in $L_n$.

Therefore no DFA can place two different parity vectors in the same state, because [L2] would then force the same acceptance behavior for the distinguishing suffix from step 1.2. Since there are $2^n$ parity vectors, every DFA for $L_n$ needs at least $2^n$ states.

So the subset-construction simulation of NFA's by DFA's can require exponentially many states.

On input $abb$, one computation branch takes the transition $q_0\stackrel{a}{\to }{q}_1$ at the first letter and then follows the two $b$-transitions to $q_3$, so this branch accepts. Another branch stays on the loop at the first letter, reaches $q_0$ again after reading the first $b$, and then has no way to complete the suffix $bb$ to $q_3$, so that branch rejects.

Step 1.1 shows that after reading $abb$ an accepting state is reachable, even though not every branch accepts. Therefore [L1] says the machine accepts $abb$.

This contradicts [A1]. NFA acceptance is existential over branches, not universal.

The definition distinguishes the alphabet letters from $\epsilon$-moves: letters of $\mathrm{\Sigma }$ are read from the input word, whereas an $\epsilon$-transition changes state without reading any letter.

So $\epsilon$ is not part of the input alphabet itself. It is extra transition notation for "read nothing."

This contradicts [A1]. Therefore the claim is false.