<p>The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex <code>/(.*)\1/</code> will capture the language $L = \{ ww | w \in \Sigma^*\}$, which is not context-free. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \{ ww | w \in \Sigma^*, \mid w \mid \le K\}$, which for any fixed $K$ is a regular expression again. </p>

<p>But in principle, regexps as specified are more powerful than regular languages, as <a href="https://cstheory.stackexchange.com/questions/448/regular-expressions-arent">this related question</a> discusses in much more detail (with a nifty example as well). </p>

CC BY-SA 2.5
2010-09-08T16:27:39.983Z
Wouldn't {ww|w ∈ Σ∗,∣w∣≤K} would be a CSL or TM recognizable??
dhruvbird
CC BY-SA 2.5
2010-09-08T16:34:24.963Z
arggh. should have done ww^R. will fix. thanks
Suresh Venkat
CC BY-SA 2.5
2010-09-08T17:18:52.377Z
Actually, I had a question about this. Is ww a CSL or is turing recognizable? I wasn't (yet) able to come up with a LBA for it, so just wondering...
dhruvbird
CC BY-SA 2.5
2010-09-30T18:00:03.323Z
If the length is unrestricted, the copy language $\{ww : w \in \Sigma^*\}$ is context-sensitive. (It is even "mildly context-sensitive", which is a notion that recently gained importance in Natural Language Processing.) A context-sensitive grammar (and thus, an LBA) for it is not easy to find, but can be found in many textbooks and teaching material on the web (use any search engine for "copy language context-sensitive").
DaniCL
CC BY-SA 4.0
2010-09-07T16:21:08.163Z
2018-07-16T08:25:18.027Z
2018-07-16T08:25:18.027Z
Suresh Venkat
<p>One interesting result, taken from <a href="https://cstheory.stackexchange.com/questions/448/regular-expressions-arent">this other question</a>, also linked by Suresh Venkat, is that "Practical" regexps are NP-complete, and thus they should be equivalent in power to SAT.</p>

<p>Being a non-expert, while I agree that intuitively "regexes with backreferences don't seem to be sufficient to match the balanced parenthesis language", there is something strange going on. NP-completeness implies that any NP problem can be polynomially reduced to a regexp, so probably there is just a polynomial reduction from the "balanced parentheses" language to one recognizable with regexps. But again, there might be some absurd regexp to parse a CFL, since they can even parse non-prime unary numbers!</p>

<p>Probably, the lesson is that complexity classes and language classes are not comparable, in general. Which also suggests rephrasing your question, to reference the Chomsky hierarchy rather than the "complexity scale" (even if, to be fair, I was not confused by that).</p>

<p>Charles Stewart writes:</p>

<blockquote>
  <p>Aho, 1990, "Algorithms for finding
  patterns in strings" shows that the
  membership problem for regular
  languages with backtracking is NP
  complete.</p>
</blockquote>

<p>A partial preview (at least of the statement) can be found <a href="http://books.google.it/books?id=-X39_rA3VSQC&amp;pg=PA289" rel="nofollow noreferrer">on Google Books</a>, at page 289, and a bibliographic reference to the paper can be found <a href="http://portal.acm.org/citation.cfm?id=114877" rel="nofollow noreferrer">here</a>. Note that in the paper, rewbr stands for Regular Expression With BackReferences.</p>

CC BY-SA 2.5
2010-09-10T15:36:48.650Z
2010-09-10T15:36:48.650Z
2017-04-13T12:32:28.080Z
Blaisorblade
<p>PCRE, the most popular implementation of "regular expressions" also implements recursive patterns, which go beyond backreferences. A questions about their complexity <a href="https://stackoverflow.com/questions/4840988/the-recognizing-power-of-modern-regexes">has just been asked</a> at Stackoverflow. According to the practical-in-depth-answer by Perl guru brian d foy, this makes PCRE as powerful as context-free grammars. However the syntax is awful compared to Backus-Naur Form.</p>

CC BY-SA 2.5
2011-01-31T13:50:53.523Z
2011-01-31T13:50:53.523Z
2017-05-23T12:40:09.333Z
Jakob
<p>I don't think that the real problem is the question of what unbounded means; this is no worse than any other situation in parsing.</p>

<p>The trouble lies with characterizing backreferences, which are both very powerful and very limited: they allow description of some non-context-free languages, without allowing some context-free languages. For example, the regex <code>(a*)b\1b\1</code> matches strings of the form $a^n \cdot b \cdot a^n \cdot b \cdot a^n$, and you can use the pumping lemma to show this is not a context-free language. However, on the other hand, regexes with backreferences don't seem to be sufficient to match the balanced parenthesis language, which is the prototypical context-free language.</p>

<p>It's easy enough to give a denotational semantics saying what strings are in a language to regexes, but giving a good automata-theoretic characterization seems much more challenging. It's something like a register machine, into whose registers you can copy substrings of your input, and which you can use to test your current string against, but for which you lack the ability to modify these registers. </p>

<p>People doing finite model theory have a bunch of funky machine models, and it would be interesting to know if this corresponds to any of their models.</p>

CC BY-SA 2.5
2010-09-08T10:56:01.730Z
2010-09-08T10:56:01.730Z
Neel Krishnaswami
<p>Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do these features let them parse statements that can't be described with a finite, non-pushdown automaton? How much closer to turing complete does this make them if they can?</p>

