Encyclopedia > Pumping lemma

  Article Content

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
xykz is in L for every k≥0.

Using this lemma, one can for instance prove that the language L = {anbn : 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 = ambm is in L, and the pumping lemma therefore yields a decomposition w = xyz with |xy|≤ m, |y|≥ 1 and xykz in L for every k≥0. But then y has to consist of a non-zero number of a's, and xy0z 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
uvkxykz is in L for every k ≥ 0.

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
BBC News 24

... signals, and this is seen by some as influential (to a certain limited extent) in promoting the take-up of digital television. BBC News 24 broadcasts from the ...

 
 
 
This page was created in 44 ms