Finite Automata
Equivalence of DFAs, NFAs and NFA-s
Subjects to be Learned
- Conversion of NFA-
to (equivalent) NFA
- Conversion of NFA to (equivalent) DFA
- Equivalence of DFAs, NFAs and NFA-
Contents
One major objective in our study of FAs and regular languages is to learn
that any language recognized by a DFA is regular and that any regular language
is recognized by a DFA. To prove the former, we are going to show that simple regular
languages are recognized by some simple DFAs and then show that using union, concatenation
and Kleene star operations, DFAs to recognize more complex languages can be constructed
from those simple DFAs. Since those operations on FAs can be described conveniently using
NFA-s, they are going to be used
to construct complex FAs from simple ones. These NFA-s
are then converted to equivalent NFAs (without s ) ,
then to DFAs so that nondeterminisms are removed and
computer programs can be written for simulating them. Finally we are going to learn that
the DFAs that recognize
a regular language can be transformed into a unique DFA by minimizing the number of their
states.
In this and the next sections we are going to study the conversion of
NFA-s to equivalent NFAs then to DFAs. The construction
of NFA-s for regular
languages is discussed in the next chapter. The minimization of states is going to be
discussed a little later in another chapter.
Conversion of NFA- to NFA
Let M1 = < Q1 , ,
q1,0 , 1 , A1 >
be an NFA- that recognizes a language L.
Then the NFA M2 = < Q2, ,
q2,0 , 2 , A2 >
that satisfies the following conditions recognizes L:
Q2 = Q1,
q2,0 = q1,0,
2( q, a ) =
1*( q , a )
= (
)
A2 = A1 { q1,0 }
if ( { q1,0 } )
A1
= A1 otherwise .
Thus to obtain an NFA M2 = < Q2,
, q2,0 ,
2 , A2 > which accepts the same
language as the given
NFA- M1 = < Q1 ,
, q1,0 ,
1 , A1 > does,
first copy the states of Q1 into
Q2.
Then for each state q of Q2 and each symbol a
of find
2( q , a ) as follows:
Find ( {q} ), that is all the states that can be
reached from q by traversing arcs.
Then collect all the states that can be reached from each state of
( {q} ) by traversing one arc labeled with the symbol a.
The closure of the set of those states is
2( q , a ) .
The set of accepting states A2 is the same as A1 if
no accepting states can be reached from the initial state q1,0
through arcs in M1 .
Otherwise, that is if an accepting state can be reached from the initial state
q1,0
through arcs in M1 ,
then all the accepting states of M1 plus state q1,0
are the accepting states of M2 .
Example 1: Let us convert the following NFA-
to NFA.
The set of states Q2 of NFA is { 0, 1, 2, 3 ), the initial state is 0
and the accepting states are 1 and 0, since 1 is in
( { 0 } ) . The transition function
2 is obtained as follows:
2( 0 , a ):
First ( { 0 } ) = { 0 , 1 } .
Then from the transition function of the NFA-
1( 0 , a ) =
, and
1( 1 , a ) = { 1 , 2 }.
Hence 2( 0 , a ) =
( { 1 , 2 } ) = { 1 , 2 } .
For 2( 0 , b ) ,
since ( { 0 } ) = { 0 , 1 } and
1( 0 , b ) =
1( 1, b ) =
,
2( 0 , b ) =
.
Similarly 2 can be obtained for other states
and symbols. They are given in the table below together with
( { q } )
and
.
State q
| Input
| ( { q } )
|
| 2 ( q ,
) ( =
(
) )
|
0
| a
| { 0 , 1 }
| { 1 , 2 }
| { 1 , 2 }
|
0
| b
| { 0 , 1 }
|
|
|
1
| a
| { 1 }
| { 1 , 2 }
| { 1 , 2 }
|
1
| b
| { 1 }
|
|
|
2
| a
| { 2 }
|
| |
|
2
| b
| { 2 }
| { 3 }
| { 1 , 3 }
|
3
| a
| { 1 , 3 }
| { 1 , 2 }
| { 1 , 2 }
|
3
| b
| { 1 , 3 }
|
| |
|
The NFA thus obtained is shown below.
Example 2: Let us convert the following NFA-
to NFA.
The set of states Q2 of NFA is { 0, 1, 2, 3, 4 ), the initial state is 0
and the accepting states are 1 and 0, since 1 is in
( { 0 } ) . The transition function
2 is obtained as for Example 1.
2 is given in the table below together with
( { q } ) ,
1 ( p , )
and
State q
| Input
| ( { q } )
|
| 2 ( q ,
) ( =
(
) )
|
0
| a
| { 0 , 1 }
| { 1 , 2 }
| { 1 , 2 , 3 }
|
0
| b
| { 0 , 1 }
|
|
|
1
| a
| { 1 }
| { 1 , 2 }
| { 1 , 2 , 3 }
|
1
| b
| { 1 }
|
|
|
2
| a
| { 2 , 3 }
| { 4 }
| { 1 , 4 }
|
2
| b
| { 2 , 3 }
| { 4 }
| { 1 , 4 }
|
3
| a
| { 3 }
| { 4 }
| { 1 , 4 }
|
3
| b
| { 3 }
|
|
|
4
| a
| { 1 , 4 }
| { 1 , 2 }
| { 1 , 2 , 3 }
|
4
| b
| { 1 , 4 }
|
|
|
The NFA thus obtained is shown below.
Test Your Understanding of Conversion of NFA-
to NFA
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 NFA.
The following notations are used in the questions:
1 : \delta1
2 : \delta2
* : \delta^*
: \Lambda
Next -- Conversion of NFA to DFA
Back to Study Schedule
Back to Table of Contents