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

- w = xyz
- |xy| <= p
- |y| >= 1
- For all i, xy
^{i}z 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 w_{p}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 xy^{i}z 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 w

_{p}= (insert here some description of a string, parametrized by p)Clearly, |w

_{p}| >= p and w_{p}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

anychoice of x,y,z for which w_{p}= xyz, |xy| <= p, and |y| >= 1.[Insert argument as to why for some particular i, xy

^{i}z 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 w_{p}.. Using this, you can usually restrict the cases for what y can be, and argue for each of the cases that xy^{i}z is not in L.] Since xy^{i}z 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

- Note that your proof shows for an arbitrary p, there is a particular
string w
_{p}in L (long enough) such that for *any* split of w_{p}=xyz (satisfying the conditions), there is an i such that xy^{i}z is not in L. So you must assume a general p, construct a concrete w_{p}, consider a general split x,y,z, and show a particular i for which the pumped word is not in L. You cannot choose a particular p (like p=2)! You cannot choose a particular split x,y,z! - The string w
_{p}must change as p changes, e.g. portions of it should get longer and shorter. - The string w
_{p}does not need to be a random, representative member of L. It may come from a very specific subset of L. For example, if your language is all strings with equal numbers of 0's and 1's, your w_{p}might be O^{p}1^{p}. - Make sure your string w
_{p}is long enough, so that the first p characters have a very limited form (e.g. all zeros). - It's important to check that
|w
_{p}| >= p and that w_{p}is in L. And your proof should mention these facts. However, they don't normally need any justification, e.g. the use of "Clearly" in the above template. - When you assert that x,y, and z must exist, it would normally be good mathematical style to quote the specific conditions they must satisfy. But everyone knows what these conditions are, so it's common to just say they satisfy "the conditions from the pumping lemma."
- You should, however, know clearly in your own mind what those numbered conditions were.
- In the variable part at the end of the proof, be sure
that you explicitly use the facts that
|xy| <= p and |y| >= 1, when you argue that xz or xyyz (or
xy
^{i}z for some other value of i) does not have the right form to be in L. - Exception: when the alphabet has only one character (e.g. the language contains all strings of zeros that have prime length), you may not need to use the fact that |xy| < p.
- The vast majority of proofs use i = 0 or i = 2, but there are exceptions.