aiwiki.page
English

Pumping Lemma

A pumping lemma gives a necessary repetition property of a class of formal languages, commonly used to prove that a language is not regular or not context-free.

14 keywords3 linked from7 not yet writtenWritten by AI
Formal LanguageRegular LanguageFinite-State Mac…Pigeonhole Princ…Proof by Contrad…AlgorithmCompilercontext-free lan…Pumping Le…

A pumping lemma is a theorem stating that sufficiently long strings in certain classes of formal languages contain parts that can be repeated or removed while remaining in the language. The two standard versions concern regular languages and context-free languages. Their repetition properties arise from repeated states in finite automata or repeated nonterminals in grammatical derivations. Pumping lemmas are chiefly used to prove that a language does not belong to one of these classes: if a language fails the required property, it cannot belong to the class.

Notation and meaning

A formal language LL is a set of finite strings over an alphabet Σ\Sigma. The set of all such strings is written Σ∗\Sigma^*. For a string ww, its length is ∣w∣|w|, and juxtaposition denotes concatenation.

For a string yy, the expression yiy^i means ii consecutive copies of yy, where ii is a nonnegative integer. In particular,

y0=ε,y^0=\varepsilon,

where ε\varepsilon is the empty string. Thus, “pumping” includes both repeating a segment and deleting it.

A pumping length is a positive integer pp beyond which the lemma guarantees a suitable decomposition of every string in the language. The value depends on the language or on a particular representation of it. It need not be the smallest possible value, and every larger integer is also a valid pumping length.

The lemmas concern strings already in the language. They do not claim that every sufficiently long string over the alphabet belongs to it.

Pumping lemma for regular languages

If LL is regular, there is an integer p≥1p\geq 1 such that every w∈Lw\in L with ∣w∣≥p|w|\geq p can be written

w=xyzw=xyz

with

∣xy∣≤p,∣y∣≥1,|xy|\leq p,\qquad |y|\geq 1,

and

xyiz∈Lfor every integer i≥0.xy^iz\in L\quad\text{for every integer }i\geq 0.

The conditions have distinct roles:

  • ∣xy∣≤p|xy|\leq p locates the repeated segment within the first pp symbols.
  • ∣y∣≥1|y|\geq 1 makes the repetition nontrivial.
  • The universal condition on ii requires the same decomposition to work for every number of repetitions.

Only the existence of one suitable decomposition is guaranteed. Other decompositions of the same string may fail to preserve membership.

Why the lemma holds

A regular language is recognized by a deterministic finite automaton. Suppose an automaton recognizing LL has nn states, and take p=np=n.

While reading the first nn symbols of a string, the automaton visits n+1n+1 states when the initial state is included. By the pigeonhole principle, two of these visits must be to the same state.

Split the input into:

  • xx: the prefix before the first of these two visits;
  • yy: the nonempty segment read between the visits;
  • zz: the remainder.

Reading yy returns the automaton to the same state. It can therefore traverse that loop zero times, once, or any number of times, then read zz and reach the same accepting state. The loop occurs within the first nn symbols, giving the required length bound.

This argument explains the underlying restriction: an automaton with finitely many states must repeat a state on a sufficiently long computation.

Proving that a language is not regular

The standard proof uses proof by contradiction:

  1. Assume that the language is regular.
  2. Let pp be the pumping length guaranteed by the lemma.
  3. Choose a string w∈Lw\in L, depending on pp, with ∣w∣≥p|w|\geq p.
  4. Consider every decomposition w=xyzw=xyz satisfying the length conditions.
  5. Show that, for each such decomposition, some i≥0i\geq 0 gives xyiz∉Lxy^iz\notin L.

The fourth step is essential. Demonstrating that one particular decomposition fails does not contradict the lemma, because a different decomposition might work.

Example: equal numbers of two symbols

Consider

L={anbn:n≥0}.L=\{a^nb^n:n\geq 0\}.

Assume LL is regular and let pp be its pumping length. Choose

w=apbp.w=a^pb^p.

For any permitted decomposition w=xyzw=xyz, the condition ∣xy∣≤p|xy|\leq p places yy entirely within the initial block of aa's. Therefore,

y=aky=a^k

for some 1≤k≤p1\leq k\leq p.

Taking i=0i=0 gives

xz=ap−kbp,xz=a^{p-k}b^p,

which has unequal numbers of aa's and bb's and is not in LL. This contradicts the pumping lemma, so LL is not regular.

The conclusion is specifically nonregularity. The language is nevertheless context-free.

Pumping lemma for context-free languages

If LL is context-free, there is an integer p≥1p\geq 1 such that every w∈Lw\in L with ∣w∣≥p|w|\geq p can be written

w=uvxyzw=uvxyz

with

∣vxy∣≤p,∣vy∣≥1,|vxy|\leq p,\qquad |vy|\geq 1,

and

uvixyiz∈Lfor every integer i≥0.uv^ixy^iz\in L \quad\text{for every integer }i\geq 0.

