4 ms·
Some regexp dialects are actually Turing complete from what I've heard. EDIT: Yes this seems to be wrong
by im3w1l 13y ago
Some regexp dialects are actually Turing complete from what I've heard.
EDIT: Yes this seems to be wrong
- kingkilr 13y agoI'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.
- chimeracoder 13y ago> they're at least as powerful as a PDA. PCREs (ie, the regular expressions that Perl uses) are NP-hard, since they allow backreferences.
- kazagistar 13y agoI think you are confusing complexity and computability class.
- anaphor 13y agoDo you mean that some regex implementations allow you to parse context-free grammars?
- hyperpape 13y agoMost 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-most-regex-implementations-fall-on-the-complexity-scale http://cstheory.stackexchange.com/questions/1047/where-do-mo...
- anaphor 13y agoYeah, I should've said "all". I know that you can describe regular grammars using languages designed for CFGs, like BNF.