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 (http://en.wikipedia.org/wiki/Pumping_lemma). 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.