pumping lemma
Definition from Wiktionary, the free dictionary
Contents
English[edit]
Noun[edit]
pumping lemma (plural pumping lemmas or pumping lemmata)
 (computer science) A lemma which states that for a language to be a member of a language class any sufficiently long string in the language contains a section that can be removed or repeated any number of times with the resulting string remaining in the language, used to determine if a particular language is in a given language class (e.g. not regular).
 1997, Dexter Kozen, Automata and computability (page 148)
 There is a pumping lemma for CFLs similar to the one for regular sets. It can be used in the same way to show that certain sets are not contextfree.
 2002, Alejandro Maass, Servet Martínez, Jaime San Martín, Dynamics and randomness (page 174)
 In the literature one finds many pumping lemmas which describe the ability to repeat (pump) certain words repeatedly in some languages, under different circumstances.
 2010, Marco Kuhlmann, Dependency Structures and Lexicalized Grammars: An Algebraic Approach (page 107)
 Stringlanguage hierarchies are usually proven using formalismspecific pumping lemmata.
 1997, Dexter Kozen, Automata and computability (page 148)
Translations[edit]
lemma stating that a section of a string can be removed or repeated with the resulting string remaining in the language

See also[edit]
 Pumping lemma on Wikipedia.Wikipedia