[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 is a member of L whose length is m or greater can be decomposed into three parts, xyz, where

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

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:


Copyright 1996 by David Matuszek
Last modified Apr 24, 1996