[Overview] [Previous] [Next]

Pumping Lemmas

Regular languages

If L is an infinite regular language, then there exists some positive integer m such that any string w L whose length is m or greater can be decomposed into three parts, xyz, where

• |xy| is less than or equal to m,
• |y| > 0,
• w_i = xyⁱz is also in L for all i = 0, 1, 2, 3, ....

Context-free languages

Let L be an infinite context-free language. Then there is some positive integer m such that, if S is a string of L of length at least m, then

• S = uvwxy (for some u, v, w, x, y)
• |vwx| m
• |vx| 1
• uvⁱwxⁱy L

for all nonnegative values of i.

Usage

Pumping lemmas are used to show that a given language is not of type (regular/context-free). The argument goes:

• Assume the language is (regular/context-free).
• Choose a string of the language.
• Pump the string to obtain another that, by the pumping lemma, must also be in the language.
• Show that the pumped string is not in the language.
• Conclude that the language cannot be (regular/context-free).