Note on Use of Pumping Lemma
•
Pumping lemma:
L
is regular
if
exist
k
³
0 and ...
then
L
is regular
exist
k
³
0 and ...
if
then
•
However, the next implication is
incorrect
:
•
We
cannot
use the pumping lemma to
prove that
L
is regular.
Main application of the pumping lemma:
•
proof by contradiction that
L
is
not
regular.
9
/26