NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Part III. NFA to DFA Conversion

Consider the following NFA,

In the above NFA, from state q₀, there are 3 possible moves for input symbol, a. ie.. to q₀, q₁, q₂. When we simulate this NFA using a program, the move from q0 for symbol a is non-deterministic. That means, which transition is to be made next cannot be determined in one move. But in a DFA, from a state, for an input symbol, only one transition exists. So it is very easy to simulate a DFA using a program. So we need to convert an NFA to an equivalent DFA. For every NFA, there exists an equivalent DFA.

5 Epsilon Closure
For converting an NFA to DFA, we first need to learn how to find the epsilon closure of a state.
Epsilon closure (ε- closure) of a state q is the set that contains the state q itself and all other states that can be reached
from state q by following ε transitions.
We use the term, ECLOSE( q₀) to denote the Epsilon closure of state q₀.
For example,
Example 1:
Consider the following NFA,

Find the epsilon closure of all states.
Here,
ECLOSE(1) = {1, 2, 4}
ECLOSE(2) = {2, 4}
ECLOSE(3) = {3}
ECLOSE(4) = {4}

Example 2:
Consider the following NFA,

Find the epsilon closure of all states.
ECLOSE(1) = {1, 2, 3, 6, 4}
ECLOSE(2) = {2, 3, 6}
ECLOSE(3) = {3, 6}
ECLOSE(4) = {4}
ECLOSE(5) = {5, 7}
ECLOSE(6) = {6}

Example 3:
Consider the following NFA,

Compute the Epsilon closure of all states.
ECLOSE(q₀) = {q₀, q₁, q₂, q₃}
ECLOSE(q₁) = {q₁, q₂, q₃}
ECLOSE(q₂) = {q₂, q₃}
ECLOSE(q₃) = {q₃}

6 Conversion of NFA to DFA
The steps involved in the conversion of NFA to DFA are,
1. Transform the NFA with Epsilon transitions to NFA without epsilon transitions.
2. convert the resulting NFA to DFA.
These steps are exaplained in detail as follows:

1. Transform the NFA with ε transitions to NFA without ε transitions.
Example 1:
Consider the following NFA with epsilon transitions:

The above NFA has states, q₀, q₁, q₂. The start state is q₀. The final state is q_2.
Step a: Find the Epsion closure of all states.
ECLOSE(q0) = {q₀, q₁, q₂}
ECLOSE(q₁) = { q₁, q₂}
ECLOSE(q₂) = {q₂}
The states of the new NFA will be {q₀, q₁, q₂}, {q₁, q₂}, {q₂}.
The start state of the new NFA will be the epsilon closure of the start state q₀.
Thus the start state of the new NFA will be {q₀, q₁, q₂}
The final states of the new NFA will be those new states that contain the final states of the old NFA.
Thus the final states of the new NFA are {q₀, q₁, q₂}, {q₁, q₂}, {q₂}, since they contain the final state q₂ of the old NFA.
Next we need to find the transitions of these new states on input symbols a, b and c.
Consider state {q0, q1, q2},



Now we have the new NFA without epsilon transitions.
The transition table for the new NFA is,

Let us say,
{q₀, q₁, q₂} as q_x
{q₁, q₂} as q_y
{q₂} as q_z
Then the transition table will become,

The transition diagram for the new NFA is,

Above is the NFA without epsilon transitions.
Note that above NFA is also a DFA.

Example 2:
Convert the following NFA to DFA.

Step 1: Transform the NFA with Epsilon transitions to NFA without epsilon transitions.
Note that above NFA does not contain any epsilon transitions.

Step 2: Convert the resulting NFA to DFA.
Step a:
Consider the start state q₀,
Seek all the transitions from state q₀ for all input symbols a and b.
We get,
δ(q₀, a) = {q₀, q₁}
δ(q₀, b) = {q₀}
Now we got,

Here we got a new state, {q₀, q₁}
Step b:
Consider the state {q₀, q₁},
Seek all the transitions from state {q₀, q₁}for all input symbols a and b.
We get,
δ({q₀, q₁}, a) = δ(q₀, a) ∪ δ(q₁, a)
= {q₀, q₁} ∪ q2
= {q0, q1, q2}
δ({q₀, q₁}, b) = δ(q₀, b) ∪ δ(q₁, b)
= q₀ ∪ q₁
= {q₀, q₁}
Now we got,

Here we got a new state, {q₀, q₁, q₂}
Step c:
Consider the state {q₀, q₁, q₂},
Seek all the transitions from state {q0, q1, q2}for all input symbols a and b.
We get,
δ({q₀, q₁, q₂}, a) = δ(q₀, a) ∪ δ(q₁, a) ∪ δ(q₂, a)
= {q₀, q₁} ∪ q₂ ∪ q₃
= {q₀, q₁, q_2, q₃}
δ({q₀, q₁, q₂}, b) = δ(q₀, b) ∪ δ(q₁, b) ∪ δ(q₂, b)
= q₀ ∪ q₁  ∪ q₃
= {q0, q1, q3}
Now we got,

