Pumping lemma
From Wikipedia, the free encyclopedia
In the theory of formal languages in computability theory, a pumping lemma states that any language of a given class can be "pumped" and still belong to that class. A language can be pumped if any sufficiently long string in the language can be broken into pieces, some of which can be repeated arbitrarily to produce a longer string in the language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
The two most important examples are the pumping lemma for regular languages and the pumping lemma for context-free languages. Ogden's lemma is a second, stronger pumping lemma for context-free languages.
These lemmas can be used to determine if a particular language is not in a given language class. However, they cannot be used to determine if a language is in a given class, since satisfying the pumping lemma is a necessary, but not sufficient, condition for class membership.
[edit] References
- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.
