Home Â» Automata Conversion from NFA to DFA

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

State01
â†’q0q0q1
q1{q1, q2}q1
*q2q2{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:

State01
â†’[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.

State01
â†’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:

State01
â†’[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: