Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
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? –  Jukka Suomela Sep 8 '10 at 17:07
    
Related (and possibly incorrect): stackoverflow.com/questions/2974210/… –  Aryabhata Feb 3 '11 at 2:48
add comment

4 Answers 4

up vote 13 down vote accepted

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.

share|improve this answer
add comment

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 a CFL much more powerful. 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 discusses in much more detail (with a nifty example as well).

share|improve this answer
    
Wouldn't {ww|w ∈ Σ∗,∣w∣≤K} would be a CSL or TM recognizable?? –  dhruvbird Sep 8 '10 at 16:27
    
arggh. should have done ww^R. will fix. thanks –  Suresh Venkat Sep 8 '10 at 16:34
    
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 Sep 8 '10 at 17:18
1  
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 Sep 30 '10 at 18:00
add comment

One interesting result, taken from this other question, 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, at page 289, and a bibliographic reference to the paper can be found here. Note that in the paper, rewbr stands for Regular Expression With BackReferences.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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