Pumping Lemma for Regular Languages

Regular languages

Regular languages are those languages that can be accepted by deterministic finite automata (DFA) or nondeterministic finite automata (NFA). They can also be described by regular expressions. Regular languages form an important class of languages in the theory of computation.

Not every language is regular. Common examples of non-regular languages are:

• L = {aⁿbⁿ | n = 0, 1, 2, ...}.
• L = {aⁿ b aⁿ | n = 0, 1, 2, ...}.
• L = {aⁿ bⁿ a a bⁿ+1 | n = 1, 2, 3, ...}.

A standard technique to show that a language is not regular is the Pumping Lemma for Regular Languages. The lemma gives a necessary condition that every regular language must satisfy; it is most often used in proofs by contradiction to show non-regularity.

The Pumping Lemma for Regular Languages

Formal statement. Let L be a regular language. Then there exists an integer p ≥ 1 (called the pumping length) such that for every string w in L with |w| ≥ p, we can write w = xyz satisfying the following three conditions:

• |y| > 0.
• |xy| ≤ p.
• For all i ≥ 0, the string x yⁱ z belongs to L.

Interpretation. For any sufficiently long string w in a regular language L, there is a substring y that occurs within the first p symbols of w and that can be repeated or removed any number of times while keeping the resulting string inside L. We say that y can be "pumped".

Remark. The pumping lemma is a necessary condition for regularity: every regular language satisfies it. It is not a sufficient condition: a language satisfying the pumping property for a particular p is not guaranteed to be regular in general.

How the lemma is used

To prove that a language L is not regular, the typical strategy is a proof by contradiction using the pumping lemma. The steps are:

1. Assume L is regular. Let p be the pumping length given by the lemma.
2. Choose a specific string w ∈ L with |w| ≥ p, chosen carefully so that information about the beginning of the string helps derive a contradiction.
3. By the pumping lemma, write w = x y z with |y| > 0 and |xy| ≤ p.
4. Show there exists an integer i ≥ 0 such that x yⁱ z ∉ L, contradicting the lemma. Hence L is not regular.

Two remarks about the choice of w and the argument in the final step:

