The two most important examples are the pumping lemma for
regular languages and the pumping lemma for context-free languages.
These are called 'lemmas' rather than 'theorems' not because they are
unimportant, but because their primary use is to generate quick proofs
that a particular language is *not* in the language class. However, they cannot be used to prove the statement that a language is in the class; satisfying the pumping lemma is a necessary, but not sufficient, condition.

Someone familiar with the pumping lemma for regular languages can see immediately that a language that allows parenthesized expressions, but requires the parentheses to balance, can not be a regular language, and so the language can not be generated by a regular grammar nor recognized by a finite state machine. Trying to compose such a proof directly would take a significant length of time.

If a languageLis regular, then there exists a numberm> 0 such that every stringwinLwith length |w| ≥mcan be written in the formwith strings

w=xyzx,yandzsuch that |xy| ≤m, |y| ≥ 1 and

xyis in^{k}zLfor everyk≥0.

The proof idea for the pumping lemma itself is as follows: the regular language is accepted by a certain deterministic finite acceptor; every string that's longer than the number *m* of states of that acceptor will revisit a certain state, thereby causing a loop which can be repeated; the loop corresponds to the string *y*.

Note that the pumping lemma does not give a *sufficient* condition for a language to be regular: for example, the language *{a ^{n}b^{m} : n ≥ m}* is not regular but can still be "pumped." For a practical test that exactly characterizes regular languages, see the Myhill-Nerode Theorem.

If a languageLis context-free, then there exists some numberm> 0 such that any stringwinLwith |w| ≥mcan be written aswith strings

w=uvxyzu,v,x,yandz, such that |vxy| ≤m, |vy| ≥ 1, and

uvis in^{k}xy^{k}zLfor everyk≥ 0.