Regular expressions aren't
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.