title: Pumping lemma
text: # 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
  