Pumping Lemma: Application
• Based on the pumping lemma for CFL, we often make a proof by contradiction to demonstrate that a language is not a CFL.
Assume that L is a CFL.
    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 uvwxy: vx ¹ ε, |vwx| £ k, show that
there exists m ³ 0 such that uvmwxmy Ï L;
from the pumping lemma,   uvmwxmy Î L
contradiction
false assumption
Therefore,
L is not a CFL
15/31