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

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

<p>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".</p>

<p><strong>Addendum:</strong> 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 <em>extended regular expressions</em> for the model with backreferences, and <em>proper regular expressions</em> 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:</p>

<p>First, <em>regex</em> and <em>rewbr</em> 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.  <em>PERL-like regular expressions</em> were also quite unwieldy. Of course, I am no native speaker, so YMMV.</p>

<p>Second, as soon as one wants to talk about both models, it is convenient to use terms that are a variation of <em>regular expression</em>, 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.</p>

<p>Third, I preferred to use a term that is already used in literature over a newly coined term, which left me the choice between <em>extended regular expressions</em> and <em>practical regular expressions</em>. 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).</p>

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

CC BY-SA 2.5
2011-01-31T13:22:01.593Z
See "On Extended Regular Expressions" by Carle and Narendran (2009) for more recent results about this "rewbr": http://portal.acm.org/citation.cfm?id=1533235
Jakob
CC BY-SA 2.5
2011-02-01T09:43:55.380Z
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
CC BY-SA 2.5
2010-09-07T14:10:40.827Z
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
CC BY-SA 2.5
2010-10-07T11:11:31.300Z
@Jörg: Actually according to [this](http://www.regular-expressions.info/posix.html) 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
CC BY-SA 2.5
2010-09-06T08:28:04.170Z
2011-02-01T10:57:52.530Z
2011-02-01T10:57:52.530Z
Dominik D. Freydenberger
<p>It is known that perl's so-called regexp is powerful enough to be Turing complete; there is even a compiler from usual program to perl regexp.</p>

<p>Hence I doubt it makes sense to search for a name for this kind of "regexps".</p>

<p>Look for example at <a href="http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm" rel="nofollow">http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm</a></p>

CC BY-SA 2.5
2010-08-24T11:48:43.743Z
Do you have some pointers?
András Salamon
CC BY-SA 2.5
2010-08-24T12:15:23.177Z
@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
CC BY-SA 2.5
2010-08-24T20:56:24.650Z
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
CC BY-SA 2.5
2010-09-10T13:45:36.730Z
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
CC BY-SA 3.0
2010-08-24T03:56:53.920Z
2015-08-13T11:04:34.570Z
2015-08-13T11:04:34.570Z
Arthur MILCHIOR
<p>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.</p>

CC BY-SA 2.5
2010-09-10T13:44:06.660Z
Not very commonly used, IMHO.
Blaisorblade
CC BY-SA 2.5
2010-09-10T19:30:09.207Z
It /is/ widely used in weighted automata theory, see http://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
CC BY-SA 2.5
2010-08-24T01:55:54.183Z
2010-08-24T01:55:54.183Z
Michaël Cadilhac
<p>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).</p>

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

CC BY-SA 2.5
2010-09-10T14:42:54.440Z
2010-09-10T14:42:54.440Z
Blaisorblade
<p>We could call them <em>pattern expressions</em>. This might introduce confusions with pattern languages, but at least these are less common.</p>

CC BY-SA 2.5
2011-02-01T09:48:44.907Z
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
CC BY-SA 2.5
2010-09-30T22:03:45.417Z
2010-09-30T22:03:45.417Z
Raphael
<p>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.</p>

<p>The power of regexes comes from backtracking, and there has been work done on automata for regular languages with backtracking.  See, in particular, Becchi &amp; Crowley, 2008, <a href="http://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf">Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions</a>.</p>

CC BY-SA 4.0
2018-07-13T20:01:26.593Z
Perl regexes have a lot more additional features than just backtracking.
reinierpost
CC BY-SA 4.0
2018-10-03T18:19:16.123Z
@reinierpost True, but I think backtracking is the most important one from a formal languages perspective.  Perl regexes have features like executing arbitrary Perl code, but I think regexes should be interpreted loosely as covering PCREs.  PCREs contain such oddities as recursive patterns, but these are dark arts, taking you far outside the realm of regular languages.  I could update my answer to cover these, though.
Charles Stewart
CC BY-SA 2.5
2010-08-24T15:02:07.960Z
I agree, something like "Perl regex" ("POSIX regex", etc.) vs. "regular language" should be clear enough to prevent any possibility of misinterpretation.
Jukka Suomela
CC BY-SA 2.5
2010-08-24T11:57:09.187Z
2010-08-24T11:57:09.187Z
Charles Stewart
<p>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.</p>

<p>For example, the “regular expression”</p>

<pre><code>/^1?$|^(11+?)\1+$/
</code></pre>

<p>created by noted Perl personality <a href="http://perl.abigail.be/">Abigail</a> (and part of <a href="http://perl5.git.perl.org/perl.git/blob/d5e45555fc406945bd8e4694adaab59e4f99120e:/t/japh/abigail.t">Perl's test suite</a> since 2002) describes a machine that accepts only composite unary numbers, but <a href="http://books.google.com/books?id=Cgooanwdo9AC&amp;lpg=PA122&amp;pg=PA122#v=onepage&amp;q&amp;f=false">exercise 4.5 (b)</a> in the third edition of Peter Linz's <a href="http://rads.stackoverflow.com/amzn/click/0763714224"><em>An Introduction to Formal Languages and Automata</em></a> has the reader use the <a href="http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages">pumping lemma</a> to prove that</p>

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

<p>is not a regular language.</p>

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

<automata-theory><pl.programming-languages><fl.formal-languages><regular-expressions><terminology>
Regular expressions aren't
Greg Bacon
# Regular expressions aren't

(Asked by: username_0 on 2010-08-23)

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?

**Tags:** automata-theory, pl.programming-languages, fl.formal-languages, regular-expressions, terminology


---

## 6 answers

### Answer by username_7 on 2010-08-24. Score: 49 | Accepted answer

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](http://www.arl.wustl.edu/~pcrowley/a25-becchi.pdf).

> **Comments:**
> **username_12**: I agree, something like "Perl regex" ("POSIX regex", etc.) vs. "regular language" should be clear enough to prevent any possibility of misinterpretation.  
> **username_11**: Perl regexes have a lot more additional features than just backtracking.  
> **username_7**: @username_11 True, but I think backtracking is the most important one from a formal languages perspective.  Perl regexes have features like executing arbitrary Perl code, but I think regexes should be interpreted loosely as covering PCREs.  PCREs contain such oddities as recursive patterns, but these are dark arts, taking you far outside the realm of regular languages.  I could update my answer to cover these, though.  

---

### Answer by username_1 on 2010-09-06. Score: 19

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.

> **Comments:**
> **username_3**: 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.  
> **username_4**: @Jörg: Actually according to [this](http://www.regular-expressions.info/posix.html) 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).  
> **username_2**: See "On Extended Regular Expressions" by Carle and Narendran (2009) for more recent results about this "rewbr": http://portal.acm.org/citation.cfm?id=1533235  
> **username_1**: 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).  

---

### Answer by username_5 on 2010-08-24. Score: 6

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

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

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

> **Comments:**
> **username_6**: Do you have some pointers?  
> **username_7**: @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.  
> **username_5**: 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.  
> **username_8**: 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.  

---

### Answer by username_9 on 2010-08-24. Score: 2

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.

> **Comments:**
> **username_8**: Not very commonly used, IMHO.  
> **username_9**: It /is/ widely used in weighted automata theory, see http://en.wikipedia.org/wiki/Rational_language .  I've seen it a good bunch of times in the field of languages over groups too.  

---

### Answer by username_8 on 2010-09-10. Score: 1

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.


---

### Answer by username_10 on 2010-09-30. Score: 0

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

> **Comments:**
> **username_1**: 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).  

---

