We will prove the theorem by showing the set equality $\mathcal L(\epsilon-\operatorname{NFA})=\mathcal L(\operatorname{NFA}).$

- The definition of the non-deterministic finite automaton NFA is a special case of the definition of the epsilon non-deterministic finite automaton $\epsilon$-NFA.
- This is because we can replace a given NFA definition $A=(C,\Sigma,\Delta_A,F,s_0),$ by replacing $\Delta_A\subset (C\times\Sigma)\times C$ by a $\Delta_B:=(C\times\Sigma^*)\times C,$ getting a definition of an $\epsilon$-NFA $B=(C,\Sigma,\Delta_B,F,s_0)$. In other words, we can replace the transition relation $\Delta_A$ by a more generalized transition relation $\Delta_B\supset\Delta_A$.

- Let $A=(C,\Sigma,\Delta,F,s_0)$ be an $\epsilon$-NFA.
- We construct an NFA $A^\prime=(C^\prime,\Sigma,\Delta^\prime,F,s_0)$ as follows: We do not have to replace the sets of states $C$, the alphabet $\Sigma$, the set of final states $F$ and the starting state $s_0$.
- Every transition of symbols (words of length $1$) remain unchanged, formally, $$\Delta^\prime(s_i,\sigma)=s_{i+1}\Longleftrightarrow \Delta(s_i,\sigma)=s_{i+1}$$ for all $s_i\in C$ and $\sigma\in\Sigma$ with $\sigma\neq\epsilon.$
- Every transition $\Delta$ of a word $\omega=\sigma_1\ldots\sigma_n$ of length $|\omega|=n\ge 2$ in the form $\Delta(s,\omega)=q$, $s,q\in C$ is to be replaced by a chain of transitions of $\Delta^\prime$ with some intermediate states $p_\omega(1),\ldots,p_\omega(n-1)\in C^\prime$ with

$$\begin{array}{rcl}

\Delta^\prime(s,\sigma_1)&=&p_\omega(1)\\

\Delta^\prime(p_\omega(1),\sigma_2)&=&p_\omega(2)\\

\vdots&&\vdots\\

\Delta^\prime(p_\omega(n-2),\sigma_{n-1})&=&p_\omega(n-1)\\

\Delta^\prime(p_\omega(n-1),\sigma_n)&=&q\\

\end{array}$$ - Every transition $\Delta$ of the empty word $\epsilon$ in the form $\Delta(s,\epsilon)=q$, $s,q\in C$ is to be replaced as follows: We look for any predecessor state of $s$ in $A^\prime$, i.e. a transition of the form $\Delta^\prime(t,a)=s$. If such a predecessor state can be found, we add the transition $\Delta^\prime(t,a)=q$. Otherwise, (i.e. we cannot find any such predecessor transition), there shall be neither a direct transition $\Delta^\prime$ from the state $s$ to the state $q.$
- We replace $C$ by the set $C^\prime:=C\cup\{\text{all states added in the construction process}\}$.

- It follows by construction, that $A^\prime$ is an NFA accepting exactly the same words as the original $\epsilon$-NFA.

q.e.d

| | | | created: 2020-05-21 16:46:41 | modified: 2020-05-21 18:42:03 | by: | references: [1086]

[1086] **Erk, Katrin; Priese, Lutz**: “Theoretische Informatik”, Springer Verlag, 2000, 2. Auflage