# What is the computational complexity of “real-life” regular expressions?

Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), and the Kleenee star x*.

"Real-life" regular expressions as used in programming usually have a lot more operations available; amongst others, quantification x{n}, negation [^x], positive and negative lookahead x(?=y), or back-reference \n.

There is a famous post on SO stating that regular expressions can not be used to parse HTML for the reason that HTML is not a regular language.

My question is: Is this accurate? Do "real-life" regular expressions, say the selection defined in the Java docs, really have the same expressive power as regular expressions as understood in formal language theory; or do the additional constructs, although possibly not strong enough to capture HTML and the like, put common regular expressions further up on the Chomsky scale than just Type 3 languages?

I would imagine the proof of the computational equality of the two would amount to showing that each operation available for the common regexp is just syntactic sugar and can be expressed by means of the 3 basic operations (concatenation, alternation, Kleene start) alone; but I am finding it hard to see how one would e.g. simulate back-reference with classic regexes alone.

• Quantification and negations are just syntactic sugar since $x\{n, m\}$ is equivalent to $\underbrace{xx\dots x}_{n \text{ times}}\underbrace{(x+\varepsilon)(x+\varepsilon)\dots (x+\varepsilon)}_{m-n \text{ times}}$ and $[\text{^} x]$ is equivalent to $(\Sigma \setminus \{x\})$ – Steven Jun 23 at 14:07
• @Steven I see the quantification translation, thanks. But $\Sigma \setminus \{x\}$ is not a regexp. I assume that would be translated as alternation between all symbols in the alphabet different from $x$, which is possible because $\Sigma$ is always finite? – lemontree Jun 24 at 17:41
• Yes, by $\Sigma \setminus \{x\}$ I mean listing out all the symbols in that set. As you point out this is always possibile. – Steven Jun 24 at 18:15

The following extended regular expression matches the language $$\{ ww : w \in \Sigma^* \}$$:

$$\texttt{^$.*$\\1\\\}$$

This language is neither regular nor context-free.

Matching using extended regular expressions is NP-complete; see for example this paper, which discusses efficient algorithms in some special cases.

• Thank you. So it can be said that the generative power of extended regexes is at least between context-sensitive and recursively enumerable? – lemontree Jun 23 at 15:11
• The extended regular expression is $$\texttt{^(.*)\\1\$$}$$if you're using a Posix library which allows back references in EREs. (Posix doesn't.)$$\texttt{^$.*$\\1$\$$}$$ is a Posix basic regular expression. (I used $\ to avoid the visible backslash before the \$.) – rici Jun 23 at 16:10
• More specifically, although the back-reference sounds "extended", it's actually part of the original "basic regular expression" (BRE) language implemented by Unix regex libraries; that language did not have alternation, so it had serious limitations (although it also could exceed Type 2, as you say). Eventually, the specification was updated to avoid the need for so much falling timber, creating "Extended Regular Expressions (EREs)". In the ERE specification, back-references were eliminated, but most libraries continue to allow them. (Also, most libraries allow alternation in BREs.) – rici Jun 23 at 16:25
• @rici But surely that BRE language can't only have had concatenation and starring then? So it was not the classic regexp as described above? – lemontree Jun 24 at 17:37
• @lemontree: It was not, correct. You don't have to take my word for it. Documentation abounds. Read man 7 regex on your computer if you use linux, or online on the Linux man-pages project site. (Here's a quote: "Obsolete ('basic') regular expressions differ in several respects. '|', '+', and '?' are ordinary characters and there is no equivalent for their functionality.") – rici Jun 24 at 20:06