liveBook · Manning

Deterministic finite automaton

As explained in Secrets of the JavaScript Ninja, Third Edition

A DFA is a deterministic finite automaton that processes each input through a single state transition path without backtracking.

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

How Secrets of the JavaScript Ninja, Third Edition covers it

How deep it goes
Explains the linear-time guarantee and feature tradeoffs, but not DFA construction or internal mechanics.
What you can do after
Apply it via node-re2 when regex safety is a priority, accepting the loss of backreferences and lookbehind.
How it connects
Connects regular expressions with backtracking, ReDoS, backreferences, and lookbehind.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Secrets of the JavaScript Ninja, Third Edition. The section links point to the parts of the book it draws on.