6
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you give a summary of what kind of operators POSIX regexes support? $\endgroup$
    – Emil Jeřábek
    Commented Jul 7, 2018 at 12:33
  • $\begingroup$ By the way, (.*)\1 is not even context-free. $\endgroup$
    – Emil Jeřábek
    Commented Jul 7, 2018 at 12:35
  • $\begingroup$ @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... $\endgroup$
    – Armin
    Commented Jul 7, 2018 at 13:09
  • $\begingroup$ @EmilJeřábek added a reference to the posix regex standard, although it isn't a particularly clear one $\endgroup$
    – Armin
    Commented Jul 7, 2018 at 13:28
  • 1
    $\begingroup$ Very similar question: cstheory.stackexchange.com/q/1047 $\endgroup$
    – Emil Jeřábek
    Commented Jul 7, 2018 at 21:55

1 Answer 1

Reset to default
7
$\begingroup$

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.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Emil Jeřábek
    Commented Jul 10, 2018 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.