I remember having a conversation with Jesse
jes5199 a couple of years ago in which I was telling him all the things I didn't really learn in undergrad.
Jes: Well, what did they teach you, then?!
Lindsey: Um...the pumping lemma.
Jes: What's that?
Lindsey: ...I don't remember.
Awesome, just awesome.
Edited at 20091029 05:00 am (UTC)
From: (Anonymous) 20100116 07:23 am (UTC)
Awesome indeed.  (Link)

Sigh. You know, I'm teaching the automata theory course again in spring 2011. You're sapping my motivation.
OK, I'll make this as quick and easy. The pumping lemma is a way to show that a set of strings isn't a regular language. Imagine it as a game between two players, Con and Pro, who disagree about a set L of strings. Con wants to show that it's not a regular language; Pro wants to keep alive the possibility that it might be regular. The game that they play is a short one, only four moves: (1) Pro chooses a positive integer, p. (2) Con chooses a string s that is in L and is at least p symbols long. (If Con can't find such a string, she loses, because then L is finite and all finite languages are regular.) (3) Pro partitions s into three substrings uvw, where v is not the null string and the sum of the lengths of uv is less than or equal to p. (4) Con chooses a nonnegative integer n, the repetition factor. Now the players check whether the string formed by concatenating u, n repetitions of v, and w is in L. If so, Pro wins; if not Con wins.
The pumping lemma says that if L is a regular language, then there is a winning strategy for Pro. The proof just explains what that strategy is: Build a deterministic finite automaton M that recognizes L and choose p as the number of states in M. In processing the string s, the automaton makes p transitions, so at some point it has to reenter a state that it was in previously; choose the substring v as the substring processed after the automaton entered the repeated state for the first time and before it exited from it the second time. Since M accepts uvw, it will also accept u v^n w  for the middle part, it will just run through the cycle of states n times.
So if, on the contrary, there is a winning strategy for Con, L can't be regular. Thus you can prove that a language isn't regular by finding a winning strategy for Con.
There's also a pumping lemma for contextfree languages, which differs only in the way move (3) works  Pro has to partition the string into five substrings, uvwxy, such that not both v and x are null and the sum of the lengths of v, w, and x is less than or equal to p. The proof of the lemma is different, of course, but it too is quite elegant  go back and look it up if you don't believe me.
This is not torture, friends. This is enlightenment.
John David Stone