[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 = {aibici: i > 0} is not context-free.

Suppose L is context-free. If string X is a member of 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 aibici, 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, uv2wx2y must also be in L. Since v and x can't both be empty, |uv2wx2y| > |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 uv2wx2y 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.


Copyright 1996 by David Matuszek
Last modified Mar 20, 1996