<p>In [1], the authors formally define the notion of an "extended regex" with the intent of capturing the back-reference capability of POSIX/perl/emacs/etc style regexes. Exactly how closely their definition matches the exact POSIX specification is an exercise left to the reader. </p>

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

<ol>
<li>Câmpeanu, Cezar, Kai Salomaa, and Sheng Yu. "A formal study of practical regular expressions." International Journal of Foundations of Computer Science 14.06 (2003): 1007-1018.</li>
</ol>

CC BY-SA 4.0
2018-07-10T08:31:37.143Z
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
CC BY-SA 4.0
2018-07-10T01:37:16.323Z
2018-07-10T01:37:16.323Z
mhum
<p>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)?</p>

<p>Proof that POSIX regex is more powerful than type 3:</p>

<p><code>(a+)b(\1)</code> which recognizes $\{ a^nba^n | n \geq 1 \}$</p>

<p>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): <a href="http://pubs.opengroup.org/onlinepubs/007908799/xbd/re.html#tag_007_003" rel="noreferrer">regex manual</a></p>

<p>Emil Jeřábek mentioned that POSIX regex is not even completely contained in type 2 languages because <code>(.*)\1</code> 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.</p>

CC BY-SA 4.0
2018-07-07T12:33:18.150Z
Can you give a summary of what kind of operators POSIX regexes support?
Emil Jeřábek
CC BY-SA 4.0
2018-07-07T12:35:43.200Z
By the way, (.*)\1 is not even context-free.
Emil Jeřábek
CC BY-SA 4.0
2018-07-07T13:09:54.170Z
@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
CC BY-SA 4.0
2018-07-07T13:28:16.573Z
@EmilJeřábek added a reference to the posix regex standard, although it isn't a particularly clear one
Armin
CC BY-SA 4.0
2018-07-07T21:55:34.523Z
Very similar question: https://cstheory.stackexchange.com/q/1047
Emil Jeřábek
<complexity-classes><regular-expressions>
How powerful is POSIX regex
Armin
# How powerful is POSIX regex

(Asked by: username_0 on 2018-07-07)

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](http://pubs.opengroup.org/onlinepubs/007908799/xbd/re.html#tag_007_003)

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.

**Tags:** complexity-classes, regular-expressions
> **Comments:**
> **username_1**: Can you give a summary of what kind of operators POSIX regexes support?  
> **username_1**: By the way, (.*)\1 is not even context-free.  
> **username_0**: @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...  
> **username_0**: @EmilJeřábek added a reference to the posix regex standard, although it isn't a particularly clear one  
> **username_1**: Very similar question: https://cstheory.stackexchange.com/q/1047  

---

## 1 answers

### Answer by username_2 on 2018-07-10. Score: 7 | Accepted answer

In [1], the authors formally define the notion of an "extended regex" with the intent of capturing the back-reference capability of POSIX/perl/emacs/etc style regexes. Exactly how closely their definition matches the exact POSIX specification is an exercise left to the reader.

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.

1. Câmpeanu, Cezar, Kai Salomaa, and Sheng Yu. "A formal study of practical regular expressions." International Journal of Foundations of Computer Science 14.06 (2003): 1007-1018.

> **Comments:**
> **username_1**: 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}$.  

---

