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.
[ Parent
| on HN ]
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.
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...