Finite Automata

Equivalence of DFAs, NFAs and NFA-s



Subjects to be Learned

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