NFA to DFA Conversion Solved Examples

Conversion from NFA to DFA may provide the following results,

• The number of states in the resulting DFA may differ from that of the original NFA.
• The DFA can have a maximum of 2ⁿ states where “n” is the number of states in the NFA.

Generally, a relationship exists between the number of states in NFA and DFA.

1 <= n <= 2m

Where,

• n represents the number of states in the DFA
• m represents the number of states in the NFA

Every nondeterministic finite automaton (NFA) can be converted to a deterministic finite automaton (DFA).

Converting NFA to DFA Algorithm

There are four basic steps for the conversion of NFA to DFA.

• Step 01: Draw an NFA Graph or diagram if it is not given.
• Step 02: Draw the NFA transition Table.
• Step 03: Convert the NFA transition Table to the DFA transition Table.
  • If any new state appears while converting the NFA to DFA then it will be added to the state column of the DFA Table.
  • If “x” was the final state in NFA, then all those states will be the final in DFA where “x” exists.
• Step 04: Convert the DFA table to the DFA Diagram.

Example 1: NFA to DFA Conversion

Problem: Draw an NFA that accepts all the strings ending with “1” over Σ {0,1} and convert this NFA to its corresponding DFA.

Note: NFA graphs or transition tables can be given to convert it into corresponding DFA tables or graphs 

Step 01: Draw NFA Graph

The following is the NFA graph for conversion into DFA.

Step 02: Draw the NFA transition Table.

The NFA transition table of the above NFA is given below

Don’t confuse: dash (“-“) symbol represents the empty symbol (ϕ). 

Step 03: Conversion of NFA To DFA transition Table

Initially, the NFA table has three states: q0 and q1 Any new state is added to the DFA states column.

First, Select the first two rows of the NFA transition table, which will become the first two rows of the DFA transition table. It is given below

The q0q1 is a new state and will be added to the states column. Following is the Transitions for q0q1.

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0} ∪ {ϕ}  

                      = {q0}

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q0q1} ∪ {ϕ}  

                      = {q0q1}

The transition of q0q1 against input 0 is q0, and the transition against input 1 is q0q1. Hence, the updated DFA table is given below.

At this stage, all newly generated states are executed successfully for their transitions. So, the DFA table is ready.

Important: As q1 was the final state in NFA Table. That’s why, all those states will be the final states where q1 is present. Simply mark with “*” to represent the final state. 

So, the following is the updated table of DFA with its final states

Step 4: Now draw DFA according to the DFA transition table

The DFA transition table contains two states (q0, q0q1) in its state column. Thus, the desired DFA machine graph will contain these similar states, and transitions will be made according to the DFA transition table.

Example 02: NFA to DFA Conversion

Problem: Draw an NFA of all binary strings in which the 2nd last bit is 1 and convert this NFA to its corresponding DFA.

Note: We will solve this problem according to the algorithm of NFA to DFA coversion. Let’s solve it.

Step 01: Draw NFA Graph.

The following is the NFA graph that has to be converted into DFA.

Step 02: Draw the NFA transition Table.

The NFA transition table of the above NFA is given below

Step 03: Conversion of NFA To DFA transition Table

Initially, the NFA table has three states: q0, q1, and q2. Any new state is added to the DFA states column.

First, Select the first two rows of the NFA transition table, which will become the first two rows of the DFA transition table. It is given below

The q0q1 is a new state and will be added to the states column. Following is the Transitions for q0q1.

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0} ∪ {q2}  

                      = [q0q2]  // new state generated

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q0q1} ∪ {q2}  

                      = {q0q1q2}  // new state generated

The transition of q0q1 against input 0 is q0q2, and the transition against input 1 is q0q1q2. Hence, the updated DFA table is given below.

q0q2 and q0q1q2 are the new states for the states column. We need to find the transitions for both newly generated states. Following is the Transitions for q0q2.

δ([q0q2], 0) = δ(q0, 0) ∪ δ(q2, 0)  

                      = {q0} 

                      = [q0]   // already found in DFA table

δ([q0q2], 1) = δ(q0, 1) ∪ δ(q2, 1)  

                      = {q0q1}

                      = {q0q1}  

                      = [q0q1]  // already found in DFA table

The transition of q0q2 against input 0 is q0, and the transition against input 1 is q0q1. Hence, the updated DFA table is given below.

