In the theory of  in , a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require  such as the .

The two most important examples are the  and the . is a second, stronger pumping lemma for .

These  can be used to determine if a particular language is not in a given language class. However, they cannot be used to determine if a language is in a given class, since satisfying the pumping lemma is a , but not sufficient, condition for class membership.

References[ | ]

•  (1997). Introduction to the Theory of Computation. PWS Publishing.  . Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.
• Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley.  . Chapter 6: Properties of Regular Languages pp. 205–210