Theory of Computation : NFA to DFA Conversion



An NFA can have zero, one or more than one move from a given state on a given input symbol. An NFA can also have NULL moves (moves without input symbol). On the other hand, DFA has one and only one move from a given state on a given input symbol.
 
Let X = (Qx, ∑, δx, q0, Fx) be an NDFA which accepts the language L(X). We have to design an equivalent DFA Y = (Qy, ∑, δy, q0, Fy) such that L(Y) = L(X). The following procedure converts the NDFA to its equivalent DFA −
 
Algorithm

Input − An NDFA
Output − An equivalent DFA
  • Step 1 − Create state table from the given NDFA.
  • Step 2 − Create a blank state table under possible input alphabets for the equivalent DFA.
  • Step 3 − Mark the start state of the DFA by q0 (Same as the NDFA).
  • Step 4 − Find out the combination of States {Q0, Q1,... , Qn} for each possible input alphabet.
  • Step 5 − Each time we generate a new DFA state under the input alphabet columns, we have to apply step 4 again, otherwise go to step 6.
  • Step 6 − The states which contain any of the final states of the NDFA are the final states of the equivalent DFA. 

Conversion from NFA to DFA
Suppose there is an NFA N < Q, ∑, q0, δ, F > which recognizes a language L. Then the DFA D < Q’, ∑, q0, δ’, F’ > can be constructed for language L as:
Step 1: Initially Q’ = ɸ.
Step 2: Add q0 to Q’.
Step 3: For each state in Q’, find the possible set of states for each input symbol using transition function of NFA. If this set of states is not in Q’, add it to Q’.
Step 4: Final state of DFA will be all states with contain F (final states of NFA) 

Example
Consider the following NFA shown in Figure 1.


Following are the various parameters for NFA.
Q = { q0, q1, q2 }
∑ = ( a, b )
F = { q2 }
δ (Transition Function of NFA)

Step 1: Q’ = ɸ
Step 2: Q’ = {q0}
Step 3: For each state in Q’, find the states for each input symbol.
Currently, state in Q’ is q0, find moves from q0 on input symbol a and b using transition function of NFA and update the transition table of DFA.

δ’ (Transition Function of DFA)

Now { q0, q1 } will be considered as a single state. As its entry is not in Q’, add it to Q’.
So Q’ = { q0, { q0, q1 } }

Now, moves from state { q0, q1 } on different input symbols are not present in transition table of DFA, we will calculate it like:
δ’ ( { q0, q1 }, a ) = δ ( q0, a ) ∪ δ ( q1, a ) = { q0, q1 }
δ’ ( { q0, q1 }, b ) = δ ( q0, b ) ∪ δ ( q1, b ) = { q0, q2 }
Now we will update the transition table of DFA.

δ’ (Transition Function of DFA)
Now { q0, q2 } will be considered as a single state. As its entry is not in Q’, add it to Q’.
So Q’ = { q0, { q0, q1 }, { q0, q2 } }

Now, moves from state {q0, q2} on different input symbols are not present in transition table of DFA, we will calculate it like:
δ’ ( { q0, q2 }, a ) = δ ( q0, a ) ∪ δ ( q2, a ) = { q0, q1 }
δ’ ( { q0, q2 }, b ) = δ ( q0, b ) ∪ δ ( q2, b ) = { q0 }
Now we will update the transition table of DFA.

δ’ (Transition Function of DFA)
As there is no new state generated, we are done with the conversion. Final state of DFA will be state which has q2 as its component i.e., { q0, q2 }

Following are the various parameters for DFA.
Q’ = { q0, { q0, q1 }, { q0, q2 } }
∑ = ( a, b )
F = { { q0, q2 } } and transition function δ’ as shown above. The final DFA for above NFA has been shown in Figure 2.
Note : Sometimes, it is not easy to convert regular expression to DFA. First you can convert regular expression to NFA and then NFA to DFA.
 
Example 2 : As per above mentioned algorithm


Let us consider the NDFA shown in the figure below. 
qδ(q,0)δ(q,1)
a{a,b,c,d,e}{d,e}
b{c}{e}
c{b}
d{e}
e
Using the above algorithm, we find its equivalent DFA. The state table of the DFA is shown in below.

qδ(q,0)δ(q,1)
[a][a,b,c,d,e][d,e]
[a,b,c,d,e][a,b,c,d,e][b,d,e]
[d,e][e]
[b,d,e][c,e][e]
[e]
[c, e][b]
[b][c][e]
[c][b]
The state diagram of the DFA is as follows −

No comments: