# Regular expressions aren't

Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton.

For example, the “regular expression”

/^1?$|^(11+?)\1+$/


created by noted Perl personality Abigail (and part of Perl's test suite since 2002) describes a machine that accepts only composite unary numbers, but exercise 4.5 (b) in the third edition of Peter Linz's An Introduction to Formal Languages and Automata has the reader use the pumping lemma to prove that

$\mathcal{L} = \left\{ a^n : n\ \mathrm{is\ not\ a\ prime\ number} \right\}$

is not a regular language.

In contexts where the distinction is important, what should we call the strictly more powerful expressions?

-
I beg your pardon, but if I read correctly your regexp, it's the "non prime" number, and not only the composite one; since it also accept zero and one "1". –  Arthur MILCHIOR Aug 24 '10 at 2:07
@arthur.mi Nice catch! Thanks! –  Greg Bacon Aug 24 '10 at 2:30
You should state where you found this perl script as a nod to the original (highly talented!) author. –  muad Sep 30 '10 at 22:50

Larry Wall proposed that we use "regular expression" for the formalism Kleene proposed, and "regex" for expressions for the widely used extensions. It's a fairly widely followed convention. If you want to make it clear that you are talking about regular expressions in the formal languages sense, it is usually not difficult to translate into talk of regular languages.

The power of regexes comes from backtracking, and there has been work done on automata for regular languages with backtracking. See, in particular, Becchi & Crowley, 2008, Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.

-
I agree, something like "Perl regex" ("POSIX regex", etc.) vs. "regular language" should be clear enough to prevent any possibility of misinterpretation. –  Jukka Suomela Aug 24 '10 at 15:02

These expressions have been examined by Aho (Handbook of Theoretical Computer Science, Vol. A, Chp. 5) and Campeanu, Salomaa, Yu ("A formal study of practical regular expressions", International Journal of Foundations of Computer Science, 14:1007–1018, 2003), as well as some of follow-up papers.

Aho calls the more powerful expressions "rewbr" (regular expression with backreferences), Campeanu et al. use "extended regular expression" as well as "practical regular expression". As it seems, "extended regular expression" is the term most commonly used in recent literature.

Building on the term "rational expression" from the French school, and considering the fact that those expressions are used in the real world, I myself like "real expression".

Addendum: A chapter in my PhD thesis deals with this class of formal languages (the corresponding paper is due to appear at STACS 2011). While writing that chapter and the paper, I experimented with various terms. Finally, I decided to use extended regular expressions for the model with backreferences, and proper regular expressions for the nice and normal regular expressions. As it is quite annoying to change the terminology in a paper that is already completely (or mostly) written, I think that some might be interested in the experiences that led to my choice:

First, regex and rewbr don't really roll of the tongue, and using them again and again in the course of a whole paper got really tiresome to write and read, in particular when using any of the possible plural forms. PERL-like regular expressions were also quite unwieldy. Of course, I am no native speaker, so YMMV.

Second, as soon as one wants to talk about both models, it is convenient to use terms that are a variation of regular expression, as this allows one to emphasize similarity or differences as needed (e.g., "a regular expression, be it proper or extended"). Furthermore, this allows one to easily emphasize the special case of "extended regular expressions without backreferences", when talking about special cases in the whole class, instead of comparing different models.

Third, I preferred to use a term that is already used in literature over a newly coined term, which left me the choice between extended regular expressions and practical regular expressions. The second choice implied (at least implicitly) that proper regular expressions are somehow impractical, which felt rather weird (especially as Google's RE2 does not use backrefs, and appears to be quite practical).

Of course, this choice is only my "personal local maximum", and depending on ones needs, other choices might be more appropriate.

-
Unfortunately, the term extended regular expression is already taken by POSIX, which distinguishes between basic regular expression (BRE) and extended regular expression (ERE), both of which are extended regular expressions according to your definition. –  Jörg W Mittag Sep 7 '10 at 14:10
@Jörg: Actually according to this neither extended nor basic POSIX regular expressions are more powerful than regular regular expressions. And pure (non-GNU) BRE seem to actually be less powerful than regular expressions (missing an alternation operator). –  sepp2k Oct 7 '10 at 11:11
See "On Extended Regular Expressions" by Carle and Narendran (2009) for more recent results about this "rewbr": portal.acm.org/citation.cfm?id=1533235 –  Jakob Jan 31 '11 at 13:22
Further recent results on this language class: "On the intersection of regex languages with regular languages" by Campeanu and Santean (TCS 410, 2009) "A Polynomial Time Match Test for Large Classes of Extended Regular Expressions" by Reidenbach and Schmid (CIAA 2010), and "Extended Regular Expressions: Succinctness and Decidability" (by me, due to appear at STACS 2011). –  Dominik D. Freydenberger Feb 1 '11 at 9:43

It is known that perl's so-called regexp is powerfull enough to be Turing complete; there is even a compiler from usual program to perl regexp.

Hence I doubt it makes sens to search for a name for this kind of "regexps".

Look for example at http://search.cpan.org/~asavige/Acme-EyeDrops-1.55/lib/Acme/EyeDrops.pm

-
Do you have some pointers? –  András Salamon Aug 24 '10 at 11:48
@András: I think Arthur is talking about Perl's ?{CODE} directive, that allows pattern expressions to interleave program code in regular expressions. I understand that PCREs are ususally defined as being the "declarative" part of the language, the whole language being called the pattern language. According to WP, Aho, 1990, "Algorithms for finding patterns in strings" shows that the membership problem for regular languages with backtracking is NP complete. There are no other hard features to declarative PCREs. –  Charles Stewart Aug 24 '10 at 12:15
I added the link; I didn't look at the source code, so i do not really know how it works and if there is any proof that the compilation is really correct. –  Arthur MILCHIOR Aug 24 '10 at 20:56
Sorry, but according to your argument, since lambda-calculus is Turing-complete, it did not make sense to search a name for it. Same for all other Turing-complete computation formalisms and languages. More to the point, Turing-completeness does not describe how expressive a language is, so it makes no sense to identify languages just because they are Turing-complete. My example about lambda-calculus was an extreme one, of course. –  Blaisorblade Sep 10 '10 at 13:45

I think the best term for "regular expression in the context of automata" is "rational expression", as used, say, in Sakarovitch's Elements of Automata Theory, or the Handbook of Weighted Automata.

-
Not very commonly used, IMHO. –  Blaisorblade Sep 10 '10 at 13:44
It /is/ widely used in weighted automata theory, see en.wikipedia.org/wiki/Rational_language . I've seen it a good bunch of times in the field of languages over groups too. –  Michaël Cadilhac Sep 10 '10 at 19:30

Given the other answers, I would suggest that "regular languages" is safe, and after briefly remarking the difference, to talk about "practical regular expressions" for regexs (with backtracking).

Also note that the same regexp, as a regular expressions and as a practical one, can have different semantics, because in the latter case semantics are defined in term of backtracking, with different results. Details would be off-topic, but I will answer if you ask another question on that (maybe on SO rather than here, dunno) and notify me through a comment.

-

We could call them pattern expressions. This might introduce confusions with pattern languages, but at least these are less common.

-
In principle, I agree with your reasoning, but Campeanu, Santean, and Yu have already used the term pattern expressions to denote a similar class of languages with a "cleaner" definition (see "Pattern expressions and pattern automata", IPL 92 (2004). –  Dominik D. Freydenberger Feb 1 '11 at 9:48