A deterministic finite automaton (DFA) matches regular expressions without backtracking: each input follows a single state-transition path. This avoids catastrophic backtracking and guarantees O(n) execution time for an input of length n. section 12.6.3
The performance guarantee comes with a feature tradeoff:
- DFA-based regex engines cannot implement features that depend on backtracking, including backreferences and lookbehind. section 12.6.3
- For JavaScript projects prioritizing regex safety, node-re2 provides a native binding for a DFA engine. section 12.6.3
