NFA to DFA Conversion Solved Examples

As we already discussed, conversion from NFA to DFA with its examples. In this lecture, we will see solved examples of NFA to DFA conversion.

NOTE: you can find the algorithm of NFA to DFA conversion in the previous lecture.

Example 1: NFA to DFA Conversions

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

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 not exist in NFA table) and will be added to the states column of DFA table. Following is the Transitions for q0q1.

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

                      = {q0q1} ∪ {ϕ}  

                      = {q0q1}

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

                      = {ϕ} ∪ {q1q2}  

                      = {q1q2}

Following is the updated DFA table

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

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

                      = {ϕ} ∪ {q0}  

                      = {q0}

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

                      = {q1q2} ∪ {ϕ}  

                      = {q1q2}

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

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

Important: As q0 was the final state in NFA Table. That’s why, all those states will be the final states where q0 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.