Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I hate the Pumping Lemma

bosker.wordpress.com

Post reply on HN
Print view View original

31–40 of 52 posts

Re: I hate the Pumping Lemma

#31

Post by sergiosgc »

xyzzyz wrote: post #15

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 wi…

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

#32

Post by pseut »

calibraxis wrote: post #28
lmm wrote: post #22

Earlier quoted context omitted.

More than any other field, correctness is important in mathematics, and thus strong typing is useful, even essential.

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…

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

#33

Post by lotsofcows »

jessaustin wrote: post #30
lotsofcows wrote: post #24

Earlier quoted context omitted.

"Buffalo Buffalo Buffalo"?

Actually even "Buffalo buffalo." is a complete sentence.

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

#34

Post by stephencanon »

lotsofcows wrote: post #33
jessaustin wrote: post #30

Earlier quoted context omitted.

Actually even "Buffalo buffalo." is a complete sentence.

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.

Yes, ignoring case. There’s no case in spoken language, so that’s quite reasonable, really.

Re: I hate the Pumping Lemma

#35

Post by stephencanon »

chimeracoder wrote: post #4

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 "J…

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

#36

Post by [deleted] »

lotsofcows wrote: post #33
jessaustin wrote: post #30

Earlier quoted context omitted.

Actually even "Buffalo buffalo." is a complete sentence.

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.

[deleted]

Re: I hate the Pumping Lemma

#37

Post by Mindless2112 »

calibraxis wrote: post #28
lmm wrote: post #22

Earlier quoted context omitted.

More than any other field, correctness is important in mathematics, and thus strong typing is useful, even essential.

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…

> 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

#38

Post by abecedarius »

sergiosgc wrote: post #31
xyzzyz wrote: post #15

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 wi…

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)

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

#39

Post by abecedarius »

Nitramp wrote: post #26

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 t…

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

#40

Post by jessaustin »

lotsofcows wrote: post #33
jessaustin wrote: post #30

Earlier quoted context omitted.

Actually even "Buffalo buffalo." is a complete sentence.

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.

Yeah I think you have to ignore case. The only word that needs to be capitalized is the first one in the sentence.
Post reply on HN