BranchesHistoryHelpLogin
Welcome guest
You're not logged in.
305 users online, thereof 1 logged in

Application: Application of the Theorem to Reduce $\epsilon$-NFA to NFA

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.

Ad Example $(2)$

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.$

Ad Example $(3)$

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:

  1. 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.$
  2. 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.$
  3. 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]

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 4.0 by:

This work is a derivative of:

Bibliography (further reading)

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

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