Fun trivia: DFAs and NFAs are computationally equivalent. Any NFA can be converted into an equivalent DFA.
https://en.wikipedia.org/wiki/Deterministic_finite_automaton
> ...not as powerful as regex libs built with a non-regular language...
Is there something that perl regex's can do, in non-crazy everyday use-cases, that can't be done by something like re2?
I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out yet though.
The various features in PERL allow you to emulate context-free languages. There is a proof somewhere, but it's trivial to see you can use backreferences to parse languages with well-nested parens.
Languages of well-nested parens are known to be non-regular, and thus impossible to write with regular expressions.
Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete.
Are you reffering to the programming language or PCRE? I would expect PCRE to be a simple superset of the regex grammar, and thus the optimization is complete and trivial: the appearance of any PCRE constructs denies the use of the DFA engine; otherwise, use the DFA.
I don’t see how you could ever optimize out eg a backreference (converting to some equivalent regex) without already having parsed the subject text and determining it to be unnecessary. In which case, I don’t see how the inability to determine regularity of a context-free grammar is relevant (if you’re referring to the context-free nature of PCRE’s grammar, its not clear to me why you should care where the regex input grammar itself is regular/context-free, and why you’d want to convert PCRE to a regular grammar; optimizing a regex search shouldn’t care about the grammar defining the search)
If you can convert a nondeterministic automata to a deterministic one, doesn't that mean they are all deterministic?
It's a representation for state machines in which state transitions are apparently ambiguous: a given state in the NFA can, for exactly the same input, go into multiple other states. This is a very convenient representation for pattern matching.
The way the ambiguity resolves itself is not through randomness, but by the understanding that the machine is in all of the possible states at the same time. Then, in a concrete implementation in a programming language, we represent that situation by using a set of states as the run-time state.
E.g. when the input symbol b is received, some NFA machine goes from state { 0, 3, 5 } to { 1, 3, 7, 8 }; i.e. it is in NFA states 0, 3 and 5, which transition to 1, 3, 7, 8 when b is seen.
NFA graphs can be executed directly by an NFA simulator which calculates these transitions on the fly.
We can also statically figure out all the state sets there can be and their transitions.Then we re-label these sets as the simple states of a deterministic automaton. E.g. { 0, 3, 5 } is dubbed S0, { 1, 3, 7, 8} is dubbed S1. There is a transition from S0 to S1 on b. We can work through all the possible transitions, ferret out all the subsets and their transitions to build a simple machine. That is the "subset construction".