Here we got 2 new states, {q₀, q₁, q_2, q₃} and {q₀, q₁, q₃}.

Step d:
Consider each one of these states, {q₀, q₁, q_2, q₃} and {q₀, q₁, q₃}
Step d.i:
Consider the state {q₀, q₁, q_2, q₃},
Seek all the transitions from state {q₀, q₁, q_2, q₃}for all input symbols a and b.
We get,

Step d.i:
Consider the state {q₀, q₁,q₃},
Seek all the transitions from state {q₀, q_1,q₃} for all input symbols a and b.
We get,

Now there are no new states generated. above is the transition table corresponding to the new DFA.
In the above DFA, the start state is q0.
The final states of the DFA are {q₀, q₁, q₂},{q₀, q₁, q_2, q₃},{q₀, q₁,q₃}, since they contain at least one final state of the NFA
(q₂ or q₃).
Let us say,
q₀ as A,
{q₀, q₁} as B,
{q₀, q₁, q₂} as C,
{q₀, q₁, q_2, q₃} as D, and
{q₀, q₁,q₃} as E
Then the transition table will become,

The transition diagram corresponding to the DFA is,

From the above diagram, it is a DFA since, there is only one transition corresponding to an input symbol from a state.
Example 3:
Consider the following NFA,

Step 1: Transform the NFA with Epsilon transitions to NFA without epsilon transitions.Note that above NFA does not contain any epsilon transitions.
Step 2: Convert the resulting NFA to DFA.
Consider the start state q₀,
Seek all the transitions from state q₀ for all input symbols a and b.
We get,
δ(q₀, a) = {q₀, q₁}
δ(q₀, b) = {q₂}
Now we got,

Step b:
Step b.i:

Step b. i. i:

Step b.ii

Thus there are no more new states. The above is the transition table for the new NFA.
The start state is q₀.
The final states are q₂ and {q₁, q₂}, since they contain the final state, q₂ of the NFA.
Let we say,
q₀as A
{q₀, q₁} as B
{q₁, q₂} as C
q₂ as D.
The new transition table is,

The transition diagram for the DFA is

Example 4:
Consider the NFA,

 

Convert the above NFA to DFA.
Step 1: Transform the NFA with Epsilon transitions to NFA without epsilon transitions.
Step a:
The states of the new NFA will be ECLOSE(q₀), ECLOSE(q₁), ECLOSE(q₂).
Find the Epsion closure of all states.
ECLOSE(q₀) = {q₀, q₁, q₂}
ECLOSE(q₁) = {q₁, q₂}
ECLOSE(q₂) = {q₂}

The states of the new NFA will be {q₀, q₁, q₂}, {q₀, q₁, q₂}.
The start state of the new NFA will be the epsilon closure of the start state q₀.
Thus the start state of the new NFA will be {q₀, q₁, q₂}
The final states of the new NFA will be those new states that contain the final states of the old NFA.
Thus the final states of the new NFA are {q₀, q₁, q₂}, {q₁, q₂}, {q₂}, since they contain the final state q₂ of the old NFA.

Next we need to find the transitions of these new states on input symbols 0 and 1.
Consider state {q₀, q₁, q₂},


Let us say,
{q₀, q₁, q₂} as A,
{q₁, q₂} as B, and
{q₂} as C.
Then the NFA without epsilon transitions is,

The above is an NFA without epsilon transitions.

Step 2: Convert the resulting NFA to DFA.
Note that above NFA is also a DFA, since from a state there is only one transition corresponding to an input symbol.

Example 5:
Consider the following NFA,

Convert this NFA to DFA.

Step 1: Transform the NFA with Epsilon transitions to NFA without epsilon transitions.
Above NFA does not contain epsilon transitions. So we need to eliminate epsilon transitions.

Step 2: Transform above NFA to DFA.
Begin from the start state, q₁,
δ(q₁, a) = {q₁, q₂}
δ(q₁, b) = {q₁}
Now we got,

Input symbol
Step b:


The start state is q₁
The final state is {q₁, q_f}
Let us say,
q₁ as A,
{q₁, q₂} as B,
{q₁, q_f } as C.
Then the transition table will become,

The transition diagram is,

 

The above is a DFA, since there is only one transition corresponding to an input symbol from every state.

Exercises:
1. Convert the following NFA to DFA.

2. Convert the following NFA to DFA.

3. Convert the following NFA to DFA.