Following is the Transitions for q0q1q2.

δ([q0q1q2], 0) = δ(q0, 0) ∪ δ(q1, 0)  ∪ δ(q2, 0)  

                      = {q0} ∪ {} ∪ {q2}

                      = [q0q2]   // already found in DFA table

δ([q0q1q2], 1) = δ(q0, 1) ∪ δ(q1, 1)  ∪ δ(q2, 1)   

                      = {q0} ∪ {q1} ∪ {q2}

                      = [q0q1q2]  // already found in DFA table

The transition of q0q1q2 against input 0 is q0q2, and the transition against input 1 is q0q1q2. Hence, the updated DFA table is given below.

At this stage, all newly generated states are executed successfully for their transitions. So, the DFA table is ready.

Important: As q2 was the final state in NFA, all those states will be the final in DFA where q2 exists. Therefore, the DFA Table with all its final states is given under,

Step 4: Now draw DFA according to the DFA transition table

The DFA transition table contains four states (q0, q0q1, q0q2, q0q1q2) in its state column. Thus, the desired DFA machine graph will contain these similar states, and transitions will be made according to the DFA transition table.

 

Example 3: NFA to DFA Conversions

Step 01: Draw NFA Graph

The following is the NFA graph that needs to be converted to a DFA.

Step 02: Draw the NFA transition Table.

The following is the NFA transition table which is derived from the given NFA.

Note: All transitions are made according to the NFA transition table to get the DFA transition table.

Step 03: Conversion of NFA To DFA transition Table

Initially, the NFA table has three states: q0 and q1 Any new state is added to the DFA states column.

First, Select the first two rows of the NFA transition table, which will become the first two rows of the DFA transition table. It is given below

The q0q1 is a new state (as it does not exist in the NFA table) and will be added to the states column of the DFA table. Following is the Transitions for q0q1.

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0q1} ∪ {ϕ}  

                      = {q0q1}

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q0} ∪ {q2}  

                      = {q0q2}

Following is the updated DFA table

The q0q2 is a new state and will be added to the states column. Following is the Transitions for q0q2.

δ([q0q2], 0) = δ(q0, 0) ∪ δ(q2, 0)  

                      = {q0q1} ∪ {ϕ}  

                      = {q0q1}

δ([q0q2], 1) = δ(q0, 1) ∪ δ(q2, 1)  

                      = {q0} ∪ {ϕ}  

                      = {q0}

So, the following is the updated table of DFA with its final states

All newly generated states are executed successfully for their transitions at this stage. So, the DFA table is ready.

Important: As q2 was the final state in NFA Table. That’s why, all those states will be the final states where q2 is present. Simply mark with “*” to represent the final state.

Step 4: Now draw DFA according to the DFA transition table

The DFA machine graph will include similar states and transitions based on the DFA transition table.

Example 4: NFA to DFA Conversions

Step 01: Draw NFA Graph

The following is the NFA graph that needs to be converted to a DFA.

Step 02: Draw the NFA transition Table.

The following is the NFA transition table which is derived from the given NFA.

Note: All transitions are made according to the NFA transition table to get the DFA transition table.

Step 03: Conversion of NFA To DFA transition Table

Initially, the NFA table has three states: q0 and q1 Any new state is added to the DFA states column.

First, Select the first two rows of the NFA transition table, which will become the first two rows of the DFA transition table. It is given below

The q0q1 is a new state (as it does not exist in the NFA table) and will be added to the states column of the DFA table. Following is the Transitions for q0q1.

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0q1} ∪ {ϕ}  

                      = {q0q1}

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q1} ∪ {q0q1}  

                      = {q0q1}

Following is the updated DFA table

The q1 is a new state and will be added to the states column. Following is the Transitions for q1.

δ([q1], 0) = {qϕ}  

δ([q1], 1) = {q0q1}

The following is the updated DFA table with all  its final states

The above given is the required DFA table

Important: As q1 was the final state in NFA Table. That’s why, all those states will be the final states where q1 is present. Simply mark with “*” to represent the final state.

Step 4: Now draw DFA according to the DFA transition table

The following is the converted DFA from the given NFA.

 

Example 5: NFA to DFA Conversions

Step 01: Draw NFA Graph

The following is the NFA graph that needs to be converted to a DFA.

Step 02: Draw the NFA transition Table.

The following is the NFA transition table which is derived from the given NFA.

