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