# 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
^{n}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.

- If any
**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 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** 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 thefinal stateswhere 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:Asq2was 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 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 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:Asq2was the final state in NFA Table. That’s why, all those states will be thefinal stateswhere q2 is present. Simplymark 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 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 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:Asq1was the final state in NFA Table. That’s why, all those states will be thefinal stateswhere q1 is present. Simplymark 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

: 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 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:Asq2was the final state in NFA Table. That’s why, all those states will be thefinal stateswhere q2 is present. Simplymark 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

: 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 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:Asq3was the final state in NFA Table. That’s why, all those states will be thefinal stateswhere q3 is present. Simplymark 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 ^{n}** is the maximum number of states in its corresponding DFA.