# Converting Epsilon NFA to NFA using Epsilon Closure

Given an Epsilon NFA transition table or transition diagram, task is to convert the $\epsilon$-NFA to NFA.

#### Solution:

Let, E be the name of the $\epsilon$-NFA. The tuple of the epsilon automaton are, $E = (Q, \sum, \delta, q_0, F) = ( \{ p,q,r \}, \{ a,b,c \}, \delta, p, \{ r \} )$

###### Informal Explanation:

First Task is to find epsilon closure of all the state of the finite automaton. In order to do so take the state and for each outgoing edge with input symbol of epsilon go to that state. From that state keep going to other states the same way following epsilon. Basically it is the states on the path following only epsilon symbol.

Epsilon closure of state is the state itself and any other states that are reachable along the path following only epsilon symbol.

Epsilon closure is identified with ECLOSE(q) for state q. So, $ECLOSE(p) = \{ p,q,r \} \\ ECLOSE(q) = \{ q \} \\ ECLOSE(r) = \{ r \} \\$

Epsilon closure of p is set {p,q,r} because from p on seeing epsilon the non deterministic finite automaton can stay in the same state. It may also go to q on seeing epsilon. Again r is also in the set because from p on seeing epsilon there is a transition to r. If upon reaching q or r from p, there were epsilon transition the also go to those states and include them in the ECLOSE set of p. $p \xrightarrow[ ]{ \epsilon } q \\ p \xrightarrow[ ]{ \epsilon } r \\$

In case of epsilon closure of q and r states there are no transitions on epsilon. So their only ECLOSE is singleton set containing that state itself.

## One thought on “Converting Epsilon NFA to NFA using Epsilon Closure”

1. Ravi Kaushik says:

Here , In removal of Epsilon , new NFA will have 2 final states, i.e. P and R, and transitions will be-
t(P,c)->R
t(P,c)->Q
t(P,b)->Q
t(Q,a)->P
t(Q,c)->P
t(Q,c)->Q

Like