We want to show that the language recognized by an automaton with epsilon transitions can also be by a non-deterministic automaton without epsilon transitions. This operation will require the addition of new transitions.

Any language recognized by an NFA with ε-transitions can be recognized by an NFA (without ε-transitions) having the same number of states.

Construction of the NFA equivalent by extending δ in δ1 (the transitive closure is all the states that can be reached by a state by a given transition).

### First step: Addition of ε-transitions by transitive closure.

For all the states q accessible from p by ε-transition (in several steps), we add a ε-transition directly from p to q. We thus extend the function δ: δ1 (p, ε) = all accessible states from p by ε-transition.

### Second step: Adding additional transitions and additional initial states, then deleting the ε-transitions.

The initial states are all states accessible from the initial states by ε-transition.

For every transition from p to q by a letter, we add transitions from p to r with the

same letter for all ε-transitions from q to r: δ1(p, a) = δ(p, a) ∪ ( ∪_{q∈δ(p, a)} δ1(q, ε)).

We delete all the ε-transitions

## Example

The principle of the algorithm is to replace each path of length 1 starting with an epsilon-transition with a new transition that describes this path.

There are two path of length 1 that start with the transition on epsilon:

- (1, ε, 3)(3, b, 3)
- (1, ε, 3)(3, c, 4)

Two new transitions are added to the automaton that summarize these two paths:

- (1, b, 3)
- (1, c, 4)

And we delete the transition (1, ε, 3).

The algorithm is a little more complex in cases where several epsilon-transitions follow each other and if they go into a final state, but the general principle presented here remains valid (just apply the first step).

The use of epsilon-transitions sometimes makes it possible to describe a language more legibly. It also makes it possible to simplify the description of certain operations (for example union or concatenation -> see Thompson automaton).

The existence of epsilon-transitions makes the automaton non-deterministic since it is always possible to borrow such a transition even when there is an ordinary transition that one could borrow.

## Another example

Take the following automaton:

For this, we first have to calculate, for each state, the ε-successors of each state p, that is to say the set of states q such that there exists a path formed solely of ε-transitions starting of p arriving in q.

We calculate the ε-successors of each state: Succ ε (p) = {q, r}, Succ ε (q) = {r}, Succ ε (r) = ∅.

We obtain the following NFA:

You can then determine it with the NFA method to DFA, or determine it directly in its transitional form as the following example.

## With transition table

Let’s take the automaton and transform it into a DFA:

The first step is to calculate the epsilon-closure for each state of this automaton:

Delta(Q) | a | b | Closure-> Q’ |

p | p | – | {p,q,r} |

q | – | q | {q,r} |

r | r | – | {r} |

For each state of the closure, we calculate its transitions in the alphabet without epsilon:

Delta(Q’) | a | b |

{p,q,r} | {p,r} | {q} |

{q,r} | {r} | {q} |

{r} | {r} | – |

For each state obtained by the transitions, the closure is calculated:

Delta(Q’) | a | b |

{p,q,r} | {p,r} -> {p,q,r} | {q} -> {q,r} |

{q,r} | {r} -> {r} | {q} -> {q,r} |

{r} | {r} -> {r} | – |

Let us denote {p, q, r} = P; {q, r} = Q and {r} = R. We obtain the following automaton: