Pumping Lemmas, Marked Positions, and the Limits of Counting Arguments

Every proof that a language is not regular has the same shape: assume an automaton with n states exists, choose a string long enough that some state must repeat, and derive a contradiction by pumping the loop between the repeats. The pumping lemma packages that argument. It is a necessary condition for regularity and it is not sufficient, and the gap between those two facts is where most incorrect proofs live.

The lemma and its quantifiers

For every regular language L there exists a pumping length p such that every string w ∈ L with |w| ≥ p can be written w = xyz with

1. |y| ≥ 1,
2. |xy| ≤ p,
3. for all i ≥ 0, xyⁱz ∈ L.

The proof is three lines. Take a DFA for L with p states, run it on w, and observe that the first p+1 states visited include a repeat by pigeonhole. Split w at the first repeat: x is the prefix before the repeated state, y is the loop, z is the rest. The loop can be traversed any number of times, including zero, so xyⁱz is accepted for every i. Condition |xy| ≤ p holds because the repeat occurs within the first p symbols, which is why the decomposition is confined to a prefix.

The quantifier structure is what makes the lemma usable and what makes it easy to misuse. To prove a language is not regular, one must show that for every p there exists a w of length at least p such that every decomposition satisfying (1) and (2) fails (3). The two universal quantifiers are the hard part: choosing one convenient decomposition and showing it can be pumped proves nothing, and choosing one string that happens to fail for one p proves nothing either.

A worked non-regularity proof

Take L = {aⁿbⁿ : n ≥ 0}. Assume p is the pumping length and choose w = aᵖbᵖ, which has length 2p ≥ p. Any decomposition with |xy| ≤ p and |y| ≥ 1 places y entirely inside the a-block, since the first p symbols are all a’s. So y = aᵏ for some k ≥ 1, and xy²z = a^{p+k}bᵖ, which has unequal counts and is not in L. The contradiction is complete because the choice of decomposition was arbitrary within the constraint.

The same template handles {w : w has equally many a’s and b’s}, {aⁿ : n is a perfect square}, and {aⁿbⁿcⁿ}. The last one is worth doing carefully: with w = aᵖbᵖcᵖ, the constraint |xy| ≤ p still confines y to the a-block, so pumping changes only the count of a’s. The proof does not need to consider any other case, and that is a feature of choosing the string so that the a-block is longer than p.

For {aⁿ : n is prime}, the argument needs arithmetic rather than counting. With w = aᵖ where p is a prime at least the pumping length, y = aᵏ for some k with 1 ≤ k ≤ p, and xyⁱz = a^{p−k+ik}. Taking i = p + 1 gives exponent p − k + (p+1)k = p(k+1), composite for every k ≥ 1 and p ≥ 2. One pump suffices, and the constraint |xy| ≤ p is what lets the exponent be computed from p and k alone.

Why the converse fails

The pumping lemma is necessary, not sufficient. There exist non-regular languages that satisfy it, and the standard example is built by adjoining a non-regular set to a regular one:

L = { aⁱbʲcᵏ : i, j, k ≥ 0 and i = 1 implies j = k }

The strings with i ≠ 1 form a regular set. Intersecting L with the regular set of one a followed by any number of b’s and then any number of c’s leaves exactly {a bⁿcⁿ : n ≥ 0}, which is not regular; a regular L would have a regular intersection with that set, so L is not regular either. It nevertheless satisfies the pumping lemma with p = 2, and the decomposition depends on the string. A string with i = 0 is unchanged in its membership by pumping its first symbol, because the implication is vacuous for every i ≠ 1. A string with even i ≥ 2 is pumped with y = aa, which keeps the count of a’s even and therefore never at 1; a string with odd i ≥ 3 is pumped with x = a and y = a, so the count drops to i − 1 at t = 0 and rises afterwards, again never reaching 1. A string with i = 1 has the form a bⁿcⁿ, and pumping the leading a keeps it in L: the count of a’s becomes 0, 1, or at least 2, and the only case that imposes a condition is i = 1, where j = k still holds.

The lesson is procedural: a pumping-lemma argument can only ever prove non-regularity, never regularity. A language that survives the lemma is not thereby regular; the only way to prove regularity is to exhibit an automaton, a regular expression, or a right-linear grammar, as Right-Linear Grammars and the Limits of One-Way Derivation describes.

Ogden’s lemma marks the positions that matter

