Pumping Lemma Game – Prove a Language Is Not Regular or Not Context-Free

1The language

2The adversary picks p

You don't choose p, so your s has to work for every p. Here p is between 3 and 10.

3You pick s

4You pick i

Pump with i =

This i is used for every case. You can change it for a single case on the right.

The adversary splits s

The pumping lemma as a game

A pumping lemma proof is a game against an adversary. The adversary picks the pumping length p, you pick a string s in the language, the adversary splits s any way the lemma allows, and you pick how many times to pump. If you can always pump s out of the language, the language is not regular (Sipser, Theorem 1.70) or not context-free (Theorem 2.34).

Writing s

Type	Means
`0^p1^p`	0^p1^p
`0^(p+1)1^p`	0^p+11^p
`1^(p^2)`	1^p²
`(01)^p`	01 repeated p times
`a^pb^pc^p`	a^pb^pc^p

A plain string such as 0011 works too, but a proof needs s to grow with p.

How the page checks your proof

It lists every split the lemma allows for the current p and groups them into cases, such as “y has only 0s”.
For each case, it pumps every split with your i and checks whether the result leaves L.
If one split can't be pumped out of L by any i, the adversary wins with that split, and your s cannot work.
When every case is covered, check every p from 3 to 10 and read the proof outline.

Good to know

i = 0 (“pumping down”) is allowed and is sometimes the only choice that works, as in Sipser's Example 1.77.
Some languages here are regular or context-free. For those the adversary always wins: the lemma really holds for them.
Passing the pumping test does not prove that a language is regular or context-free.