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