Subset construction

Also known as: Powersets construction, NFA to DFA

Subset construction converts an NFA into an equivalent DFA. Each DFA state is a set of NFA states: the set of places you might be after reading the same prefix.

Start from ${q_0}$ (or ε-closure of the start, if you have an ε-NFA). From a subset $S$, on symbol $a$, go to the set of all NFA successors of states in $S$ (then ε-close again if needed). A DFA state is accepting if any member is accepting.

Lazy construction only builds subsets you actually reach; you rarely materialize the full powerset. Worst case the DFA is exponential in the NFA size, but the language is unchanged: still regular.

← Back to CS Glossary