Pumping lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Whenever a sufficiently long string uvw is recognized by a finite automaton, it must have reached some state (qs=qt) twice. Hence, after repeating ("pumping") the middle part v arbitrarily often (uvvw, uvvvw, ...) the word will still be recognized.

In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that 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 (cf. picture) and the pumping lemma for context-free languages. Ogden's lemma is a second, stronger pumping lemma for context-free languages. Pumping lemmas are known also for regular tree languages,[1] and for indexed languages.[2]

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.

References[edit]

  • 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.
  • Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Addison-Wesley. ISBN 0-321-32221-5.  Chapter 6: Properties of Regular Languages pp. 205–210
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.  Chapter 4.1.1: The Pumping Lemma for Regular Languages, pp.126–129. Chapter 7.2: The Pumping Lemma for Context-Free Languages, pp.274–281
  1. ^ H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard and D. Lugiez, S. Tison, M. Tommasi (Nov 2008). Tree Automata Techniques and Applications. Retrieved 11 February 2014.  Chapter 1.2: The Pumping Lemma for Recognizable Tree Languages, pp.28–29
  2. ^ T. Hayashi (1973). "On Derivation Trees of Indexed Grammars – An Extension of the uvxyz Theorem". Publication of the Research Institute for Mathematical Sciences (Research Institute for Mathematical Sciences) 9 (1): 61–92.