News for hackers. Stuff that matters.
Re:I hate the Pumping Lemma by xyzzyz on Monday August 19, 2013 @12:12AM (#6235579)
The real insult is that the actual underlying idea, and the proof, is shockingly simple. It is essentially the pigeonhole principle: the principle that if you put more than n pigeons into n holes then there must be a hole with more than one pigeon in. Take the regular language L, and express it as a deterministic finite automaton with p states. Any string in L determines a path through the automaton; so any string with p or more characters must visit the same state twice, forming a loop. This looped part can be repeated any arbitrary number of times to produce other strings in L.

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.

Re:I hate the Pumping Lemma by sergiosgc on Monday August 19, 2013 @09:29AM (#6237061)
This must beg the question: is math formal language expressive enough? Too often, the ideas are really simple but the mathematical formulation is extraordinarily complex. The first time I realized this was with Fourier transforms. Analytically, it is hell to understand the fundamentals, while if you read the original description by Fourier, it becomes dead obvious (as most great ideas, after the fact)
Re:I hate the Pumping Lemma by xyzzyz on Monday August 19, 2013 @12:57PM (#6238228)
Math formal language is expressive enough to express everything most mathematicians want. The thing is that formal math language wasn't designed as a medium to transfer ideas, but rather as a notation to write them down concisely and make things easy to manipulate. That's why learning from books that are very formal is such a difficult experience, though it gets easier with experience. Unfortunately, to get to that level of experience, you pretty much have to be focused on pure mathematics for years, and if you're just trying to learn some math to get some other shit done, and there isn't any book written in more conversational style (which thankfully usually is the case), you're out of luck.
Re:I hate the Pumping Lemma by abecedarius on Monday August 19, 2013 @10:32AM (#6237415)
Have a link to the original description?

Apostol explained it with linear algebra, which made sense, but seems pretty magical in terms of how you'd notice sine waves make an orthogonal basis in the first place.

Re:I hate the Pumping Lemma by sergiosgc on Monday August 19, 2013 @04:34PM (#6239614)
It was handed out as support material in a course. I can't for the life of me find it online. Anyhow, the transform hinges on two insights: you can use a point rotating in a circle as a basic building block and you can look at any signal as a sequence of spikes. This article looks like it follows the same approach: http://betterexplained.com/articles/an-interactive-guide-to-...
Re:I hate the Pumping Lemma by contravert on Monday August 19, 2013 @03:36PM (#6239234)
I would like to see his original description as well. I've never understood the Fourier transform intuitively, no matter how much my professors and textbooks attempt to explain it. At this point, I'm just applying algorithms without fully understanding why I'm doing it.
Re:I hate the Pumping Lemma by a8i on Sunday August 18, 2013 @09:06PM (#6235032)
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.)

Re:I hate the Pumping Lemma by jfb on Sunday August 18, 2013 @09:46PM (#6235144)
Same here. Also, cheers for "nerdsniped." I'd never heard that before.
Re:I hate the Pumping Lemma by cschmidt on Sunday August 18, 2013 @10:03PM (#6235182)
Re:I hate the Pumping Lemma by kingkilr on Sunday August 18, 2013 @09:08PM (#6235044)
A conversation I had the other week:

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.

Re:I hate the Pumping Lemma by TheZenPsycho on Sunday August 18, 2013 @11:47PM (#6235496)
the answer if you're using perl or pcre, is probably yes, but for the love of djikstra don't ever do it. This was on HN a while back:

http://nikic.github.io/2012/06/15/The-true-power-of-regular-...

Re:I hate the Pumping Lemma by mcguire on Monday August 19, 2013 @12:03PM (#6237938)
This is a trivial corollary of the Basic Technique For Finding the Correct Answer to a Question on the Internet:

Strongly assert a wrong answer on the Internet.

The correct answer will appear shortly.

Re:I hate the Pumping Lemma by im3w1l on Sunday August 18, 2013 @10:24PM (#6235264)
Some regexp dialects are actually Turing complete from what I've heard.

EDIT: Yes this seems to be wrong

Re:I hate the Pumping Lemma by kingkilr on Sunday August 18, 2013 @10:32PM (#6235288)
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.
Re:I hate the Pumping Lemma by chimeracoder on Sunday August 18, 2013 @10:36PM (#6235300)
> they're at least as powerful as a PDA.

PCREs (ie, the regular expressions that Perl uses) are NP-hard, since they allow backreferences.

Re:I hate the Pumping Lemma by kazagistar on Monday August 19, 2013 @01:22AM (#6235775)
I think you are confusing complexity and computability class.
Re:I hate the Pumping Lemma by anaphor on Monday August 19, 2013 @06:54AM (#6236496)
Do you mean that some regex implementations allow you to parse context-free grammars?
Re:I hate the Pumping Lemma by hyperpape on Monday August 19, 2013 @11:39AM (#6237803)
Most regex implementations allow you to parse some context-free grammars, and even some non-context-free grammars. But they don't let you parse all context-free grammars.

reference: http://cstheory.stackexchange.com/questions/1047/where-do-mo...

Re:I hate the Pumping Lemma by anaphor on Monday August 19, 2013 @04:59PM (#6239789)
Yeah, I should've said "all". I know that you can describe regular grammars using languages designed for CFGs, like BNF.
Re:I hate the Pumping Lemma by zidar on Sunday August 18, 2013 @11:57PM (#6235531)
Call me crazy, but I like the pumping lemma

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

Re:I hate the Pumping Lemma by mcguire on Monday August 19, 2013 @12:07PM (#6237962)
Plus, any alternative (Language derivatives? Really?[1]) is going to have an uphill public relations struggle, at least unless they too have a name that sounds vaguely obscene.

[1] I like them a lot, but are they really less cruel than the pumpster?

Re:I hate the Pumping Lemma by chimeracoder on Sunday August 18, 2013 @09:14PM (#6235064)
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.

Re:I hate the Pumping Lemma by ronaldx on Monday August 19, 2013 @04:34AM (#6236185)
I don't think this explains why the pumping lemma works for all strings (above a required length)?
Re:I hate the Pumping Lemma by stephencanon on Monday August 19, 2013 @10:01AM (#6237240)
I’m not sure what this has to do with the pumping lemma for DFAs, as English isn't a regular language.
Re:I hate the Pumping Lemma by lotsofcows on Monday August 19, 2013 @06:24AM (#6236425)
"Buffalo Buffalo Buffalo"?
Re:I hate the Pumping Lemma by jessaustin on Monday August 19, 2013 @09:18AM (#6237022)
Actually even "Buffalo buffalo." is a complete sentence.
Re:I hate the Pumping Lemma by lotsofcows on Monday August 19, 2013 @09:55AM (#6237209)
Yeah, but OP said I could remove as many "buffalo"s as I want and the sentence would still make sense. "Buffalo Buffalo Buffalo" does not make sense. Unless OP was ignoring case which makes it all rather contrived.

...even more contrived.

Re:I hate the Pumping Lemma by stephencanon on Monday August 19, 2013 @09:59AM (#6237226)
Yes, ignoring case. There’s no case in spoken language, so that’s quite reasonable, really.
Re:I hate the Pumping Lemma by jessaustin on Monday August 19, 2013 @10:45AM (#6237488)
Yeah I think you have to ignore case. The only word that needs to be capitalized is the first one in the sentence.
Re:I hate the Pumping Lemma by lotsofcows on Monday August 19, 2013 @10:53AM (#6237529)
What? No. The whole point is that the bison from Buffalo is bullying. If you ignore case it makes no sense. You can remove all the capital B-uffalos but you can't remove all the buffalos.

Some nice random down voting going on. This moderation system is sooooo good.

Re:I hate the Pumping Lemma by jessaustin on Monday August 19, 2013 @11:14AM (#6237655)
"Buffalo buffalo.": Ungulates bamboozle. Base case one.

"Buffalo buffalo buffalo.": Ungulates associated with western New York bamboozle. Base case two.

"X buffalo.": X bamboozle. Inductive case.

From these we have:

"Buffalo buffalo buffalo buffalo.": Ungulates bamboozled by ungulates, it turn bamboozle.

"Buffalo buffalo buffalo buffalo buffalo.": Ungulates bamboozled by ungulates, in turn bamboozle ungulates.

"Buffalo buffalo buffalo buffalo buffalo buffalo.": Ungulates associated with western New York and bamboozled by ungulates, in turn bamboozle ungulates.

"Buffalo buffalo buffalo buffalo buffalo buffalo buffalo.": Ungulates bamboozled by ungulates, in turn bamboozle ungulates that are bamboozled by ungulates.

It seems that only the N=6 case even requires a mention of the city.

I upvoted you to help you feel better.

Re:I hate the Pumping Lemma by lotsofcows on Tuesday August 20, 2013 @08:17AM (#6243172)
Nice. And thanks for the upvote - I feel better now.
Re:I hate the Pumping Lemma by more_original on Monday August 19, 2013 @07:40AM (#6236636)
I think one reason the Pumping Lemma is emphasized so much is that it is a good exercise in logic. We often find that students have difficulties with quantifier alternations (there exists x, such that for all y, there exists z, such that...). I think it is a good idea to practise such reasoning (e.g. for complicated module abstractions in software systems). The Pumping Lemma is a good example to exercise such reasoning.
Re:I hate the Pumping Lemma by H3g3m0n on Monday August 19, 2013 @04:29AM (#6236177)
I think a worse programming example is when inheritance is taught.

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

Re:I hate the Pumping Lemma by raverbashing on Monday August 19, 2013 @05:15AM (#6236286)
And that's one of the reasons I think mathematicians overcomplicate things.

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.

Re:I hate the Pumping Lemma by lmm on Monday August 19, 2013 @05:20AM (#6236301)
More than any other field, correctness is important in mathematics, and thus strong typing is useful, even essential.
Re:I hate the Pumping Lemma by calibraxis on Monday August 19, 2013 @07:43AM (#6236645)
Interesting argument, though I currently think correctness is more important in programming. Their proofs are hand-wavy compared to our programs.

Thurston expands, "It’s just that the reliability does not primarily come from mathematicians formally checking formal arguments; it comes from mathematicians thinking carefully and critically about mathematical ideas." (http://arxiv.org/abs/math/9404236)

But I could also accept the claim that mathematics is more intellectually gratifying, if they're not so much at the mercy of standardization and other boring fiddly issues. I don't know.

Re:I hate the Pumping Lemma by pseut on Monday August 19, 2013 @09:45AM (#6237144)
I disagree. A small nearly impossible to encounter edge case error may or may not be worth fixing in a program, but it invalidates a proof.
Re:I hate the Pumping Lemma by hyperpape on Monday August 19, 2013 @11:36AM (#6237785)
Depends. Many proofs have errors in them. You'll only get people to pay attention if it's difficult/impossible to repair those errors for a reasonable practitioner.

In contrast, since a program is executed by a computer, many sorts of errors will cascade.

I think the right thing to say is that a proof must be 100% conceptually sound. But a program relies on many many more bookkeeping details that must be correct or there will be bad behavior.

Re:I hate the Pumping Lemma by Mindless2112 on Monday August 19, 2013 @10:14AM (#6237304)
> Interesting argument, though I currently think correctness is more important in programming. Their proofs are hand-wavy compared to our programs.

This is where proof systems like Coq come into play. You can write code in Coq and then use Coq to formally prove properties about it -- the CompCert C compiler [1], for example.

Or you can model real-world problems in Coq and use Coq to help you prove them. Either way, proofs don't have to be hand-wavy.

[1] http://compcert.inria.fr/doc/

Re:I hate the Pumping Lemma by raverbashing on Monday August 19, 2013 @05:51AM (#6236365)
True

However, the evolution of math often goes towards generalising a certain behaviour, operation or set.

For example, first we had the natural numbers and the addition operation. Then addition was generalised as an operation on different 'objects' like matrices, equations, etc

So, yes, the strong typing idea makes sense, maybe someday math will be able to generalise addiction for any set and any object based only on their properties, regardless of what they are.

Re:I hate the Pumping Lemma by lmm on Monday August 19, 2013 @08:02AM (#6236711)
If you want to see generalization look no further than Category Theory. But it's all done "safely": you define what a category is, and prove things about it, and then declare how certain objects can be viewed as categories (somewhat like the typeclass pattern).
Re:I hate the Pumping Lemma by Nitramp on Monday August 19, 2013 @07:17AM (#6236552)
I remember a professor teaching parser construction and trying to explain the various sets (tokens, states, actions, followers) with triple nested set notation in mathematical notation. E.g. {x of {y of {z of Z| z > 0} | y != x | ...}. Completely incomprehensible.

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

Re:I hate the Pumping Lemma by abecedarius on Monday August 19, 2013 @10:38AM (#6237446)
If you'd like a code-first approach to broadly this topic (regular expressions), I wrote https://github.com/darius/regexercise and would welcome feedback.
Re:I hate the Pumping Lemma by kbutler on Monday August 19, 2013 @12:07AM (#6235562)
How many times can you use the word "and" in a row in an English sentence?

Type "Ham and eggs".

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

Now, put more space between...

Re:I hate the Pumping Lemma by sudo_robin on Monday August 19, 2013 @01:02AM (#6235703)
The real insult is that the actual underlying idea, and the proof, is shockingly simple. It is essentially the pigeonhole principle: the principle that if you put more than n pigeons into n holes then there must be a hole with more than one pigeon in.

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

Re:I hate the Pumping Lemma by andreasvc on Monday August 19, 2013 @05:12AM (#6236276)
I think it may be the punchline in many cases, but still, setting up the right pigeons and holes is what makes proving stuff nontrivial.
Re:I hate the Pumping Lemma by neic on Monday August 19, 2013 @03:55PM (#6239360)
I have an exam in this subject tomorrow, I just watched this really good explanation of the pumping lemma by Shai Simonson yesterday.

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