Article · Wikipedia archive · Last revised Jun 3, 2026

Pumping lemma

In the theory of formal languages, the pumping lemma may refer to:Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular Pumping lemma for context-free languages, the fact that all sufficiently long strings in such a language have a pair of substrings that can be repeated arbitrarily many times, usually used to prove that certain languages are not context-free Pumping lemma for indexed languages Pumping lemma for regular tree languages

Last revised
Jun 3, 2026
Read time
≈ 1 min
Length
112 w
Citations
Source

In the theory of formal languages, the pumping lemma may refer to:

See also

See also

  • Ogden's lemma, a stronger version of the pumping lemma for context-free languages