[Overview] [Previous] [Next]

Using the Pumping Lemma

The pumping lemma can be used to show that certain languages are not context free. As an example, we will show that the language L = {aⁱbⁱcⁱ: i > 0} is not context-free.

Suppose L is context-free. If string X L, where |X| > m, it follows that X=uvwxy, where |vwx| m. Choose a value for i that is greater than m. Then, wherever vwx occurs in the string aⁱbⁱcⁱ, it cannot contain more than two distinct letters--it can be all a's, all b's, all c's, or it can be a's and b's, or it can be b's and c's. Thus the string vx cannot contain more than two distinct letters; but by the pumping lemma, it cannot be empty, either, so it must contain at least one letter.

Now we are ready to "pump." Since uvwxy is in L, uv²wx²y must also be in L. Since v and x can't both be empty, |uv²wx²y| > |uvwxy|, so we have added letters. But since vx does not contain all three distinct letters, we cannot have added the same number of each letter. Thus uv²wx²y cannot be in L.

We have arrived at a contradiction. Therefore our original assumption, that L is context free, must be false. Q.E.D.