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