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