Pumping Lemma Proof Template

Pumping Lemma proofs have a very standard outline. It's almost always better to follow the standard outline, rather than trying to improvise directly from the statement of the theorem.

Recall that the pumping-lemma states that for any regular language L, there exists a number p such that for any string w in L of length at least p there are strings x,y,z such that

  1. w = xyz
  2. |xy| <= p
  3. |y| >= 1
  4. For all i, xyiz is in L

To prove that a language L is not regular, we show that the pumping lemma fails. That is, we show that

For any number p, there exists a string wp in L of length at least p such that if we choose any strings x,y,and z satisfying conditions (1)-(3), then there is some number i such that xyiz is not in L.

So, a pumping lemma proof normally looks something like this (just fill in the blanks)

Suppose L were regular. Let p be the pumping length given by the pumping lemma.

Consider the string wp = (insert here some description of a string, parametrized by p)

Clearly, |wp| >= p and wp is in L. So, by the pumping lemma, there must be some choice of x,y,z satisfying the conditions of the pumping lemma.

But, consider any choice of x,y,z for which wp = xyz, |xy| <= p, and |y| >= 1.

[Insert argument as to why for some particular i, xyiz is not in L; usually i=0 or i=2 works. Using the fact that |xy| <= p, you know that y must be in the first p characters of the string wp.. Using this, you can usually restrict the cases for what y can be, and argue for each of the cases that xyiz is not in L.] Since xyiz is not in L, we get a contraditiction; hence the assumption that L is regular is false. Hence L is not regular. QED

Several points to note