“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.�
[By Martin Cohn and Harry Mairson]