# Eliminating ε Transitions

NFA with ε can be converted to NFA without ε, and this NFA without ε can be converted to DFA. To do this, we will use a method, which can remove all the ε transition from given NFA. The method will be:

1. Find out all the ε transitions from each state from Q. That will be called as ε-closure{q1} where qi ∈ Q.
2. Then δ’ transitions can be obtained. The δ’ transitions mean a ε-closure on δ moves.
3. Repeat Step-2 for each input symbol and each state of given NFA.
4. Using the resultant states, the transition table for equivalent NFA without ε can be built.

### Example:

Convert the following NFA with ε to NFA without ε. Solutions: We will first obtain ε-closures of q0, q1 and q2 as follows:

1. ε-closure(q0) = {q0}
2. ε-closure(q1) = {q1, q2}
3. ε-closure(q2) = {q2}

Now the δ’ transition on each input symbol is obtained as:δ'(q0, a) = ε-closure(δ(δ^(q0, ε),a))

1.               = ε-closure(δ(ε-closure(q0),a))
2.               = ε-closure(δ(q0, a))
3.               = ε-closure(q1)
4.               = {q1, q2}
5.
6. δ'(q0, b) = ε-closure(δ(δ^(q0, ε),b))
7.               = ε-closure(δ(ε-closure(q0),b))
8.               = ε-closure(δ(q0, b))
9.               = Ф

Now the δ’ transition on q1 is obtained as:

1. δ'(q1, a) = ε-closure(δ(δ^(q1, ε),a))
2.               = ε-closure(δ(ε-closure(q1),a))
3.               = ε-closure(δ(q1, q2), a)
4.               = ε-closure(δ(q1, a) ∪ δ(q2, a))
5.               = ε-closure(Ф ∪ Ф)
6.               = Ф
7.
8. δ'(q1, b) = ε-closure(δ(δ^(q1, ε),b))
9.               = ε-closure(δ(ε-closure(q1),b))
10.               = ε-closure(δ(q1, q2), b)
11.               = ε-closure(δ(q1, b) ∪ δ(q2, b))
12.               = ε-closure(Ф ∪ q2)
13.               = {q2}

The δ’ transition on q2 is obtained as:

1. δ'(q2, a) = ε-closure(δ(δ^(q2, ε),a))
2.               = ε-closure(δ(ε-closure(q2),a))
3.               = ε-closure(δ(q2, a))
4.               = ε-closure(Ф)
5.               = Ф
6.
7. δ'(q2, b) = ε-closure(δ(δ^(q2, ε),b))
8.               = ε-closure(δ(ε-closure(q2),b))
9.               = ε-closure(δ(q2, b))
10.               = ε-closure(q2)
11.               = {q2}

Now we will summarize all the computed δ’ transitions:

1. δ'(q0, a) = {q0, q1}
2. δ'(q0, b) = Ф
3. δ'(q1, a) = Ф
4. δ'(q1, b) = {q2}
5. δ'(q2, a) = Ф
6. δ'(q2, b) = {q2}

The transition table can be:

Statesab
→q0{q1, q2}Ф
*q1Ф{q2}
*q2Ф{q2}

State q1 and q2 become the final state as ε-closure of q1 and q2 contain the final state q2. The NFA can be shown by the following transition diagram: 