2.3 Pumping Lemma for CFL

Definition of Pumping Lemma

Let be a context-free language. Then there is a constant so that if and then can be decomposed into 5 parts: . so that:

An non-CFL to prove that cannot be pumped

Suppose it is context free. Let p be its pumping constant. Let be a string longer than p and in the language. Suppose we have a decomposition , where , so cannot include all three letters because it is too short.

then we pumped the string to , which cannot be in the language. Because the letter that cannot be covered in cannot get repeated then there is less numbers of it in the new string.

So is not in the language, which contradicted to the pumping lemma.

An non-CFL that can be pumped

L is not CFL

Suppose L is context free. We know that is a regular language R. Then the intersection should also be context-free. However, , which is not context-free. Contradiction.

L can be pumped

First of all, and are regular languages, so all strings in them can be pumped.

Let p be the pumping constant of , , no matter what the value of is, the pumped string can belong to , which is still in L. So L is pumpable.