Project ForgeTheory of Computation
Finite Automata & Regular Languages
GATE 2018
Medium
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
- Ak ≥ 2ⁿ
- Bk ≥ n
- Ck ≤ n²
- k ≤ 2ⁿ
Explanation
The subset construction converts an n-state NFA into a DFA whose states are subsets of the NFA's state set, giving at most 2ⁿ DFA states. The minimal equivalent DFA can only have fewer states than (or equal to) this bound, so k ≤ 2ⁿ always holds.
Source: GATE CS 2018 (2018)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.