CC BY-SA 2.5
2011-02-03T02:48:03.120Z
Related (and possibly incorrect): http://stackoverflow.com/questions/2974210/does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions/2991587#2991587
Aryabhata
CC BY-SA 2.5
2010-09-08T17:07:24.907Z
A closely related question: Do we have anything interesting between "regexes with backreferences" and "regexes that can contain arbitrary program code"? For example, are regexes with *backreferences and lookahead/lookbehind* strictly more expressive than regexes with backreferences but no lookahead/lookbehind? What about "Special Backtracking Control Verbs" in Perl?
Jukka Suomela
<automata-theory><regular-expressions><fl.formal-languages>
Where do most REGEX implementations fall on the complexity scale?
Dan Monego
# Where do most REGEX implementations fall on the complexity scale?

(Asked by: username_0 on 2010-09-07)

Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do these features let them parse statements that can't be described with a finite, non-pushdown automaton? How much closer to turing complete does this make them if they can?

**Tags:** automata-theory, regular-expressions, fl.formal-languages
> **Comments:**
> **username_2**: A closely related question: Do we have anything interesting between "regexes with backreferences" and "regexes that can contain arbitrary program code"? For example, are regexes with *backreferences and lookahead/lookbehind* strictly more expressive than regexes with backreferences but no lookahead/lookbehind? What about "Special Backtracking Control Verbs" in Perl?  
> **username_1**: Related (and possibly incorrect): http://stackoverflow.com/questions/2974210/does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions/2991587#2991587  

---

## 4 answers

### Answer by username_8 on 2010-09-08. Score: 19 | Accepted answer

I don't think that the real problem is the question of what unbounded means; this is no worse than any other situation in parsing.

The trouble lies with characterizing backreferences, which are both very powerful and very limited: they allow description of some non-context-free languages, without allowing some context-free languages. For example, the regex `(a*)b\1b\1` matches strings of the form $a^n \cdot b \cdot a^n \cdot b \cdot a^n$, and you can use the pumping lemma to show this is not a context-free language. However, on the other hand, regexes with backreferences don't seem to be sufficient to match the balanced parenthesis language, which is the prototypical context-free language.

It's easy enough to give a denotational semantics saying what strings are in a language to regexes, but giving a good automata-theoretic characterization seems much more challenging. It's something like a register machine, into whose registers you can copy substrings of your input, and which you can use to test your current string against, but for which you lack the ability to modify these registers.

People doing finite model theory have a bunch of funky machine models, and it would be interesting to know if this corresponds to any of their models.


---

### Answer by username_3 on 2010-09-07. Score: 9

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex `/(.*)\1/` will capture the language $L = \{ ww | w \in \Sigma^\*\}$, which is not context-free. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L\_K = \{ ww | w \in \Sigma^\*, \mid w \mid \le K\}$, which for any fixed $K$ is a regular expression again.

But in principle, regexps as specified are more powerful than regular languages, as [this related question](https://cstheory.stackexchange.com/questions/448/regular-expressions-arent) discusses in much more detail (with a nifty example as well).

> **Comments:**
> **username_4**: Wouldn't {ww|w ∈ Σ∗,∣w∣≤K} would be a CSL or TM recognizable??  
> **username_3**: arggh. should have done ww^R. will fix. thanks  
> **username_4**: Actually, I had a question about this. Is ww a CSL or is turing recognizable? I wasn't (yet) able to come up with a LBA for it, so just wondering...  
> **username_5**: If the length is unrestricted, the copy language $\{ww : w \in \Sigma^*\}$ is context-sensitive. (It is even "mildly context-sensitive", which is a notion that recently gained importance in Natural Language Processing.) A context-sensitive grammar (and thus, an LBA) for it is not easy to find, but can be found in many textbooks and teaching material on the web (use any search engine for "copy language context-sensitive").  

---

### Answer by username_6 on 2010-09-10. Score: 5

One interesting result, taken from [this other question](https://cstheory.stackexchange.com/questions/448/regular-expressions-arent), also linked by Suresh Venkat, is that "Practical" regexps are NP-complete, and thus they should be equivalent in power to SAT.

Being a non-expert, while I agree that intuitively "regexes with backreferences don't seem to be sufficient to match the balanced parenthesis language", there is something strange going on. NP-completeness implies that any NP problem can be polynomially reduced to a regexp, so probably there is just a polynomial reduction from the "balanced parentheses" language to one recognizable with regexps. But again, there might be some absurd regexp to parse a CFL, since they can even parse non-prime unary numbers!

Probably, the lesson is that complexity classes and language classes are not comparable, in general. Which also suggests rephrasing your question, to reference the Chomsky hierarchy rather than the "complexity scale" (even if, to be fair, I was not confused by that).

Charles Stewart writes:

> Aho, 1990, "Algorithms for finding
> patterns in strings" shows that the
> membership problem for regular
> languages with backtracking is NP
> complete.

A partial preview (at least of the statement) can be found [on Google Books](http://books.google.it/books?id=-X39_rA3VSQC&pg=PA289), at page 289, and a bibliographic reference to the paper can be found [here](http://portal.acm.org/citation.cfm?id=114877). Note that in the paper, rewbr stands for Regular Expression With BackReferences.


---

### Answer by username_7 on 2011-01-31. Score: 4

PCRE, the most popular implementation of "regular expressions" also implements recursive patterns, which go beyond backreferences. A questions about their complexity [has just been asked](https://stackoverflow.com/questions/4840988/the-recognizing-power-of-modern-regexes) at Stackoverflow. According to the practical-in-depth-answer by Perl guru brian d foy, this makes PCRE as powerful as context-free grammars. However the syntax is awful compared to Backus-Naur Form.


---