Ogden’s lemma generalises the argument by allowing the proof to designate positions in the chosen string. For every context-free language L there exists p such that for every w ∈ L with at least p marked positions, there is a decomposition w = uvxyz with

1. vx contains at least one marked position,
2. vxy contains at most p marked positions,
3. for all i ≥ 0, uvⁱxyⁱz ∈ L.

Setting every position marked recovers the ordinary pumping lemma for context-free languages, in which the pumped pair is vx and the constraint says that |vxy| ≤ p. The strengthening matters because marking lets the proof ignore irrelevant parts of the string. For {aⁿbⁿcⁿ}, mark all the a’s and all the c’s. Then vx must contain a marked symbol, so it lies in the a-block or the c-block or spans both, and pumping changes the count in one block without changing the b-block. The case analysis is shorter and the argument does not have to reason about pumpings confined to b’s, which would be harmless.

The lemma is also the tool for proving inherent ambiguity, a use Ogden introduced. A grammar is inherently ambiguous when every grammar for its language is ambiguous. The standard witness is {aⁱbʲcᵏ : i = j or j = k}. A proof via Ogden’s lemma shows that any grammar must have two distinct parse trees for some string in the language, because a single parse tree cannot simultaneously enforce i = j and j = k with only one stack. The two constraints require the derivation to commit to one equality at the point where the other becomes checkable, and the commitment can be made in two incompatible ways.

The lemma is an approximation, and the approximation has a shape

The pumping lemma describes regular languages as those where every sufficiently long string contains a short loop. That is a necessary condition derived from a counting argument over states. It is not a characterisation because a language can have short loops everywhere and still be non-regular — the loops exist but no finite automaton can track which of them is currently relevant.

The Myhill–Nerode theorem gives the exact characterisation: L is regular if and only if the relation u ≡_L v, defined by “for all w, uw ∈ L iff vw ∈ L”, has finitely many equivalence classes. The number of classes is the number of states in the minimal DFA, so the theorem is both a decision procedure and a minimality proof. For {aⁿbⁿ}, the strings aᵏ are pairwise inequivalent because aᵏbᵏ ∈ L while aʲbᵏ ∉ L for j ≠ k, so there are infinitely many classes. This argument is usually shorter than a pumping argument and always gives more information.

The relation between the two results is worth stating precisely. Myhill–Nerode implies the pumping lemma: a finite quotient with p classes means any string of length p or more visits some class twice, and the segment between the visits can be deleted or repeated. The converse implication fails, which is exactly the non-sufficiency above. Ogden’s lemma stands in the same relation to the context-free case, where no exact analogue of Myhill–Nerode is available, because the equivalence question for context-free grammars is undecidable, as Ambiguity, Equivalence, and Other Undecidable Grammar Questions explains.

Writing the argument as a checkable script

The mechanical part of a pumping proof — enumerating all decompositions for a candidate string and confirming each one fails — is short enough to automate, and doing so catches the common error of considering only one split:

def pumpable_examples(lang_pred, p, w):
    """Return decompositions x,y,z with |xy| <= p, |y| >= 1, that survive
    pumping for i in {0, 2}. A language that has no survivors for every
    pumping length p is not regular, by the contrapositive of the lemma."""
    survivors = []
    for cut in range(1, min(p, len(w)) + 1):      # end of xy
        for ylen in range(1, cut + 1):           # |y| >= 1
            x, y, z = w[:cut - ylen], w[cut - ylen:cut], w[cut:]
            if all(lang_pred(x + y * i + z) for i in (0, 2)):
                survivors.append((x, y, z))
    return survivors

L = lambda s: (lambda a, b: a == b)(s.count('a'), s.count('b'))
print(pumpable_examples(L, 3, 'aaabbb'))   # [] for this witness

Testing i ∈ {0, 2} is sufficient in practice because most witnesses fail at those two values, but a complete proof must handle every i, and a script that returns a nonempty list has proved nothing — it has only failed to find a counterexample for that particular w and that particular p. The asymmetry is the lemma’s, not the script’s.

The final caution is about the choice of witness. The string must be long enough that the constraint |xy| ≤ p bites: a witness shorter than p is not subject to the lemma at all, and a witness whose first p symbols are not the part that must be pumped forces a longer case analysis. Choosing a witness where the first p symbols are homogeneous — all a’s, or all copies of one symbol — is not a trick but the standard way to make the quantifier over decompositions collapse to a single case.