Re:A Perl Regular Expression That Matches Prime Numbers
by sp332 on Sunday December 25, 2011 @04:11PM
(#3391603)
Yeah, if the title wasn't clear enough, this isn't a "regular expression" in the Computer Science definition (type-3 in the Chomsky hierarchy). It's a Perl regular expression, so it supports context-free grammars (type-2) I think. http://en.wikipedia.org/wiki/Chomsky_hierarchy
[ Parent
| on HN ]
Re:A Perl Regular Expression That Matches Prime Numbers
by nikic on Sunday December 25, 2011 @04:13PM
(#3391606)
Incidentally it supports quite a bit more. Even the less powerful Perl Compatible Regular Expressions (PCRE), which are used by PHP, can also easily handle context sensitive grammars (type 1): http://stackoverflow.com/questions/7434272/match-an-bn-cn-e-...
Re:A Perl Regular Expression That Matches Prime Numbers
by theshadow on Sunday December 25, 2011 @09:38PM
(#3392079)
Perl regular expressions probably accept more than just context-free grammars since the language that accepts prime numbers is not Context-Free, you can't build a pushdown automaton for such a language, there is a relatively trivial proof of this using the pumping lemma for context-free languages.