5 ms·
The problem is that a deterministic regex engine (deterministic finite automata or DFA) is strictly less powerful than a non-deterministic one (NFA). DFA's can
by bsder 7y ago
The problem is that a deterministic regex engine (deterministic finite automata or DFA) is strictly less powerful than a non-deterministic one (NFA). DFA's can't backtrack, for example. In addition, DFA's can be quite a bit slower for certain inputs and matches.
- Firerouge 7y agoPerhaps a parser exists that can determine if an input regex is runaway backtrack prone, and can automatically switch to a deterministic algorithm?
- ehaliewicz2 7y agoJust check if it uses backreferences, otherwise it can be implemented via NFA/DFA.
- auscompgeek 7y agoActually, it is proven that NFAs and DFAs are equally expressive. See https://en.wikipedia.org/wiki/Powerset_construction https://en.wikipedia.org/wiki/Powerset_construction
- bsder 7y ago"You are technically correct. The best kind of correct." In theory, your statement is perfectly correct. However, quoting that reference: "However, if the NFA has n states, the resulting DFA may have up to 2^n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs." This means that in practice, DFAs are larger, slower, and sometimes can't be run at all if complex enough. However, this was my mistake. I remembered (vaguely) the 2^n issue and didn't follow up to make sure I was accurate. And I completely spaced on the fact that neither NFA's nor DFA's handle backreferences without extension.
- gautamdivgi 7y agoI thought NFAs and DFAs are equivalent, i.e. an NFA can be reduced to a DFA (at least what I remember of undergraduate theory of computation).
- Thorrez 7y agoI don't know what you mean by "DFA's can't backtrack". Maybe you mean DFAs don't support backreferences, which is true, but NFAs don't support backreferences either. I believe if r is the size of the regex and d is the size of the data, an NFA is O(r) to compile and O(rd) to execute, while a DFA is O(2^r) to compile and O(d) to execute. So DFAs are slower to compile, but faster to execute.
- ashton314 7y agoYou might be thinking of push down automata, where N-PDAs are strictly more powerful than D-PDAs.
- nabla9 7y agoThe problem is not DFA vs NFA. “regular expression” has different meaning in programming context and formal language context. Regular expressions in regex libraries do more than match regular languages. PCRE can recognize also all context free languages and some subset of context-sensitive languages. Just having backreferences makes the problem NP-hard.