4
$\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.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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