# How powerful is POSIX regex

The set of languages recognized by POSIX regex is a true superset of type 3 languages. But how powerful is POSIX regex really? Is it in an already known class? Is it its own class? If so, what is the next bigger class (for some context)?

Proof that POSIX regex is more powerful than type 3:

(a+)b(\1) which recognizes $\{ a^nba^n | n \geq 1 \}$

I haven't found a really good description of what features POSIX regex allows but this is one link that lists all features (as far as I know): regex manual

Emil Jeřábek mentioned that POSIX regex is not even completely contained in type 2 languages because (.*)\1 is $\{ ww | w \in \Sigma^* \}$. So, it recognizes all type 3 languages, some type 2 languages and some type 1 languages, maybe even some type 0 languages.

• Can you give a summary of what kind of operators POSIX regexes support? – Emil Jeřábek Jul 7 '18 at 12:33
• By the way, (.*)\1 is not even context-free. – Emil Jeřábek Jul 7 '18 at 12:35
• @EmilJeřábek you're right, so it has to be its own class that contains true subsets of type 2 and type 1 languages, maybe even type 0... – Armin Jul 7 '18 at 13:09
• @EmilJeřábek added a reference to the posix regex standard, although it isn't a particularly clear one – Armin Jul 7 '18 at 13:28
• Very similar question: cstheory.stackexchange.com/q/1047 – Emil Jeřábek Jul 7 '18 at 21:55

Under their definition, extended regexes are a proper subset of Type 1 (context-sensitive) languages and incomparable with Type 2 (context-free) languages. They show that extended regexes are a subset of Type 1 languages by showing how to construct an equivalent LBA for any extended regex. They prove that they're incomparable with Type 2 languages by showing that $\{a^nba^nba^n|n \geq 1\}$ (which is not context-free) can be recognized by an extended regex while $\{a^n b^n | n \geq 0\}$ (which is context-free) cannot.
• I think the inclusion in context-sensitive languages can be shown in an easier way by noting that parsing of a string with respect to a fixed regex with backereferences can be done in $\mathrm{NTime}(n)\subseteq\mathrm{NSpace}(n)=\mathrm{CSL}$. – Emil Jeřábek Jul 10 '18 at 8:31