##### Finite Automata

##
Conversion of NFA to DFA

**Conversion of NFA to DFA **

Let M_{2} = < Q_{2} , ,
q_{2,0} , _{2} , A_{2} > be an
NFA
that recognizes a language L.
Then the DFA M
= < Q, ,
q_{0} , , A > that satisfies the following conditions recognizes L:

**Q** = 2^{Q2} , that is the set of all subsets of Q_{2} ,

q_{0} = { q_{2,0} } ,

( q, a ) =
for each state q in **Q** and each symbol a in and

A = { q Q | q A_{2}
}

To obtain a DFA M = < Q, ,
q_{0} , , A > which accepts the same language as the given
NFA
M_{2} = < Q_{2} , ,
q_{2,0} , _{2} , A_{2} > does,
you may proceed as follows:

Initially **Q **= .

First put { q_{2,0} } into **Q**. { q_{2,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 M_{2},
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 M_{2}.

When no more new states can be added to **Q**, the process terminates. All the states of **Q** that contain
accepting states of M_{2} 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 2^{Q2} .

**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 Q_{2} in .
Hence there are no states that M_{2} 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 **