# Determinize e-NFA to DFA

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.

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: 