The following are examples to apply the construction given in the proof of the theorem about the reduction of $\epsilon$-NFA to NFA, reducing the examples of $\epsilon$-NFA to the corresponding NFA.

Please note that in this example, the intermediate states $p_{01}(1), p_{101}(1)$ and $p_{101}(2)$ have been added to reflect transitions marked by words with length $\ge 2$ in the original graph of the second $\epsilon$-NFA example. Also, the original $\epsilon$ transition from the state $a$ to the state $b$ disappeared, since there is no predecessor state $t$ and symbol $x\in\{0,1\}$ such that $\Delta^\prime(t,x)=a.$

In this example, no new intermediate states are needed to reduce the original $\epsilon$-NFA to an NFA. However, we have to deal with the original $\epsilon$ transitions between the states $a\to b$ and $b\to c$ and replace them according to the construction in the proof. The construction steps are as follows:

- We first take over all loop transitions $a\to a$ via $1$, $b\to b$ via $2$ and $c\to c$ via $3$. Those remain unchanged since they use words of length $1.$
- Dealing with $a\to b$ via the empty word $\epsilon$ in the original graph: There is only one predecessor transition of $a$ in the new graph, namely $\Delta^\prime(a,1)=a.$ Therefore, we add $\Delta^\prime(a,1)=b.$
- Dealing with $b\to c$ via the empty word $\epsilon$ in the original graph: There are two predecessor transitions of $b$ in the new graph, namely $\Delta^\prime(b,2)=b$ and $\Delta^\prime(a,1)=b$. Therefore, we add $\Delta^\prime(b,2)=c$ and $\Delta^\prime(a,1)=c.$

| | | | created: 2020-05-21 17:03:57 | modified: 2020-05-21 18:37:40 | by: *bookofproofs* | references: [1086], [7895]

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

[7895] **Hoffmann, Dirk**: “Theoretische Informatik, 3. Auflage”, Hanser, 2015