Expand description
Subset-construction NFA → DFA converter. Subset-construction NFA → DFA converter.
Walks the NFA’s epsilon closures to produce a deterministic transition table. Dead states (non-accepting with no reachable accept) are pruned so downstream packing does not spend memory on them.
Per perf-audit L.2.1: closures are stored as sorted deduplicated
Vec<NfaStateId> (not BTreeSet) so that dedup via hashmap lookup
uses the flat buffer directly — no BTreeSet → Vec key conversion per
byte, no allocation hot-path inside the inner 256-byte loop. Edge
adjacency is flattened into a per-state slice so the byte transition
loop is a linear scan instead of a BTreeMap::get per byte per state.
Constants§
- MAX_
DFA_ STATES - Configured ceiling on the DFA state count.
Functions§
- nfa_
to_ dfa - Convert a Thompson NFA into a minimized-ready DFA via subset construction.