Any regular language *L* has a magic number *p*

And any long-enough word in *L* has the following property:

Amongst its first *p* symbols is a segment you can find

Whose repetition or omission leaves *x* amongst its kind.

So if you find a language *L* which fails this acid test,

And some long word you pump becomes distinct from all the rest,

By contradiction you have shown that language *L* is not

A regular guy, resiliant to the damage you have wrought.

But if, upon the other hand, *x* stays within its *L*,

Then either *L* is regular, or else you chose not well.

For *w* is *xyz*, and *y* cannot be null,

And *y* must come before *p* symbols have been read in full.

As mathematical postscript, an addendum to the wise:

The basic proof we outlined here does certainly generalize.

So there is a pumping lemma for all languages context-free,

Although we do not have the same for those that are r.e.

Thu Oct 9 11:06:29 EDT 1997