News for hackers. Stuff that matters.
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.