# 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 thealgorithmof 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 q1Any 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:Asq0was the final state in NFA Table. That’s why, all those states will be thefinal stateswhere 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.