I hate the Pumping Lemma

Ironically, this post's explanation caused me understand the pumping lemma for the first time after years of letting my eyes just slide over any time I read across a mention.

(It nerdsniped me by claiming it was difficult.)

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...

[1] http://en.wikipedia.org/wiki/James_while_John_had_had_had_ha...

[2] 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.

What is with these hacker news articles that are hard to understand with no clear point?

I'm not sure if they're turing complete, however many many many common regexp dialects (as seen in perl, ruby, python, etc.) are more powerful than what you learned as "regular expressions" in CS class, they're at least as powerful as a PDA.