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

Part III. NFA to DFA Conversion

Consider the following NFA,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
In the above NFA, from state q0, there are 3 possible moves for input symbol, a. ie.. to q0, q1, q2. 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( q0) to denote the Epsilon closure of state q0.
For example,
Example 1:
Consider the following NFA,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Compute the Epsilon closure of all states.
ECLOSE(q0) = {q0, q1, q2, q3}
ECLOSE(q1) = {q1, q2, q3}
ECLOSE(q2) = {q2, q3}
ECLOSE(q3) = {q3}

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:
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
The above NFA has states, q0, q1, q2. The start state is q0. The final state is q2.
Step a: Find the Epsion closure of all states.
ECLOSE(q0) = {q0, q1, q2}
ECLOSE(q1) = { q1, q2}
ECLOSE(q2) = {q2}
The states of the new NFA will be {q0, q1, q2}, {q1, q2}, {q2}.
The start state of the new NFA will be the epsilon closure of the start state q0.
Thus the start state of the new NFA will be {q0, q1, q2}
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 {q0, q1, q2}, {q1, q2}, {q2}, since they contain the final state q2 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},
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Now we have the new NFA without epsilon transitions.
The transition table for the new NFA is,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Let us say,
{q0, q1, q2} as qx
{q1, q2} as qy
{q2} as qz
Then the transition table will become,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
The transition diagram for the new NFA is,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Above is the NFA without epsilon transitions.
Note that above NFA is also a DFA.

Example 2:
Convert the following NFA to DFA.
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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 q0,
Seek all the transitions from state q0 for all input symbols a and b.
We get,
δ(q0, a) = {q0, q1}
δ(q0, b) = {q0}
Now we got,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Here we got a new state, {q0, q1}
Step b:
Consider the state {q0, q1},
Seek all the transitions from state {q0, q1}for all input symbols a and b.
We get,
δ({q0, q1}, a) = δ(q0, a) ∪ δ(q1, a)
= {q0, q1} ∪ q2
= {q0, q1, q2}
δ({q0, q1}, b) = δ(q0, b) ∪ δ(q1, b)
= q0 ∪ q1
= {q0, q1}
Now we got,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Here we got a new state, {q0, q1, q2}
Step c:
Consider the state {q0, q1, q2},
Seek all the transitions from state {q0, q1, q2}for all input symbols a and b.
We get,
δ({q0, q1, q2}, a) = δ(q0, a) ∪ δ(q1, a) ∪ δ(q2, a)
= {q0, q1} ∪ q2 ∪ q3
= {q0, q1, q2, q3}
δ({q0, q1, q2}, b) = δ(q0, b) ∪ δ(q1, b) ∪ δ(q2, b)
= q0 ∪ q1  ∪ q3
= {q0, q1, q3}
Now we got,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Here we got 2 new states, {q0, q1, q2, q3} and {q0, q1, q3}.

Step d:
Consider each one of these states, {q0, q1, q2, q3} and {q0, q1, q3}
Step d.i:
Consider the state {q0, q1, q2, q3},
Seek all the transitions from state {q0, q1, q2, q3}for all input symbols a and b.
We get,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Step d.i:
Consider the state {q0, q1,q3},
Seek all the transitions from state {q0, q1,q3} for all input symbols a and b.
We get,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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 {q0, q1, q2},{q0, q1, q2, q3},{q0, q1,q3}, since they contain at least one final state of the NFA
(q2 or q3).
Let us say,
qas A,
{q0, q1} as B,
{q0, q1, q2} as C,
{q0, q1, q2, q3} as D, and
{q0, q1,q3} as E
Then the transition table will become,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
The transition diagram corresponding to the DFA is,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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 q0,
Seek all the transitions from state q0 for all input symbols a and b.
We get,
δ(q0, a) = {q0, q1}
δ(q0, b) = {q2}
Now we got,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Step b:
Step b.i:
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Step b. i. i:
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Step b.ii
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Thus there are no more new states. The above is the transition table for the new NFA.
The start state is q0.
The final states are qand {q1, q2}, since they contain the final state, q2 of the NFA.
Let we say,
q0as A
{q0, q1} as B
{q1, q2} as C
q2 as D.
The new transition table is,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
The transition diagram for the DFA is
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Example 4:
Consider the NFA,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
 

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(q0), ECLOSE(q1), ECLOSE(q2).
Find the Epsion closure of all states.
ECLOSE(q0) = {q0, q1, q2}
ECLOSE(q1) = {q1, q2}
ECLOSE(q2) = {q2}

