Regular expressions, deterministic finite automata, and nondeterministic finite automata are all equivalent[0][1]. All three of these representations are capab

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 https://www.perlmonks.org/?node_id=809842