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?
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 &amp; Crowley, 2008, Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.