Powerset construction

Remarks

By induction on the length of $w$, the state $\delta^*(\set{q_0}, w)$ is exactly the set of states that $N$ can reach from $q_0$ by reading $w$. So $D$ accepts $w$ if and only if some run of $N$ on $w$ ends in $F$. In practice one builds only the subsets reachable from $\set{q_0}$, which are often few. The bound $2^n$ cannot be improved in general. The language of words over $\set{a, b}$ whose $n$-th letter from the end is $a$ has an NFA with $n + 1$ states. But every DFA for it needs at least $2^n$ states, since it must remember the last $n$ letters. For an NFA with $\varepsilon$-moves, the same construction works after replacing each set by its $\varepsilon$-closure.

Going deeper

For a student

This theorem shows that nondeterminism adds no power to finite automata, unlike the open question for polynomial-time Turing machines. It is the standard way to prove that NFAs, $\varepsilon$-NFAs and DFAs all accept exactly the regular languages. Combined with the translation of regular expressions into $\varepsilon$-NFAs, it is how lexer generators and some search tools turn a pattern into a fast deterministic matcher. The resulting DFA can then be reduced by DFA minimization.