Pumping Lemma: Application I
•
Based on the pumping lemma, we often make a proof by
contradiction to demonstrate that a language is
not
regular
Assume
that
L
is regular
Consider the PL constant
k
and select
z
Î
L
, whose
length depends on
k
so
|z|
³
k
is surely true.
For
all
decompositions of
z
into
uvw
,
v
¹
e
,
|
u
v
|
£
k
, show
:
there exists
m
³
0 such that
uv
m
w
Ï
L
from the
pumping lemma,
uv
m
w
Î
L
contradiction
false
assumption
Therefore,
L
is not regular
7
/26