Word.ws English Dictionary

pumping lemma

pumping lemma noun: 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).

Noun

pumping lemma (plural pumping lemmas or pumping lemmata)

  1. 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).
    • 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.1997, Dexter Kozen, Automata and computability, page 148
    • In the literature one finds many pumping lemmas which describe the ability to repeat (pump) certain words repeatedly in some languages, under different circumstances.2002, Alejandro Maass, Servet Martínez, Jaime San Martín, Dynamics and randomness, page 174

Forms of pumping lemma

pluralpumping lemmas
pluralpumping lemmata

Questions about pumping lemma

What does pumping lemma mean?
Pumping lemma means 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).
What part of speech is pumping lemma?
Pumping lemma is a noun.
What is the plural of pumping lemma?
The plural of pumping lemma is pumping lemmas.

Words near pumping lemma in the dictionary

  1. pumpies
  2. pumpin'
  3. pumping
  4. pumping and dumping
  5. pumping iron
  6. pumping lemma
  7. pumping lemmas
  8. pumping lemmata
  9. pumping one's fist
  10. pumping out
  11. pumping someone's fist

Source and license

Adapted from Wiktionary: pumping lemma (page history and authors). Text available under the Creative Commons Attribution-ShareAlike 4.0 license. Word.ws reformatted the entry and added links. Wiktionary data of 2026-09-02.

Last updated:

Pronunciation audio from Wikimedia Commons, each file under its own free license: LL-Q1860 (eng)-Naomi Persephone Amethyst (NaomiAmethyst)-pumping lemma.wav.

Cite this entry: “pumping lemma.” Word.ws, https://word.ws/pumping_lemma. Based on Wiktionary, CC BY-SA 4.0.