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, |uv| £ k , show:
there exists m ³ 0 such that uvmw Ï L
from the pumping lemma,   uvmw Î L
contradiction
false assumption
Therefore,
L is not regular
7/26