[charlesdaniels]

Regular expressions, deterministic finite automata, and nondeterministic finite automata are all equivalent[0][1].

All three of these representations are capable of describing any regular language (set of symbol sequences, or more intuitively a set of strings), and the fact that a language can be described by an NFA, DFA, or RE implies that it is regular.

I am not hugely familiar with Pearl's "extended regular expression" system, however I was under the understanding that the set of languages it can recognize is a superset of the set of all regular languages. Based on [2], it would appear that Perl regexes can recognize all regular languages, and parts of the set of all Turing-recognizable languages.

0 - Introduction to the Theory of Computation 3/e, Michael Sipser, Thm 1.39, pp. 55.

1 - Introduction to the Theory of Computation 3/e, Michael Sipser, Thm 1.54, pp. 67.

2- https://www.perlmonks.org/?node_id=809842

[beecafe]

FWIW the equivalence between NFA and DFA requires an exponential space increase to encode the NFA as a DFA, with an exponential space blow up you can encode a lot of things as DFAs (I'm pretty sure you could encode a Turing machine that uses bounded space on the tape as a DFA with exponentially more space, "just" make each possible configuration one state in the DFA)