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.
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 formwith strings x, y and z such that xy ≤ m, y ≥ 1 and
 w = xyz
 xy^{k}z is in L for every k≥0.
Using this lemma, one can for instance prove that the language L = {a^{n}b^{n} : 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^{m}b^{m} is in L, and the pumping lemma therefore yields a decomposition w = xyz with xy≤ m, y≥ 1 and xy^{k}z in L for every k≥0. But then y has to consist of a nonzero number of a's, and xy^{0}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.
If a language L is contextfree, then there exists some number m > 0 such that any string w in L with w ≥ m can be written aswith strings u, v, x, y and z, such that vxy ≤ m, vy ≥ 1, and
 w = uvxyz
 uv^{k}xy^{k}z is in L for every k ≥ 0.
A typical application of this pumping lemma is the proof that the language L = {a^{n}b^{n}c^{n} : n ≥ 0} over the alphabet Σ = {a, b, c} is not contextfree.
Search Encyclopedia

Featured Article
