Oh, how the CS majors of '04 love the pumping
lemma. So much in fact, that he's got his own game in
development. CDT Andrew Reed has been plugging away with Dark
Basic Pro to create this exciting challenge against a fire-team of
"Turing Machines" to collect lambdas. Stay tuned as we update
the game and bring you more lovable CS perversions.
The Game (As of 02 November)
The "Hanky" Mod
Harry Mairson:
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, resilient 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.
A more
technical description:
|
Main Page
Pictures
Art
Videos
Links |
