4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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\})$ $\endgroup$
    – Steven
    Jun 23, 2020 at 14:07
  • $\begingroup$ @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? $\endgroup$
    – Natalie Clarius
    Jun 24, 2020 at 17:41
  • $\begingroup$ Yes, by $\Sigma \setminus \{x\}$ I mean listing out all the symbols in that set. As you point out this is always possibile. $\endgroup$
    – Steven
    Jun 24, 2020 at 18:15

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. So it can be said that the generative power of extended regexes is at least between context-sensitive and recursively enumerable? $\endgroup$
    – Natalie Clarius
    Jun 23, 2020 at 15:11
  • 1
    $\begingroup$ 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 $.) $\endgroup$
    – rici
    Jun 23, 2020 at 16:10
  • $\begingroup$ 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.) $\endgroup$
    – rici
    Jun 23, 2020 at 16:25
  • $\begingroup$ @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? $\endgroup$
    – Natalie Clarius
    Jun 24, 2020 at 17:37
  • $\begingroup$ @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.") $\endgroup$
    – rici
    Jun 24, 2020 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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