Thursday, May 23, 2013

The Pumping Lemma

This was originally posted in October 2008 while I was at the National Science Foundation (NSF)  in Arlington, Virginia -- the 12th floor of NSF was the big room, but this post is primarily on the wonders of computer science.

My talk on "the 12th floor" yesterday went well, and I'm here on the second floor of the Arlington library, looking out on a beautiful day ... maybe a matinee later, and DC tomorrow.

I've been remembering the Pumping Lemma, a little gem from computer science ( The Pumping Lemma says that for certain languages that have an infinite number of possible sentences, there is a fragment (e.g., "big") of a sentence that is 'long' enough ("You are making a big mistake"), which you can repeat an arbitrary number of times (or exclude in some cases), and you will still have a (legal) sentence -- so if "big" is the fragment, then "You are making a mistake" is a sentence (excluding "big" from the original), and "You are making a big, big mistake" and You are making a big, big, big, mistake" are sentences (if you know enough to note the comma, you know enough to know the fix; and I don't think that English is one of the "certain" languages for which the Pumping lemma covers "in all cases", but it's ok). More generally, if I've got an adjective in a sentence, I could repeat that adjective or any other for that matter an arbitrary number of times, and still end up with a (legal) sentence.

What does this have to do with anything? I first saw the pumping lemma(s) about age 21, my first or second quarter at UC Irvine, after transferring schools (UCSC, USNA) and changing majors twice before, having my heart broken a few times, etc :-) When I saw these lemmas and their proofs I was struck by the formal beauty of them, but I also saw them as descriptive metaphors of my life to date -- you can repeat the some mistakes over and over, but still have hope of completing a sentence -- I'm serious, I was wow'd by it, as well as by the metaphorical significance of other gems in computing and mathematics. 

There are some parts of a partial sentence, of course, that you can't repeat arbitrarily and have hope of completing a sentence; for example, you can't write "You are making a a " and have any hope of completing the sentence so it's legal -- once you repeat that 'a' in the way written, you end up in a 'dead' state. And you can of course keep repeating the "big" and never get to the final "mistake" before you "run out of time", and since "You are making a big, big,..., big" isn't a legal sentence, again, its a "dead" state -- both of these examples have formal interpretation. And of course, the repetition (or pumping) need not be metaphorical of mistakes, but successes, and a lot of in between.

The pumping lemmas are just concerned with syntax and not semantics -- you can understand and appreciate a string such as "Made you a mistake big" or even "You are making a big, ...., big", but I'm retaining hope for a sentence, and a compound, rich sentence at that. 

Thank goodness for the pumping lemmas -- I've reflected on their lessons since age 21 :-). Hallelujah.