Pumping Lemma for Regular Languages: How to Prove a Language Is Not Regular

The pumping lemma is the standard tool for showing that a language is not regular. It turns the fact that a finite automaton has only finitely many states into a statement about long strings, and a proof then looks for a contradiction. The page belongs to the wider topic of formal languages and the Chomsky hierarchy.

What does the pumping lemma for regular languages say?

If L is a regular language, there is an integer p ≥ 1, the pumping length, that depends only on L. Every string w in L with |w| ≥ p can be written as w = xyz so that three conditions hold:

1. |y| ≥ 1, so the middle part is not empty.
2. |xy| ≤ p, so the middle part lies within the first p symbols.
3. x yⁱ z is in L for every i ≥ 0, so the middle part can be repeated any number of times, or deleted.

Course notes use other letters. The Cornell lecture notes, for example, write the pumping length as n and the three parts as u, v and w, with the repetition count named k. The statements are the same, and this page uses p, x, y and z.

The lemma speaks about languages recognized by a finite automaton, since those are the regular languages. In the language of an automaton, pumping y means running through a loop of the automaton zero, one or many times.

What is the pumping length?

The pumping length p is a property of the language, not of a particular string. It is at least 1, and it exists whenever the language is regular. One way to see where it comes from is to think of a DFA with n states for the language. A string with at least n symbols makes the automaton visit n + 1 states while it reads its first n symbols, so two of them must be the same state. The stretch between the two visits is a loop that can be traversed any number of times, and that loop is the middle part y.

In a proof the pumping length is an unknown. The prover may not pick a convenient value for p. The argument has to work for every p, because the lemma only promises that some p exists. The prover also does not get to pick the split of the string into x, y and z: the proof must handle every split that meets the conditions. What the prover does choose is the string w, and later the exponent i.

How do you prove a language is not regular with the pumping lemma?

The proof runs by contradiction.

1. Assume that the language L is regular. Then the lemma applies, and L has a pumping length p.
2. Choose a string w in L with |w| ≥ p. The choice may depend on p, and a good choice makes the next step easy.
3. Consider every split w = xyz with |y| ≥ 1 and |xy| ≤ p. The conditions limit where y can lie.
4. For each split, find an exponent i, possibly different for different splits, such that x yⁱ z is not in L.
5. This contradicts the lemma, which says that all pumped strings stay in L. The assumption was false, so L is not regular.

Step 3 is where the work happens. The condition |xy| ≤ p pins y to the beginning of the string, and a well-chosen w turns that into a strong restriction on what y can contain.

Worked example: aⁿbⁿ is not regular

Let L be the set of strings aⁿbⁿ for n ≥ 0: some a symbols followed by the same number of b symbols. Assume L is regular, and let p be its pumping length.

Choose w = a^pb^p. It is in L and has length 2p, which is at least p. Take any split w = xyz that satisfies |xy| ≤ p and |y| ≥ 1. Because w starts with p symbols a and xy lies within the first p symbols, both x and y consist only of a. So y = a^k for some k ≥ 1.

Now pump with i = 2. The string x y² z has k extra copies of a, so it equals a^p+kb^p. It has more a symbols than b symbols, and therefore it is not in L. This holds for every split, and the lemma says it cannot, so L is not regular.

The number of splits to consider is smaller than it first looks. Write x = a^s and y = a^t with t ≥ 1 and s + t ≤ p. For p = 1 to 8 this gives 1, 3, 6, 10, 15, 21, 28 and 36 splits, which is p(p+1)/2 in general. In none of them does the pumped string x y² z belong to L. That count is a check on the cases for small p; the argument for all p is the one in the paragraph above.

The same proof appears in the Cornell notes for the language of 0ⁿ1ⁿ, with x = 0ⁿ1ⁿ and k = 2. A course at Korea University proves the same statement with i = 0 instead, which deletes y and leaves fewer a than b.

Can the pumping lemma prove that a language is regular?

No. The lemma gives a necessary condition for regularity and not a sufficient one. If a language fails the condition, it is not regular. If it satisfies the condition, nothing follows, because some non-regular languages pass the test as well.

A standard counterexample is the language of strings aⁱb^jc^k where i = 0 or j = k. It satisfies the pumping conditions with p = 1: any nonempty string in it can be split with y equal to its first symbol and pumped any number of times without leaving the language. Yet the language is not regular. One way to see this is to intersect it with the regular language ab*c*. The intersection is the set of strings ab^jc^j, which is not regular, and regular languages are closed under intersection. The theorem of Myhill and Nerode gives the same result.

To show that a language is regular, build a finite automaton or a regular expression for it. A language such as aⁿbⁿ is context-free and not regular, and a grammar like the mixed one in the page on left-linear and right-linear grammars can generate it.

Where do pumping proofs usually go wrong?

• Picking the split. The decomposition is not the prover's choice. If a proof fixes one convenient y, it covers only that case, and the lemma allows any valid split.
• Ignoring |xy| ≤ p. This condition is what confines y to a known part of the string. Without it, y could lie anywhere in the string, including over the b symbols, and the argument above would fail.
• Choosing w without regard to p. The string must have length at least p and must be built from p, as in a^pb^p. A fixed string like aaabbb does not work for every p.
• Fixing i in advance. The exponent may be chosen after the split is known. For aⁿbⁿ, i = 2 works and so does i = 0, but for other languages no single exponent works for every split. For the strings of a whose length is a prime number, checks for p from 4 to 15 found splits for which both i = 0 and i = 2 give a prime length again.
• Reading a passed test as proof of regularity. Passing shows nothing.