Subset construction (DFA)
Subset construction takes the NFA Thompson's construction builds and produces a deterministic finite automaton (a DFA) whose own states are *sets* of NFA states — the exact sets the NFA simulation would have been tracking live, enumerated once up front instead. Two NFA states that are always active together become indistinguishable from the DFA's point of view and collapse into one of its states.
When it is the right choice
The right choice whenever the same pattern will be matched against many inputs: the expensive part — working out which combinations of NFA states are reachable — is paid once, at compile time, and every match after that is a single table lookup per character. It is the wrong choice when the pattern changes on every call and is only used once, since building the DFA can itself take time proportional to the number of states it discovers, and in the worst case that is exponential in the pattern's size (though not in the input's).
How it works
- Start from the epsilon closure of the NFA’s start state; that set is the DFA’s own start state.
- For each DFA state and each character the pattern uses, compute where the NFA would end up from every state in the set, closed under epsilon transitions, and call that the next DFA state.
- Keep only sets actually reached this way; give each a fresh id the first time it appears.
- Repeat until no DFA state produces a set that has not already been seen.
- A DFA state is accepting exactly when the NFA set it stands for contains the NFA’s own accepting state.
Worth noticing
- There is exactly one active state at every step, never a set — that is the entire difference from the NFA page, and it is why this page’s picture never needs more than one highlighted node.
- A DFA state can be a dead end with nowhere further to go. This tool draws that as "no state at all" rather than inventing a sink state, since none of this tool’s examples need one to make their point.
- Building the table (shown once, before the input is read) can itself cost more states than the NFA has, which is a real cost this page does not hide — it is just a cost paid once rather than on every match.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Extra space
- O(2^m) states, in the worst case
The pattern is capped at 14 characters and the text at 24, both pedagogical rather than technical: every extra pattern character can roughly double the automaton this tool draws, and this tool draws one frame per character, so the real limit in practice is legibility rather than time.