Monday, February 24, 2003

Maaaaaagic

Today in theory...

The Pumping Theorem:

Let L be a regular language.
Then there exists n >=1 such that any string w that is an element of L with |w|>n,
there exists x, y, z so that w can be rewritten as w=xyz, such that y !=e, |xy|<=n, and xy^iz is an element of L for each i>=0.

Me: "So, where does the n come from?"
Dr. McAllister: "Oh, well, the n is sorta like magic."
Class: "Ah, magic..mm, yes *note note note*."

No comments: