Pumping Lemma

Proof.  We prove the theorem by using the pumping lemma. Let the demon pick a k. Now we pick a word z = a^2kb^2k. Suppose the demon divides the word like this:
u = a,   v = a,   w = a,   x = a,   y = a^2k-4b^2k.
Clearly, z = uvwxy, |vwx|≤k. Since uv²wx²y = a^2k+2b^2k doesn't belong to L, it follows from the pumping lemma that L is not a context free language.

But it is very easy to show that L is context free! In fact, you have seen a CF grammar for L in the lecture. So what's wrong with the proof?

The problem is that you have to show that for any choice of cutting z into u, v, w, x and y, there is some i such that uvⁱwxⁱy is not in L. In this case it isn't quite true, because for every z from L, |z|\gt; 1 there is a choice of u, v, w, x and y such that uvⁱwxⁱy is in L for any i. For z = aⁿbⁿ, the demon simply picks u = a^n-1, v = a, w = epsilon, x = b and y = b^n-1.