Hacker News Reader

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

View on HN

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-...

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.

Reply on news.ycombinator.com