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.
Advertisements

Converting NFA to DFA by Complete and Lazy Subset Construction

Question

Given a transition table construct the NFA and using subset construction generate the DFA.


Task:

Task is to convert the NFA N = ( Q_N, \sum, \delta_N, q_0, F_N ) to DFA D = ( Q_D, \sum, \delta_D, \{ q_0 \}, F_D ) such that L(D) = L(N) . Both DFA and the NFA will accept the same language.


Transition Table:
NFA transition table for subset construction
NFA transition table for subset construction

Transition Diagram:
 nfa from transition table
nfa from transition table

NFA Tuples:
N = ( Q_N, \sum, \delta_N, q_0, F_N ) \\  

  = ( \{ p,q,r,s \}, \{ 0,1 \}, \delta, p, \{ s \} )  

Power set of NFA states Q_N :

Since the NFA has 4 states its power set will contain 2^4 = 16 states. Omitting the empty set \emptyset there will be 2^4 - 1 = 15 states.

If Q_N is set of states of NFA the P(Q_N) which is the power set of Q_N are possible states of the DFA Q_D .

Each sets in the power sets can be named something else to make it easy to understand. Each of the sets in the power set represent a state in the DFA.

Q_N = \{ p,q,r,s \} 

P(Q_N) = \{ \{ \},\{ p \},\{ q \},\{ r \},\{ s \}, \{ p,q \}, \{ p,r \}, \{ p,s \}, \{ q,r \}, \{ q,s \}, \{ r,s \},  
        \{ p,q,r \}, \{ p,q,s \}, \{ p,r,s \}, \{ q,r,s \}, \{ p,q,r,s \} \}   

Subset Construction:

The NFA can be converted to DFA using complete subset construction or by lazy evaluation of states. I will show both methods.

F_D is all the set of N states that includes at least one accepting state. Final state of the DFA F_D is set of subset of NFA states Q_N such that S \cap F_N \ne \emptyset .

For each set S \subseteq Q_N and for each input symbol a in \sum ,

\delta_D (S,a) = \bigcup\limits_{\text{p in S}} \delta_N (p,a)

This above is the formula to fill subset table. Although when filling by hand it is clearly visible.

complete subset construction nfa to dfa
complete subset construction nfa to dfa

This will be the transition table for the DFA. Although not all the 2^N states will be there. First thing to do is where ever there is the final state of the NFA mark that with star and p will also be start state for the DFA.

The table can be filled using shortcut by first copying the NFA table for the first four states since they are same as the NFA. Next for each element in the set for an copy from its corresponding row and union all the sets.

The same thing is done in the formula above. To get the transition from a state ( each of the sets in the power set ) for an input symbol which replaces a it produces the output. Right side of the formula takes each element from the set and for the input symbol it produces an item and unions them.

For example,

\delta_D ( \{ p,s \}, 0) = \delta_N (p,0) \cup \delta_N (s,0)  
         = \{ p,q \} \cup \{ s \}  
         = \{ p,q,s \}  

Another example,

\delta_D ( \{ p,q,r,s \}, 1) = \delta_D ( \{ p,q,r \} ,1) \cup \delta_N (s,1)  
            = \{ p,r \} \cup \{ s \}  
            = \{ p,r,s \}  

Here, I just used the pre-computed value in the subset table. Since {p,q,r} is computed beforehand so I get the value from the table.

Each sets can be renamed to something else. Here I name sets from 1 to 15. Although it becomes a little bit confusing with the input symbol but it will take a lot of work to change things.

After renaming the states in the subset table,

subset construction renamed dfa states
subset construction renamed dfa states

Reachable States:

Only reachable states of power set of Q_N or the reachable states of the DFA Q_D .

subset construction reachable states of dfa
subset construction reachable states of dfa

Constructed DFA:
complete subset construction dfa
complete subset construction dfa
Lazy Evaluation / Subset Construction:

The above method is very slow and time consuming. Since all 2^N are not reachable for every DFA so this method will speed up the process by avoiding extra work.

