Converting Epsilon NFA to NFA using Epsilon Closure

Task:

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

Question:

Transition Table:
epsilon nfa question
epsilon nfa question
Transition Diagram:
epsilon nfa from transition table
epsilon nfa from transition table

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.


Todo: Complete the post and add another example.
Note: I did not realize how bad( not wrong ) the example is in current context until half way through. For reference look in Introduction to automata theory, languages and computation book.

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

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s