*86*

# Conversion from NFA to DFA

In this section, we will discuss the method of converting NFA to its equivalent DFA. In NFA, when a specific input is given to the current state, the machine goes to multiple states. It can have zero, one or more than one move on a given input symbol. On the other hand, in DFA, when a specific input is given to the current state, the machine goes to only one state. DFA has only one move on a given input symbol.

Let, M = (Q, âˆ‘, Î´, q0, F) is an NFA which accepts the language L(M). There should be equivalent DFA denoted by Mâ€™ = (Qâ€™, âˆ‘â€™, q0â€², Î´â€™, Fâ€™) such that L(M) = L(Mâ€™).

## Steps for converting NFA to DFA:

**Step 1:** Initially Qâ€™ = Ï•

**Step 2:** Add q0 of NFA to Qâ€™. Then find the transitions from this start state.

**Step 3:** In Qâ€™, find the possible set of states for each input symbol. If this set of states is not in Qâ€™, then add it to Qâ€™.

**Step 4:** In DFA, the final state will be all the states which contain F(final states of NFA)

### Example 1:

Convert the given NFA to DFA.

**Solution:** For the given transition diagram we will first construct the transition table.

State | 0 | 1 |
---|---|---|

â†’q0 | q0 | q1 |

q1 | {q1, q2} | q1 |

*q2 | q2 | {q1, q2} |

Now we will obtain Î´â€™ transition for state q0.

The Î´â€™ transition for state q1 is obtained as:

The Î´â€™ transition for state q2 is obtained as:

Now we will obtain Î´â€™ transition on [q1, q2].

The state [q1, q2] is the final state as well because it contains a final state q2. The transition table for the constructed DFA will be:

State | 0 | 1 |
---|---|---|

â†’[q0] | [q0] | [q1] |

[q1] | [q1, q2] | [q1] |

*[q2] | [q2] | [q1, q2] |

*[q1, q2] | [q1, q2] | [q1, q2] |

The Transition diagram will be:

The state q2 can be eliminated because q2 is an unreachable state.

### Example 2:

Convert the given NFA to DFA.

**Solution:** For the given transition diagram we will first construct the transition table.

State | 0 | 1 |
---|---|---|

â†’q0 | {q0, q1} | {q1} |

*q1 | Ï• | {q0, q1} |

Now we will obtain Î´â€™ transition for state q0.

The Î´â€™ transition for state q1 is obtained as:

Now we will obtain Î´â€™ transition on [q0, q1].

Similarly,

As in the given NFA, q1 is a final state, then in DFA wherever, q1 exists that state becomes a final state. Hence in the DFA, final states are [q1] and [q0, q1]. Therefore set of final states F = {[q1], [q0, q1]}.

The transition table for the constructed DFA will be:

State | 0 | 1 |
---|---|---|

â†’[q0] | [q0, q1] | [q1] |

*[q1] | Ï• | [q0, q1] |

*[q0, q1] | [q0, q1] | [q0, q1] |

The Transition diagram will be:

Even we can change the name of the states of DFA.

**Suppose**

With these new names the DFA will be as follows: