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?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ 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? $\endgroup$– Jukka SuomelaCommented Sep 8, 2010 at 17:07
-
$\begingroup$ Related (and possibly incorrect): stackoverflow.com/questions/2974210/… $\endgroup$– AryabhataCommented Feb 3, 2011 at 2:48
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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.
answered Sep 8, 2010 at 10:56
$\begingroup$
$\endgroup$
4
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 discusses in much more detail (with a nifty example as well).
answered Sep 7, 2010 at 16:21
-
$\begingroup$ Wouldn't {ww|w ∈ Σ∗,∣w∣≤K} would be a CSL or TM recognizable?? $\endgroup$ Commented Sep 8, 2010 at 16:27
-
$\begingroup$ arggh. should have done ww^R. will fix. thanks $\endgroup$ Commented Sep 8, 2010 at 16:34
-
$\begingroup$ 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... $\endgroup$ Commented Sep 8, 2010 at 17:18
-
1$\begingroup$ 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"). $\endgroup$– DaniCLCommented Sep 30, 2010 at 18:00
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
