NFA to DFA Dead State Example

For Complete YouTube Video: Click Here

In this class, We discuss NFA to DFA Dead State Example.

The reader should have prior knowledge of the NFA to DFA conversion procedure explained in the previous class. Click here

Example: The below diagram shows the example NFA.

First, we write the transition table for the given NFA.

The below diagram shows the transition table.

The initial state is q0, and the final state is q4.

First Step: We start from an initial state and write the initial state in the NFA transition table in the DFA transition table.

On state q0, if we see input symbol zero, we do not move to any state. So Φ is given.

On state q0, if we see input symbol one, we move to q1 state.

The above two transitions are written in the DFA table.

Point to understand: In DFA, Φ is not allowed. We consider Φ as a new state.

Take a look at the NFA. The given NFA is accepting string 1100 only.

In our DFA examples, we already constructed logic to accept strings only 1100.

We moved to a dead state in the DFA when there was no need to check the future input string.

During the conversion process, the new state Φ is considered the dead state in DFA.

Step 2:

After writing the initial state transition, the new state that is not yet written in the DFA table is q1.

Now we write a transition to state q1 using the NFA transition table.

The process is explained in our previous class.

Now repeat step 2 till new states are possible.

Here in the last, we write transition for Φ.

This new state Φ is written as a dead state.

If we see the input symbol zero or one on dead state, we move to the dead state itself.

The below table shows the complete DFA transition.

The below diagram shows the DFA transition diagram.