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.

Basis Step: For any symbol a in we are going to show that
1*( q , a ) = 2*( q , a ) .

By the definition of * for NFA (see the frame at right)
2*( q , a ) =
Since 2*(q, ) = { q } , 2*( q , a ) = 2( q , a ) .
But 2( q , a ) = 1*( q , a ) because of the way NFA is constructed from NFA- (see the frame at right).
Hence 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,

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

2*( q , wa ) =
=
= since 2( q , a ) = 1*( q , a ) by the way NFA is constructed from NFA- .
By the definition of 1* , it is equal to

= as proven below in Claim 3,
= since 1*(q,w) is already a -closure, all r in ({p}) for any p in 1*(q,w) are in 1*(q,w) .
= 1*( q , wa ) by the definition of 1* .

Hence 2*( q , wa ) = = 1*( 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