Lazy evaluation to construct dfa from subset
Lazy evaluation to construct dfa from subset

Start with the start state and only construct the states the are reachable from starting state and similarly follow those states.


After Renaming:
Lazy evaluation to construct dfa from subset renamed table
Lazy evaluation to construct dfa from subset renamed table

Generated DFA using Lazy Subset Construction:
lazy subset construction dfa
lazy subset construction dfa

As it is visible both DFA are same.

NFA Extended Transition Function Input Processing

Question:

\sum = \{ 0,1 \} \\   \\  L = \{ w|w \text{ over} \sum^* \text{ where w has 1 before the ending symbol} \}

Equivalent regular expression: (0 + 1)^* 1 (0 + 1)


The NFA:

NFA accepting w 1 alphabet
NFA accepting w 1 alphabet

Here,
N = (Q, \sum, \delta, q_0, F) = ( \{q_0,q_1,q_2 \} , \{ 0,1 \} , \delta , q_0 , \{ q_2 \} )


Transition Table:

NFA transition table
NFA transition table

Transition Function:

\delta (q_0, 0 ) = \{ q_0 \} \\  \\  \delta (q_0, 1 ) = \{ q_0, q_1 \} \\  \\  \delta (q_1, 0 ) = \{ q_2 \} \\  \\  \delta (q_1, 1 ) = \{ q_2 \} \\  \\  \delta (q_2, 0 ) = \emptyset \\  \\  \delta (q_2, 1 ) = \emptyset \\


Input Processing Shown with Arrows:

For input string, w = 011
nfa input tracing 011
nfa input tracing 011

For input string, w = 01010
nfa 01010
nfa 01010

Extended transition Function Input Processing:

For input, w = 011

\hat{\delta} (q_0, \epsilon ) = \{ q_0 \} \\     \\  \\    \hat{\delta} (q_0, 0 ) = \{ q_0 \} \\    \\  \\    \hat{\delta} (q_0, 01 ) = \delta ( \hat{\delta} (q_0, 0 ), 1 ) \\  ............. = \delta ( q_0, 1 ) \\   ............. = \{ q_0, q_1 \} \\     \\  \\    \hat{\delta} (q_0, 011 ) = \delta ( \hat{\delta} (q_0, 01 ), 1 ) \\  .............. = \delta ( \{ q_0, q_1 \}, 1 ) \\  .............. = \delta ( q_0, 1 ) \cup \delta ( q_1, 1 ) \\  .............. = \{ q_0, q_1 \} \cup \{ q_2 \} \\   .............. = \{ q_0, q_1, q_2 \} \\


For input, w = 01010. Since sub-string 01 is already calculated I will reuse it.

\hat{\delta} (q_0, 010 ) = \delta ( \hat{\delta} (q_0, 01 ), 0 ) \\  .............. = \delta ( \{ q_0, q_1 \}, 0 ) \\  .............. = \delta ( q_0, 0 ) \cup \delta ( q_1, 0 ) \\  .............. = \{ q_0 \} \cup \{ q_2 \} \\   .............. = \{ q_0, q_2 \} \\     \\  \\    \hat{\delta} (q_0, 0101 ) = \delta ( \hat{\delta} (q_0, 010 ), 1 ) \\  ................. = \delta ( \{ q_0, q_2 \}, 1 ) \\  ................. = \delta ( q_0, 1 ) \cup \delta ( q_2, 1 ) \\  ................. = \{ q_0, q_1 \} \cup \emptyset \\   ................. = \{ q_0, q_1 \} \\     \\  \\    \hat{\delta} (q_0, 01010 ) = \delta ( \hat{\delta} (q_0, 0101 ), 0 ) \\  .................. = \delta ( \{ q_0, q_1 \}, 0 ) \\  .................. = \delta ( q_0, 0 ) \cup \delta ( q_1, 0 ) \\  .................. = \{ q_0 \} \cup \{ q_2 \} \\   .................. = \{ q_0, q_2 \} \\