Finite Automata

Proof of Equivalence of NFA- and NFA



We are going to prove that the NFA obtained from NFA- by the conversion algorithm accepts the same language as the NFA- .
NFA- that recognizes a language L is denoted by M1 = < Q1 , , q1,0 , 1 , A1 > and NFA obtained by the conversion is denoted by M2 = < Q2, , q2,0 , 2 , A2 >

First we are going to prove that 1*( q , w ) = 2*( q , w ) for any non-empty string w.

To review the definition of * for NFA, and NFA-, and the conversion of NFA- to NFA click here.

When it is proven, it implies that NFA- M1 and NFA M2 accept the same non-empty strings. The case when w is an empty string is going to be proven separately.

Claim 1: For any non-empty string w and for any state q,
1*( q , w ) = 2*( q , w ) .

Proof: This is going to be proven by induction on w. Recall that the set of strings is defined recursively (click here for a quick review). Thus we first prove that it is true for any arbitrary symbol, then assuming it holds for any arbitrary string w we prove it for any of the children of w, that is wa for any symbol a in the alphabet.

Basis Step: We need to show that for any symbol a in
                1*( q , a ) = 2*( q , a ) .
We are going to prove it by showing that both of them are equal to 2( q , a ) .

Firstly 2( q , a ) = 1*( q , a ) --- (1)
because of the way NFA is constructed from NFA- (click here for a review) .

Secondly 2*( q , a ) = 2*(q , a ) =
by the definition of 2* for NFA (click here for a review) . .
Since 2*(q , ) = { q } , = = 2( q , a ) .
Hence 2*( q , a ) = 2( q , a ) . --- (2)

Hence from (1) and (2),
1*( q , a ) = 2*( q , a ) .

Inductive Step: We need to show that if 1*( q , w ) = 2*( q , w ) for an arbitrary string w (Induction Hypothesis),

then 1*( q , wa ) = 2*( q , wa ) holds for any arbitrary symbol a in .

First we show that 2*( q , wa ) = --- (1)
using the definition of 2*, the induction hypothesis and the construction of NFA from NFA-.
Then we show that = 1*( q , wa ) --- (2)
basically using the definition of 1*.
Then from (1) and (2) we can see that 1*( q , wa ) = 2*( q , wa ) .

Let us first prove (1).
By the definition of 2*
            2*( q , wa ) =
Since 2*( q , w ) = 1*( q , w ) by the induction hypothesis,
            =
Since 2( q , a ) = 1*( q , a ) by the way NFA is constructed from NFA- .
            =
Hence 2*( q , wa ) = , that is (1) has been proven.

Let us next prove (2), that is = 1*( q , wa ) .
By the definition of 1* for NFA-,
            1*( p , a ) =
Substituting this into the left hand side of (2) produces
            = .
The right hand side of this equality is equal to
            ( the first and have been swapped to get this) ,
as proven below in Claim 3,

This can be shown to be equal to , because = .
To see an explanation for this click here.

Hence = .
On the other hand = 1*( q , wa ) , by the definition of 1* .
Hence = 1*( q , wa ) .
Hence we have proven (2).
Thus from (1) and (2) 1*( q , wa ) = 2*( q , wa ) .

End of Induction

With this Claim 1 we can see that any non-empty string w is accepted by NFA if and only if it is accepted by the corresponding NFA- .
As for the empty string , if it is accepted by an NFA-, then ( { q10 } ) A1 . Hence by the way A2 is constructed, q20 A2 . Hence is accepted by NFA.
Conversely if is accepted by NFA, then q20 A2 . By the way NFA is constructed from NFA- this means that ( { q10 } ) A1 . Hence is accepted by NFA- .

Thus NFA- and the corresponding NFA accept the same language.


As a preparation for the proof of commutativity of union and -closure operations, let us prove the following claim.

Claim 2: ( S T ) = ( S ) ( T ) .

We are going to prove this in two parts:

( S T ) ( S ) ( T )   and
( S ) ( T ) ( S T ) .

Part 1 : ( S T ) ( S ) ( T )
This is going to be proven by induction on ( S T ) .
For that let us restate the statement so that the induction becomes clearer.
What Part 1 states is that all the elements of ( S T ) have the property of being in the set ( S ) ( T ) .
Since ( S T ) is defined recursively, in the Basis Step of our proof we prove the property for the elements of the basis of ( S T ) and in the Inductive Step we prove that if an arbitrary element of ( S T ) has that property, then its childen also have it.
Let us review the definition of the -closure of the set of states of an NFA- . Let X be the set of states of an NFA-. Then the -closure of X is defined recursively as

Basis Clause: X ( X ) .
Inductive Clause: If q ( X ) , then ( q , ) ( X ) .
Extremal Clause: Nothng is in ( X ) unless it is obtained by the Basis and Inductive Clauses.

Proof of Part 1:
Basis Step: We need to prove that ( S T ) ( S ) ( T ) .
Since S ( S ) and T ( T ) , S and T are subsets of ( S ) ( T ) . Hence ( S T ) ( S ) ( T ) .

Inductive Step: We need to prove that if q is an arbitrary element of ( S T ) with the property of being in ( S ) ( T ) , then ( q , ) ( S ) ( T ) .

Let q be an arbitrary element of ( S T ) with the property of being in ( S ) ( T ) .
Since q ( S ) ( T ) , q ( S ) or q ( T ) .
If q ( S ) , then ( q , ) ( S ) by the definition of ( S ) . Hence ( q , ) ( S ) ( T ) .
Similarly if q ( T ) , then ( q , ) ( S ) ( T ) .
Hence if q is an arbitrary element of ( S T ) with the property of being in ( S ) ( T ) , then ( q , ) ( S ) ( T ) .

Thus all the elements of ( S T ) have the property of being in ( S ) ( T ) which is to say that ( S T ) ( S ) ( T ) .
End of Proof for Part 1


Part 2 : ( S ) ( T ) ( S T ) .
Proof of Part 2: We are going to prove ( S ) ( S T ) and ( T ) ( S T ) . That would imply that ( S ) ( T ) ( S T ) .

Proof of ( S ) ( S T ) :
By induction on ( S ) .
Basis Step: We need to show that S ( S T ) .
Since S ( S T ) , and ( S T ) ( S T ) , S ( S T ) .
Inductive Step: We need to prove that for an arbitrary element q in ( S ) , if q is in ( S T ) , then ( q , ) ( S T ) .

Since q is in ( S T ) and since ( S T ) is a -closure, by the definition of -closure ( q , ) ( S T ) .

Thus ( S ) ( S T ) has been proven.

Similarly ( T ) ( S T ) holds.
Hence ( S ) ( T ) ( S T ) holds.
End of Proof of Part 2
End of Proof of Claim 2

Claim 3: ( Si ) = ( Si ) .
Proof : Proof by induction on n.
Basis Step: n = 1. If n = 1, then ( Si ) = ( S1 ) and
( Si ) = ( S1 ) .
Hence ( Si ) = ( Si ) holds for n = 1.
Inductive Step: Assume that ( Si ) = ( Si ) holds for n. --- Inducion Hypothesis
( Si ) = ( ( Si ) ) ( Sn+1 ) by the definition of union.
= ( Si ) ( Sn+1 ) by the induction hypothesis.
= ( ( Si ) Sn+1 ) by Claim 2 above, since Si   is a set as well as Sn+1.
= ( Si ) by the definition of union.
End of Proof for Claim 3



Test Your Understanding of Proof of Equivalence of NFA and 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.

The following notations are used in the questions:

   : \delta        : \Lambda        : \Sigma     *   : \Sigma^*        : \cup








Next -- Kleene's Theorem --- Part 1

Back to Study Schedule

Back to Table of Contents