Note: All transitions are made according to the NFA transition table to get the DFA transition table.

Step 03: Conversion of NFA To DFA transition Table

Initially, the NFA table has three states: q0 and q1 Any new state is added to the DFA states column.

First, Select the first two rows of the NFA transition table, which will become the first two rows of the DFA transition table. It is given below

The q0q1 is a new state (as it does not exist in the NFA table) and will be added to the states column of the DFA table. Following is the Transitions for q0q1.

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0q1} ∪ {q0}  

                      = {q0q1}

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q2} ∪ {q1}  

                      = {q1q2}

Following is the updated DFA table

The q0q2 is a new state (as it does not exist in the NFA table) and will be added to the states column of the DFA table. Following is the Transitions for q1q2.

δ([q1q2], 0) = δ(q1, 0) ∪ δ(q2, 0)  

                      = {q0} ∪ {ϕ}  

                      = {q0}

δ([q1q2], 1) = δ(q1, 1) ∪ δ(q2, 1)  

                      = {q1} ∪ {q0q1}  

                      = {q0q1}

Following is the updated DFA table

The q2 is the state in the above table which is still not expressed in the state column. Simply add it also for its transitions.

δ([q2], 0) = {qϕ}

δ([q2], 1)  = {q0q1}

Following is the updated DFA table

 

 The DFA table is ready.

Important: As q2 was the final state in NFA Table. That’s why, all those states will be the final states where q2 is present. Simply mark with “*” to represent the final state.

Step 4: Now draw DFA according to the DFA transition table

The following is the DFA machine that derives from the given NFA.

 

Example 6: Convert NFA to DFA 

Step 01: Draw NFA Graph

The following is the NFA graph that needs to be converted to a DFA.

Step 02: Draw the NFA transition Table.

The following is the NFA transition table which is derived from the given NFA.

Note: All transitions are made according to the NFA transition table to get the DFA transition table.

Step 03: Conversion of NFA To DFA transition Table

Initially, the NFA table has three states: q0 and q1 Any new state is added to the DFA states column.

First, Select the first two rows of the NFA transition table, which will become the first two rows of the DFA transition table. It is given below

The q0q1 is a new state (as it does not exist in the NFA table) and will be added to the states column of the DFA table. Following is the Transitions for q0q1.

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0q1} ∪ {q2}  

                      = {q0q1q2}

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q0} ∪ {q1}  

                      = {q0q1}

Following is the updated DFA table

The q0q1q2 is a new state (as it does not exist in the NFA table) and will be added to the states column of the DFA table. Following is the Transitions for q1q2.

δ([q0q1q2], 0) = δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0)  

                      = {q0q1} ∪ {q2} ∪ {q3}  

                      = {q0q1q2q3}

δ([q0q1q2], 1) = δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1)  

                      = {q0} ∪ {q1} ∪ {q3}  

                      = {q0q1q3}

Following is the updated DFA table

The q0q1q2q3 is a new state

δ([q0q1q2q3], 0) = δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0)  ∪ δ(q3, 0)  

                      = {q0q1} ∪ {q2} ∪ {q3}  ∪ {ϕ}  

                      = {q0q1q2q3}

δ([q0q1q2q3], 1) = δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1)  ∪ δ(q3, 1)  

                      = {q0} ∪ {q1} ∪ {q3}  ∪ {q2}  

                      = {q0q1q2q3}

Following is the updated DFA table

The q0q1q3 is the state in the above table which is still not expressed in the state column. Simply add it also for its transitions.

δ([q0q1q3], 0) = δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q3, 0)  

                      = {q0q1} ∪ {q2} ∪ {ϕ} 

                      = {q0q1q2}

δ([q0q1q3], 1) = δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q3, 1)  

                      = {q0} ∪ {q1} ∪ {q2}  

                      = {q0q1q2}

Following is the updated DFA table

 The DFA table is ready.

Important: As q3 was the final state in NFA Table. That’s why, all those states will be the final states where q3 is present. Simply mark with “*” to represent the final state.

Step 4: Now draw DFA according to the DFA transition table

The following is the DFA machine that derives from the given NFA.

Note: Hence proved that,

DFA has a higher number of states as compared to NFA states. If “n” is the maximum number of states in NFA, then 2ⁿ is the maximum number of states in its corresponding DFA.