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
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