Pumping lemma

In the theory of formal languages, the pumping lemmas provide necessary conditions for languages to be regular or context-free. They are almost exclusively used in order to prove that a given language is not regular or context-free.

One can say therefore that 'pumping lemma' is a name for the application of the pigeonhole principle, in the context of a finite state machine.

Pumping lemma for regular languages

If a language L is regular, then there exists a number m > 0 such that every string w in L with length |w| ≥ m can be written in the form

w = xyz

with strings x, y and z such that |xy| ≤ m, |y| ≥ 1 and

xy^kz is in L for every k≥0.

Using this lemma, one can for instance prove that the language L = {aⁿbⁿ : n ≥ 0} over the alphabet Σ = {a, b} is not regular. For if it were, we could pick m as in the pumping lemma. The string w = a^mb^m is in L, and the pumping lemma therefore yields a decomposition w = xyz with |xy|≤ m, |y|≥ 1 and xy^kz in L for every k≥0. But then y has to consist of a non-zero number of a's, and xy⁰z has less a's than b's and is therefore not in L, a contradiction.

The proof idea for the pumping lemma is as follows: the regular language is accepted by a certain deterministic finite acceptor; every string that's longer than the number m of states of that acceptor will revisit a certain state, thereby causing a loop which can be repeated; the loop corresponds to the string y.

Pumping lemma for context-free languages

If a language L is context-free, then there exists some number m > 0 such that any string w in L with |w| ≥ m can be written as

w = uvxyz

with strings u, v, x, y and z, such that |vxy| ≤ m, |vy| ≥ 1, and

uv^kxy^kz is in L for every k ≥ 0.

A typical application of this pumping lemma is the proof that the language L = {aⁿbⁿcⁿ : n ≥ 0} over the alphabet Σ = {a, b, c} is not context-free.