Pumping Lemma: Example
1/2
Prove that L = {anbncn : n ³ 1} is not CFL.
1) Assume that L is a CFL. Let k ³ 1 be
the pumping
lemma constant for L.
2) Let z = akbkck: akbkck Î L, |z| = |akbkck| = 3k ³ k
3) All
decompositions of z into uvwxy; vx ¹ ε, |vwx| £ k:
aaaaa…aabb…bb…bbcc…ccccc
k k k
a) vwx Î {a}*{b}*,
vx ¹ e
b) vwx Î
{b}*{c}*,
vx ¹ e
16/31