• Choose w so that the constraint |xy| ≤ p forces y to lie in a particular, controlled region of w (for example, entirely in the block of a's in a string of the form aⁿbⁿ).
• In the final step you typically choose i = 0 (remove y) or some other i (repeat y), and then argue using length or the structural properties of strings in L to show x yⁱ z cannot belong to L.

Proof of the Pumping Lemma

Proof (sketch using DFA and the pigeonhole principle).

Since L is regular, there exists a DFA M that recognises L. Let n be the number of states of M.

Consider any string w ∈ L with |w| ≥ n. Let the symbols of w be a₁, a₂, ..., a_m, where m ≥ n.

When M processes w from the start state, it visits a sequence of states P₀, P₁, P₂, ..., P_m, where P₀ is the start state and P_k is the state after reading a₁ ... a_k.

There are m + 1 ≥ n + 1 visited states but only n distinct states in the DFA. By the pigeonhole principle, two of these visited states must be the same: there exist indices i and j with 0 ≤ i < j="" ≤="" n="" such="" that="" />_i = P_j.

Now split the string w into three parts as follows.

x = a₁a₂ ... a_i.

y = a_i+1 a_i+2 ... a_j.

z = a_j+1 a_j+2 ... a_m.

The following observations follow directly from construction:

• x may be empty if i = 0.
• y cannot be empty because j > i, so |y| > 0.
• |xy| = j ≤ n, so |xy| ≤ n (that is, y lies within the first n symbols of w).

Because P_i = P_j, reading y from state P_i returns to the same state P_i. Therefore, for any i ≥ 0, reading y repeated i times still returns to P_i, and then reading z leads to an accepting state (because the original x y z = w was accepted). Thus x yⁱ z is accepted for every i ≥ 0 and hence belongs to L.

Examples and applications

Example 1: The language {aⁿ | n ≥ 1} is regular

The language consists of strings of one or more a's: {a, aa, aaa, aaaa, ...}.

A simple DFA with one loop on state q₁ accepts any number of a's and demonstrates regularity. The pumping lemma is satisfied for this language: choose a pumping length p; take any w = a^m with m ≥ p, and let y be a substring of some a's within the first p symbols. Pumping y just changes the number of a's and every result remains of the form a^k, hence stays in the language.

Example 2: The language {aⁿ b^m | n, m ≥ 1} is regular

This is the set of strings that consist of one or more a's followed by one or more b's. A DFA that loops on a's and then switches to a loop on b's recognises this language.

The pumping lemma is satisfied: for any string w in the language with |w| ≥ p, the substring y that lies within the first p positions consists only of a's. Pumping y changes the number of a's but the overall shape "some a's then some b's" remains, so every pumped string is still in the language.

Example 3: The language {aⁿ bⁿ | n ≥ 1} is not regular

The set contains strings with the same number of a's followed by the same number of b's, for example {ab, aabb, aaabbb, ...}.

Proof (by pumping lemma).

Assume for contradiction that L is regular. Let p be the pumping length.

Choose w = a^p b^p. Then |w| = 2p ≥ p, so the lemma applies and we can write w = x y z with |y| > 0 and |xy| ≤ p.

Because |xy| ≤ p, the substring y consists only of a's. There are three possible forms for y:

• y contains only a's. Then choose i = 0. The pumped string x z has fewer a's than b's, so x z ∉ L.
• y contains only b's. This cannot happen here because |xy| ≤ p ensures y lies within the a block.
• y contains both a's and b's. This cannot occur either because |xy| ≤ p forces y to lie entirely in the a block.

Thus in all actual possibilities for this choice of w, pumping produces a string not in L, contradicting the pumping lemma. Hence L is not regular.

Example 4: The language {0ⁱ 1ⁱ | i ≥ 1} is not regular

Proof (by pumping lemma).

Assume L is regular and let p be the pumping length.

Choose w = 0^p 1^p. Then |w| = 2p ≥ p, so w = x y z with |y| > 0 and |xy| ≤ p.

Because |xy| ≤ p, the substring y consists only of 0's. Take i = 0. Then x z has fewer 0's than 1's, so x z ∉ L. This contradicts the pumping lemma, hence L is not regular.

Example 5: The language {a^i² | i ≥ 1} (perfect squares) is not regular

Correcting the notation: L = { a^i² | i ≥ 1 }.

Proof (sketch using the pumping lemma).

Assume L is regular and let p be the pumping length.

Choose w = a^p². Then |w| = p² ≥ p, so w = x y z with |y| > 0 and |xy| ≤ p.

Because |xy| ≤ p, the substring y lies among the first p a's. Thus y = a^k for some k ≥ 1 and k ≤ p.

If we pump with i = 0 then the length becomes p² - k, which is not necessarily a perfect square; but to make a sure contradiction choose i = p+1. The resulting string has length p² + p·k = p(p + k), which is divisible by p and hence composite (not a perfect square of an integer unless p + k = p, impossible). Therefore x y^p+1 z ∉ L. This contradicts the pumping lemma, so L is not regular.

Example 6: The language {a^p | p is prime} is not regular

Proof (by pumping lemma with a simple number-theoretic choice).

Assume the language of prime-length a-strings is regular. Let p be the pumping length.

Choose a prime number q > p and consider w = a^q ∈ L. By the pumping lemma write w = x y z with |y| > 0 and |xy| ≤ p.

Since |xy| ≤ p < q,="" y="" />^k for some k ≥ 1.

Now pump with i = q + 1. The new length is q + q·k = q(1 + k), which is composite because it has q as a factor and 1 + k > 1. Therefore x y^q+1 z ∉ L. This contradicts the pumping lemma. Hence the language of prime-length a-strings is not regular.

Example 7: The language {ww | w ∈ {a,b}*} is not regular

This language contains all strings that are the concatenation of a string with itself, for example aa, abab, aab aab, etc.

Proof (by pumping lemma).

Assume L = {ww | w ∈ {a,b}*} is regular and let p be the pumping length.

Consider the particular string s = a^p b a^p b. This string is of the form ww with w = a^p b.

We have |s| = 2(p + 1) ≥ p, so by the lemma s = x y z with |y| > 0 and |xy| ≤ p. Because |xy| ≤ p, the substring y lies entirely inside the first block of a's.

If we pump with i = 0 we remove some a's from the first half but not from the second half. The resulting string will no longer be of the form uu (the two halves will be different), hence x z ∉ L. This contradicts the pumping lemma. Therefore L is not regular.

Comments and common pitfalls

• When applying the pumping lemma for a contradiction, the opponent chooses the decomposition x y z subject to the constraints; you must show that for every possible decomposition satisfying |y| > 0 and |xy| ≤ p there is some i with x yⁱ z ∉ L.
• Choose the witness string w carefully so that the restriction |xy| ≤ p forces y to lie in a region where pumping changes a property that characterises L (for example, the number of symbols in a block).
• Remember that the lemma gives existence of p and then for every w with |w| ≥ p there exists a decomposition. You cannot choose the decomposition; you must argue about all possible decompositions that meet the constraints.
• The pumping lemma cannot be used directly to prove a language is regular. It can only be used to show non-regularity. To prove regularity, construct a DFA/NFA or a regular expression.

Summary

The pumping lemma for regular languages is a fundamental tool to prove that a given language is not regular. It formalises the intuitive idea that a finite-state automaton has only finitely many states, so when processing sufficiently long strings some part of the computation must repeat. Using this repetition one shows that pumping (repeating or removing) a substring leads to strings that must still be accepted by any DFA for a regular language; if this contradicts the structure of the candidate language, the language is not regular.