Here's what I think is a fun explanation of the pumping lemma, using no special terminology. As many people on here know, the phrase "Buffalo buffalo Buffalo b

Here's what I think is a fun explanation of the pumping lemma, using no special terminology. As many people on here know, the phrase "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo" is a complete sentence[0]. What many people may not know is that you can add (but not subtract) as many "buffalo" as you want and still have it be a complete sentence. Why's that? Well, an easier sentence to look at is "James while John had had had had had had had had had had had a better effect on the teacher"[1]. In this case, it's clear (once you understand the meaning of the sentence) that you can add as many "had" words as you want, as long as you keep above a certain minimum. This is because all but a couple of the "hads" should really be inside quotation marks, as they are simply denoting the words that James (or John) did have at some past time - they convey no semantic meaning within the sentence. If you envision a DFA[2] (okay, here's where it gets technical), we're basically saying that one node has an edge that goes to itself - a "self loop" - or a previous node that has already been visited. Once you have this loop established, you can traverse it as many times as you want (ie, arbitrarily many), as long as you traverse it a minimum number of times. All the pumping lemma states is that: (1) if this loop exists, it can be traveled as many times as you want, and (2) It must have the same effect each time (since DFAs have no "memory" - they have no stack). If there is a limit to the number of times it can be traversed, or if it has a different effect depending on the number of iterations[3], then the language cannot be regular. [0]http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo... [1] http://en.wikipedia.org/wiki/James_while_John_had_had_had_had_had_had_had_had_had_had_had_a_better_effect_on_the_teacher http://en.wikipedia.org/wiki/James_while_John_had_had_had_ha... [2] http://en.wikipedia.org/wiki/Deterministic_finite_automaton http://en.wikipedia.org/wiki/Deterministic_finite_automaton [3] Okay, to be really pedantic, it can have a different effect each time, as long as there is a finite number of "different" effects it can have, since there must be a finite number of states in a DFA. But that was a bit too clumsy to try and write.