Regular Expressions and Automata

The number of states is proportional to the length of the regular expression (each character/operator produces a small number of new states), unlike backtracking engines which may explode exponentially. ε-transitions (empty transitions: state jumps that do not consume input characters) are the key mechanism here—both alternation and closure rely on ε-branching.

DFA: Subset Construction

The "nondeterminism" of an NFA means that for the same input character, the current state might be a set of multiple states. The core insight of a DFA is to treat these "state sets" as new states in the DFA—this is called subset construction:

Algorithm:
  dfa_start = ε-closure({nfa_start})       ← From the NFA start state, without consuming input, find all reachable states
  worklist = [dfa_start]
  while worklist not empty:
    S = worklist.pop()
    for each input character c:
      T = ε-closure(move(S, c))            ← From any state in S, transition via c, then ε-closure
      if T is new:
        worklist.push(T)
      Add DFA transition: S ─c─► T

• move(S, c): From state set S, find all states reachable via character c (only looking at character transitions, ignoring ε).
• ε-closure: From a set of states, find all states reachable without consuming input, only via ε-transitions (including the states themselves).

These two operations constitute the entirety of subset construction. In the worst case, the number of DFA states is exponential relative to the NFA states—but in practice, lexical regular expressions rarely trigger the worst case: for most lexers, the number of DFA states is roughly equal to the number of NFA states.

This is why lexers use DFAs (few states, deterministic, O(1) transition per character), while general-purpose regex libraries (PCRE) use backtracking—DFAs cannot handle capture groups and backreferences, which are features that go beyond "true regular languages."

DFA Minimization: Hopcroft's Algorithm

The DFA produced by subset construction may have redundant states (two states behave identically for any input). Hopcroft's algorithm merges equivalent states:

Algorithm (Hopcroft, O(n log n)):
  Initial partition: One group for accept states, one group for non-accept states
  while partition is still refining:
    Take a partition block A
    For each input character c:
      If states in A transition to different partition blocks on c
        → Further split A based on "which block they transition to"

Split until stable—states within the same block behave identically for any input and can be merged into one. Hopcroft's n log n is currently the theoretical optimum (the theoretical lower bound for DFA minimization is Ω(n log n), and Hopcroft's algorithm achieves this optimum; DFA equivalence checking is a separate independent problem that can be solved in O(n) time).

In practice, most lexer generators (lex/flex/re2c) perform DFA minimization—lexer DFAs usually have only a few hundred states, so linear or near-linear algorithms are more than sufficient, and there is no need to invest heavily in constant-factor optimizations.

From Automata to Lexer: Longest Match and Priority

A lexer does not simply "run the DFA until the first accept state is reached," but rather uses longest match + priority:

Algorithm (maximal munch):
  Starting from the current source code position, run the DFA, recording every accept state encountered and its position
  Continue until the DFA cannot proceed further (dead state / no transition)
  Return to the most recent accept state → Extract that token
  Restart from the next character

• Longest Match: if will not stop after reading i (even if i is a valid identifier token); it must read if and only confirm the token when reading one more character makes continuation impossible.
• Priority: if is both a keyword and a valid identifier—keywords have higher priority. During DFA construction, mark keyword accept states with higher priority; after the longest match, if multiple accept states match the same length, select the one with the highest priority.

Two Types of Regex Engines: Why This Is Not Just Textbook Knowledge

Understanding the NFA→DFA chain directly corresponds to real-world regex engine selection:

The essence of a backtracking engine is performing DFS (Depth-First Search) on an NFA, while an automata engine is "first construct the DFA, then perform an O(n) scan on the input." The root cause of regex injection attacks (ReDoS) is that backtracking engines explode exponentially on carefully crafted regexes—constructing a DFA eliminates this problem.

This boundary also explains the difference between lexer regexes and general-purpose regexes: lexer regexes are "true regular" (no need for captures/backreferences), so they can use DFAs; general-purpose regexes add too many super-regular capabilities, requiring backtracking.

Trade-offs and Failure Modes

• DFA State Explosion: Certain regexes (like nested quantifiers (a*)* or Kleene star followed by complex alternation) can cause subset construction to produce exponential states → Rarely seen in practice; if triggered, use NFA simulation (on-demand state set calculation) instead of a full DFA.
• Longest Match Consuming Unwanted Characters: >> might be misinterpreted as nested generics >> vs right shift → The lexer itself cannot handle this (it requires context from the parser); the lexer only handles tokenization.
• Character Classes under Unicode: \w has different meanings under ASCII and Unicode; the DFA alphabet explodes from 128 to millions → Modern engines use character interval encoding (not enumerating each Unicode code point, but storing transition intervals), keeping the alphabet size manageable.

References

• Dragon Book (Aho, Lam, Sethi, Ullman): Chapter 3, Lexical Analysis — The complete chain of Regex → NFA → DFA → Minimization
• Ken Thompson (1968): "Regular Expression Search Algorithm" (CACM 11(6)) — The origin of NFA simulation
• Russ Cox (2007): "Regular Expression Matching Can Be Simple And Fast" — A thorough comparison of the two types of engines

Keywords: regular expression, finite automaton, NFA, DFA, Thompson construction, subset construction, ε-closure, ε-transition, Hopcroft minimization, maximal munch, longest match, backtracking, RE2, ReDoS, character class, Unicode character intervals