Comments: 
It's hilarious how I write about stuff like this, and then I go to job interviews and can't answer questions about hash tables.
Yeah, I think that's usually how it goes. Shameful secret: I didn't even really know what a hash table *was* until I had a master's degree in CS.
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)
I get the feeling nobody really thinks much about the pumping lemma (I almost wrote "pumpkin lemma", ftw) until they get to be a professor and it's *their* turn to torment the undergrads with it.
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
 From: pmb 20100116 07:48 am (UTC)
Re: Awesome indeed.  (Link)

This is not torture, friends. This is enlightenment.
Preach on.
(Deleted comment)
*flips through* Chain pruning aka path compression? Actually, we do (but without sideeffecting the substitution  we just stick the last thing in the chain on the front of the substitution so it's faster to look up the next time). (Does path compression come from Cardelli? If so, awesome  I was looking for an appropriate reference.) We have a couple of other tricks for dealing with long chains, as well, but part of the gist of our paper is that we find that most of the substitutions that arise from running real miniKanren programs don't contain very long chains; rather, they're just big. So, we present some techniques that make real mK programs run faster. (Although our suite of "real" mK programs includes, you know, the Zebra Puzzle, so I guess "real" is debatable.) Would you be interested in looking over the paper? I'd love to get comments from you (in a couple of days, probably, once I finish making all the revisions that are already on my list). (Deleted comment)
Great! I'll get it to you. (Deleted comment)
From: (Anonymous) 20091030 04:14 pm (UTC)
 (Link)

> By chain pruning I mean...
Hee. I love how reading this journal always gives me great tips for my own thesis... about a month or so after I've learned about the same principle the hard way.
I want to read that paper.
I want you to! I'll send you a draft of it in a day or so.  