NFA to DFA Example

For Complete YouTube Video: Click Here

In this class, We discuss NFA to DFA Example.

The reader should have prior knowledge of DFA and NFA. Click Here.

First Example: Convert the given NFA to DFA.

The below given NFA has the initial state q0 and the final state q2.

First, we need to draw the transition table to the NFA.

The below table shows the transition table for the given NFA.

Using the transition table of NFA, we need to construct the transition table of DFA.

We represent the transition function of NFA using δ.

We represent the transition function of DFA using δ’.

We follow the sequence of steps to find DFA from the given NFA.

Step 1: consider the initial state transition in NFA and write as it is in the transition table of DFA.

We follow the below-given representation.

δ'(q0,0) = δ(q0,0)

From the table δ(q0,0) is q0.

So δ'(q0,0) = q0.

δ'(q0,1) = δ(q0,1)

δ(q0,1) is moving to two states in the NFA.

δ(q0,1) = q0,q1.

So δ'(q0,1) = q0,q1.

We finish the DFA Transition for the state q0.

Step 2: In step one we have δ'(q0,1) = q0,q1. step 2 is to take a new combination of states.

So we consider q0,q1 as the new state in DFA.

We consider different possible combination of states as new states in DFA.

δ'((q0,q1),0) = δ((q0,q1),0)

δ((q0,q1),0) is given as δ(q0,0) ∪ δ(q1,0). ∪ represent union.

δ(q0,0) is q0 from NFA table. and δ(q1,0) is Φ.

δ((q0,q1),0)= q0 ∪ Φ

δ((q0,q1),0) = q0.

δ'((q0,q1),0) = q0.

Similarly we do for δ'((q0,q1),1).

δ'((q0,q1),1) = δ((q0,q1),1)

δ((q0,q1),1)= δ(q0,1) ∪ δ(q1,1)

δ((q0,q1),1) = q0,q1 ∪ q2.

δ((q0,q1),1) = q0,q1,q2.

δ'((q0,q1),1) = q0,q1,q2.

We defined the DFA transition for state q0q1.

In the state q0q1, we have a new combination. q0q1q2.

The combination q0q1q2 considered as a new state in DFA.

Repeat step 2 till no new combinations found.

The below diagram shows the final DFA transition table and transition diagram.

The above given NFA is finding strings containing last two characters 11.

The DFA for the same question is constructed in our previous classes.

We got the same DFA that we constructed in our examples.