Pumping Lemma

Found an interesting article about pumping lemma, it is a poetry about pumping lemma. Here it is.

The Pumping Lemma, in poetic form

“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 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.”

By Martin Cohn and Harry Mairson