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

41–50 of 52 posts

Re: I hate the Pumping Lemma

#41

Post by lotsofcows »

jessaustin wrote: post #40
lotsofcows wrote: post #33

Earlier quoted context omitted.

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.

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

#42

Post by jessaustin »

lotsofcows wrote: post #41
jessaustin wrote: post #40

Earlier quoted context omitted.

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

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.

"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

#43

Post by hyperpape »

pseut wrote: post #32
calibraxis wrote: post #28

Earlier quoted context omitted.

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.

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

#44

Post by hyperpape »

anaphor wrote: post #25
kingkilr wrote: post #10

Earlier quoted context omitted.

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.

Do you mean that some regex implementations allow you to parse context-free grammars?

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

#45

Post by mcguire »

kingkilr wrote: post #3

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.

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

#46

Post by mcguire »

zidar wrote: post #13

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

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

#47

Post by xyzzyz »

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)

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

#48

Post by contravert »

abecedarius wrote: post #38
sergiosgc wrote: post #31

Earlier quoted context omitted.

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.

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

#50

Post by sergiosgc »

abecedarius wrote: post #38
sergiosgc wrote: post #31

Earlier quoted context omitted.

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.

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-...
Post reply on HN