Finite Automata
Conversion of NFA to DFA
Conversion of NFA to DFA
Let M2 = < Q2 , 
,
q2,0 , 
2 , A2 > be an
NFA
that recognizes a language L.
Then the DFA M
= < Q, ,
q0 , , A > that satisfies the following conditions recognizes L:
Q = 2Q2 , that is the set of all subsets of Q2 ,
q0 = { q2,0 } ,
( q, a ) = 
for each state q in Q and each symbol a in and
A = { q 
Q | q 
A2
}
To obtain a DFA M = < Q, ,
q0 , , A > which accepts the same language as the given
NFA
M2 = < Q2 , ,
q2,0 , 2 , A2 > does,
you may proceed as follows:
Initially Q = .
First put { q2,0 } into Q. { q2,0 } is the initial state of the DFA M.
Then for each state q in Q do the following:
add the set , where here is that of NFA M2,
as a state to Q if it is not already in Q for each symbol a
in .
For this new state, add
( q, a ) =
to
, where the on the right hand side
is that of NFA M2.
When no more new states can be added to Q, the process terminates. All the states of Q that contain
accepting states of M2 are accepting states of M.
Note: The states that are not reached from the initial state are not included in Q obtained by this procedure.
Thus the set of states Q thus obtained is not necessarily equal to 2Q2 .
Example 1: Let us convert the following NFA
to DFA.
Initially Q is empty.
Then since the initial state of the DFA is {0} , {0} is added to Q.
Since 2( 0 , a ) = { 1 , 2 } ,
{ 1 , 2 } is added to Q and ( { 0 } , a ) =
{ 1 , 2 } .
Since 2( 0 , b ) =
,
is added to
Q and ( { 0 } , b ) =
.
At this point Q = { {0} , { 1 , 2 },
} .
Then since { 1 , 2 } is now in Q, the transitions from { 1 , 2 } on symbols a and b are computed.
Since 2( 1 , a ) = { 1 , 2 } , and
2( 2 , a ) = ,
( { 1 , 2 } , a ) = { 1 , 2 } .
Similarly ( { 1 , 2 } , b ) = { 1 , 3 } . Thus { 1 , 3 } is added to Q .
Similarly ( { 1 , 3 } , a ) = { 1 , 2 } and
( { 1 , 3 } , b ) = .
Thus
no new states are added to Q . Since the transitions from all states of Q have been
computed and no more states are added to Q, the conversion process stops here.
Note that there are no states of Q2 in .
Hence there are no states that M2 can go to from .
Hence (
, a ) =
(
, b ) =
.
For the accepting states of M, since states 0 and 1 are the accepting states of the NFA, all the states of
Q that contain 0 and/or 1 are accepting states. Hence { 0 }, { 1 , 2 } and { 1 , 3 } are the accepting
states of M.
The DFA thus obtained is shown below.
Example 2: Similarly the NFA
is converted to the following DFA:
Test Your Understanding of Conversion of NFA to DFA
Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
There are two sets of questions.
Answer the questions below on converting the following NFA
to DFA.
The following notation is used in the questions:
: \delta
Next -- Equivalence of NFA-
andf NFA
Back to Study Schedule
Back to Table of Contents