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^{i}b^{i}c^{i}, 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^{2}wx^{2}y must also be in L.
Since v and x can't both be empty,
|uv^{2}wx^{2}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^{2}wx^{2}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.

Copyright © 1996 by David Matuszek

Last modified Mar 20, 1996