What is "pumping lemma"

n. (context computer science English) 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).

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