I hate the Pumping Lemma

Yeah, that's how it is usually introduced to students. First you introduce them to finite state automatons, then you show them a cool trick of extending the words by walking in circles on the automaton's state graph, and only then you mention that this is basically a pumping lemma. After everyone understood the point of the pumping lemma, you write it down formally using five quantifiers, so that student can write it down concisely, as the idea is already understood at that point.

I agree that the formal statement of the pumping lemma can be very uninspiring, but it only hints to two important facts. First, it's very important to have a good teacher, who is able to introduce ideas in a way and order they work for you. Second is that in math, it's the proofs and ideas that are important, not theorem statements.

(It nerdsniped me by claiming it was difficult.)

Him: Do you know how to check if it's possible to write a regular expression for this?

Me: Either create an automata and then it's demonstrably possible, or apply the pumping lemma to prove it's impossible?

Him: No. Dare Stackoverflow to write it.

"It has an ferociously intimidating logical structure, with no fewer than five alternating quantifiers ... If two are a struggle, five is cruelty".

Seriously, if you're planing on using the pumping lemma you should also be able to read and understand those five quantifiers. It's not "just the lemma", it's also the ability to read that and understand it that has some value in itself. Go on then to the pumping lemma for context free languages. I don't know about you but learning how to read the lemma and understand it, helped me understand the lemma for CFG really quickly.

Knowledge is always good, and if you have to learn something else to get the lemma too, then that's even better and what do you know maybe one day you'll have to know how to read a complex statement with quantifiers and not the pumping lemma.

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.

It's always Car>Vehicle>Entity kind of structures, which actually sucks and in most cases composition should be done.

They use "for all X" "of type" Y (being "of type" meaning: has these properties) then Z happens in place of "if you have something that has these properties Z happens"

Yes, they are equivalent, but the first order logic version looks like "strongly typed" and the second version looks like "duck typed"

This is just my 2 cents.

And that while parsing languages is actually a really nice topic, and the various parsing modes are very easy to understand if you talk through them from the implementation perspective (LL in particular, but also LR, LALR). It's very intuitive how parsing has to make a decision given a certain lookahead and thus has to pick the correct rule to descend into, how that relates to the runtime efficiency, and it also makes other solutions understandable, e.g. packrat parsing.

Nothing against getting a strong formal model for a problem, but I think Academia's approach is often the wrong way around. It's much easier to understand these solutions from the code, and then develop a theoretical model around them (this is how all of them were invented anyway).

Type "Ham and eggs".

Now, put more space between "Ham" and "and" and "and" and "eggs".

Now, put more space between...

Right. I wonder how many statements in theory of computation are essentially the pigeonhole principle.

Starts at 3:43. http://www.youtube.com/watch?v=sqkcpQw-78A&feature=share&lis...