pumping lemma

English

Noun

pumping lemma (plural pumping lemmas or pumping lemmata)

1. (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 context-free.

   • 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:

     String-language hierarchies are usually proven using formalism-specific pumping lemmata.

Translations

lemma stating that a section of a string can be removed or repeated with the resulting string remaining in the language

• Icelandic: dælusetning f

See also

• pumping lemma on Wikipedia.Wikipedia