Let \(N\) be an NFA with n states. Let \(k\) be the number of states of a…
2018
Let \(N\) be an NFA with n states. Let \(k\) be the number of states of a minimal which is equivalent to \(N\). Which one of the following is necessarily true?
- A.
\(k \geq 2^n\) - B.
\(k \geq n\) - C.
\(k \leq n^2\) - D.
\(k \leq 2^n\)
Attempted by 197 students.
Show answer & explanation
Correct answer: D
Key insight: The subset (power-set) construction turns an NFA with n states into a DFA whose states correspond to subsets of the NFA's states, so there are at most 2^n possible DFA states.
Therefore the DFA produced by determinization has at most 2^n states; the minimal DFA equivalent to the NFA can have no more states than that.
The bound is tight in the worst case: there are standard constructions of NFAs with n states whose equivalent minimal DFA requires 2^n states, so 2^n is the correct universal upper bound.
A video solution is available for this question — log in and enroll to watch it.