# 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

## See also

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

This article is issued from Wikipedia - version of the 3/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.