The states of the new NFA will be {q0, q1, q2}, {q0, q1, q2}.
The start state of the new NFA will be the epsilon closure of the start state q0.
Thus the start state of the new NFA will be {q0, q1, q2}
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 {q0, q1, q2}, {q1, q2}, {q2}, since they contain the final state q2 of the old NFA.

Next we need to find the transitions of these new states on input symbols 0 and 1.
Consider state {q0, q1, q2},
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Let us say,
{q0, q1, q2} as A,
{q1, q2} as B, and
{q2} as C.
Then the NFA without epsilon transitions is,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
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, q1,
δ(q1, a) = {q1, q2}
δ(q1, b) = {q1}
Now we got,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
Input symbol
Step b:
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
The start state is q1
The final state is {q1, qf}
Let us say,
q1 as A,
{q1, q2} as B,
{q1, q} as C.
Then the transition table will become,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
The transition diagram is,
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
 

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.
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
2. Convert the following NFA to DFA.
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)
3. Convert the following NFA to DFA.
NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE)

The document NFA to DFA Conversion | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
18 videos|69 docs|44 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on NFA to DFA Conversion - Theory of Computation - Computer Science Engineering (CSE)

1. What is NFA to DFA conversion in computer science engineering?
Ans. NFA to DFA conversion is a process in computer science engineering where a Non-deterministic Finite Automaton (NFA) is transformed into an equivalent Deterministic Finite Automaton (DFA). This conversion enables the implementation of NFA-based algorithms using DFA, which often leads to more efficient and optimized computations.
2. Why is NFA to DFA conversion important in computer science engineering?
Ans. NFA to DFA conversion is important in computer science engineering as it allows for easier analysis and manipulation of non-deterministic systems. By converting NFAs to DFAs, algorithms and techniques that are specifically designed for deterministic systems can be applied, leading to improved efficiency, reliability, and accuracy in various computational tasks.
3. How does NFA to DFA conversion work?
Ans. NFA to DFA conversion involves creating a DFA that simulates the behavior of the original NFA. This is done by considering the power set of the states in the NFA as the states of the DFA. The new DFA transitions are determined based on the transitions of the NFA, considering all possible combinations of NFA states for a given input symbol. The resulting DFA is then minimized to remove redundant states and transitions.
4. What are the advantages of NFA to DFA conversion?
Ans. The advantages of NFA to DFA conversion include improved efficiency in computation, simplification of algorithms, and enhanced understanding and analysis of non-deterministic systems. DFA-based algorithms are generally easier to implement, optimize, and debug compared to NFA-based algorithms. Additionally, DFA can be easily simulated and represented in software or hardware systems.
5. Are there any limitations to NFA to DFA conversion?
Ans. While NFA to DFA conversion offers several benefits, it also has some limitations. The conversion process can result in an exponential increase in the number of states and transitions, leading to larger and more complex DFAs. This can impact memory usage and computational resources. Additionally, some NFAs with complex behaviors or infinite languages may not have an equivalent DFA, making the conversion impossible in such cases.
18 videos|69 docs|44 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Sample Paper

,

mock tests for examination

,

MCQs

,

Viva Questions

,

practice quizzes

,

Semester Notes

,

Exam

,

Extra Questions

,

past year papers

,

Free

,

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

,

Objective type Questions

,

Important questions

,

study material

,

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

,

Previous Year Questions with Solutions

,

pdf

,

ppt

,

video lectures

,

shortcuts and tricks

,

Summary

,

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

;