[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^{i}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
^{i}wx^{i}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).

Copyright © 1996 by David Matuszek

Last modified Apr 24, 1996