[Overview] [Previous] [Next]

A Pumping Lemma for CFGs

A pumping lemma is a theorem used to show that, if certain strings belong to a language, then certain other strings must also belong to the language. In this section we discuss a pumping lemma for context-free languages.

We will show that, if L is a context free language, then strings of L that are at least m symbols long can be "pumped" to produce additional strings in L. (The value of m depends on the particular language.)

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.

Let's see what this says.

Copyright 1996 by David Matuszek
Last modified Mar 19, 1996