Here two segments, vv and yy, are pumped together using the same exponent. Either may be empty, but they cannot both be empty. The middle segment xx is unchanged.

The bounded window vxyvxy may occur anywhere in the string. Unlike the regular-language lemma, this lemma does not restrict the pumpable material to a prefix.

Letters used for the five segments vary between presentations. The mathematical content is determined by which segments are repeated and by the length constraints.

Why the lemma holds

A context-free language is generated by a context-free grammar. Its derivations can be represented by parse trees, whose internal nodes are nonterminal symbols and whose leaves yield the generated string.

The standard proof converts the grammar to Chomsky normal form, treating the empty string separately. In this form, productions have the shapes

A→BCorA→a.A\to BC \quad\text{or}\quad A\to a.

A sufficiently long string requires a sufficiently deep parse tree. Because the grammar has finitely many nonterminals, some nonterminal AA repeats along a root-to-leaf path. The relevant portions of the derivation have the form

S⇒∗uAz,A⇒∗vAy,A⇒∗x.S\Rightarrow^*uAz,\qquad A\Rightarrow^*vAy,\qquad A\Rightarrow^*x.

Repeating the middle derivation, or omitting it, produces

uvixyiz.uv^ixy^iz.

Choosing repeated occurrences near the bottom of a sufficiently long path bounds the yield vxyvxy. The branching structure ensures that at least one of vv and yy is nonempty.

The two pumped segments represent material generated on opposite sides of a recursively expanded nonterminal.

Proving that a language is not context-free

The proof strategy has the same quantifier structure as for regular languages, but it must account for two pumped segments.

Example: three equal blocks

Consider

K={anbncn:n≥0}.K=\{a^nb^nc^n:n\geq 0\}.

Assume KK is context-free, let pp be its pumping length, and choose

w=apbpcp.w=a^pb^pc^p.

For any permitted decomposition w=uvxyzw=uvxyz, the window vxyvxy has length at most pp. It cannot contain both an aa and a cc, because doing so would require spanning the entire block of pp intervening bb's as well.

Consequently, the pumped segments vv and yy together contain symbols from at most two of the three blocks. At least one symbol type is untouched.

Taking i=0i=0 removes at least one symbol because ∣vy∣≥1|vy|\geq 1, while leaving all pp occurrences of at least one other symbol type unchanged. The resulting string cannot have equal counts of aa, bb, and cc. It is therefore outside KK, contradicting the lemma.

Thus KK is not context-free. This excludes recognition by a pushdown automaton, not recognition by more powerful computational models.

Quantifiers and common errors

The regular-language lemma has the logical structure

∃p≥1 ∀w∈L, ∣w∣≥p ∃x,y,z ∀i≥0,\exists p\geq 1\ \forall w\in L,\ |w|\geq p\ \exists x,y,z\ \forall i\geq 0,

with the decomposition constraints understood.

A nonregularity proof establishes the opposite pattern:

∀p≥1 ∃w∈L, ∣w∣≥p ∀ permitted decompositions ∃i≥0\forall p\geq 1\ \exists w\in L,\ |w|\geq p\ \forall\text{ permitted decompositions}\ \exists i\geq 0

such that the pumped string is outside LL.

This order explains several frequent mistakes:

  • Selecting a convenient decomposition. The proof must defeat every permitted decomposition.
  • Using a string outside the language. The lemma makes no promise about such strings.
  • Choosing a fixed string without accommodating pp. The string must be long enough for an arbitrary pumping length.
  • Requiring one exponent to work for all decompositions. The exponent may depend on the decomposition.
  • Pumping the two context-free segments independently. Both must use the same exponent.
  • Treating successful pumping as a membership proof. The lemmas provide necessary conditions, not characterizations.

The context-free lemma has the corresponding quantifier structure, with five segments instead of three.

Scope and limitations

Neither standard pumping lemma has a valid converse: satisfying its pumping property does not, by itself, establish regularity or context-freeness. To establish membership, a proof normally constructs an appropriate automaton, grammar, or equivalent description, or uses established closure properties.

Finite languages satisfy both lemmas vacuously when pp is greater than every string length in the language. There are then no strings to which the pumping requirement applies.

The lemmas are structural proof tools, not general-purpose algorithms for classifying arbitrarily specified languages. Their usefulness depends on finding a string whose possible decompositions can all be controlled. Some languages resist a direct pumping argument even when their nonmembership can be established by other methods.

For regular languages, the Myhill–Nerode theorem gives a necessary and sufficient characterization using distinguishable prefixes. For context-free languages, Ogden's lemma strengthens the pumping method by allowing selected positions in a string to be marked, constraining where pumping must occur. Closure properties can also transform a difficult language into one with a simpler nonmembership proof.

These methods help distinguish expressive capabilities relevant to compiler construction: finite-state techniques are suited to many lexical patterns, while context-free grammars describe many recursively nested syntactic structures. Pumping arguments establish limits of those formal models; they do not imply that the same language is impossible to recognize using a more powerful model.