[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

• S = uvwxy (for some u, v, w, x, y)
• |vwx| m
• |vx| 1
• uviwxiy L
for all nonnegative values of i.

Let's see what this says.

• If S is a sufficiently long string, then there are two substrings, v and x, somewhere in S. There is stuff (u) before v, stuff (w) between v and x, and stuff (y) after x.
• The stuff between v and x won't be too long, because |vwx| can't be larger than m.
• Substrings v and x won't both be empty (though either one could be).
• If we duplicate substring v some number (i) of times, and duplicate x the same number of times, the resultant string will also be in L.