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

11–20 of 52 posts

Re: I hate the Pumping Lemma

#11

Post by chimeracoder »

kingkilr wrote: post #10
im3w1l wrote: post #9

Earlier quoted context omitted.

Some regexp dialects are actually Turing complete from what I've heard. EDIT: Yes this seems to be wrong

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.

> 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

#12

Post by TheZenPsycho »

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.

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

#13

Post by zidar »

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

#14

Post by kbutler »

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

#15

Post by xyzzyz »

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

#16

Post by sudo_robin »

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

#17

Post by kazagistar »

chimeracoder wrote: post #11
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.

> they're at least as powerful as a PDA. PCREs (ie, the regular expressions that Perl uses) are NP-hard, since they allow backreferences.

I think you are confusing complexity and computability class.

Re: I hate the Pumping Lemma

#18

Post by H3g3m0n »

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

#19

Post by ronaldx »

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 don't think this explains why the pumping lemma works for all strings (above a required length)?

Re: I hate the Pumping Lemma

#20

Post by andreasvc »

sudo_robin wrote: post #16

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.

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