An NFA with $n$ states can be converted to an equivalent DFA. The resulting DFA has AT MOST how many states?

1. The SUBSET (powerset) CONSTRUCTION converts an NFA to an equivalent DFA. 2. Each state of the DFA represents a SUBSET of the NFA's states (the set of NFA states the NFA could be in after reading the input). 3. The number of subsets of an $n$-element set is $2^n$. So the DFA has at most $2^n$ states. 4. For SOME languages, this exponential blow-up is unavoidable — there exist NFAs with $n$ states whose minimal equivalent DFA needs $2^n$ states. 5. For OTHER languages, the DFA may be much smaller (e.g. for a single-state NFA the DFA has 1 state). 6. Options A, B, D underestimate the bound. _Source: Jeff Erickson, "Models of Computation", §2.6 (Powerset construction)._