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?

By the standard subset construction method (powerset construction), any Non-Deterministic Finite Automaton (NFA) with $n$ states can be converted into an equivalent Deterministic Finite Automaton (DFA) with at most $2^n$ states.

Minimizing this DFA can either keep the number of states the same or reduce it further. Hence, the number of states $k$ in the minimal equivalent DFA must satisfy:

Thus, option D is necessarily true.

• Option A ($k \ge 2^n$) is not necessarily true because $k$ can be as small as $1$.

• Option B ($k \ge n$) is not necessarily true since an $n$-state NFA can accept $\Sigma^*$, which has a minimal DFA with $1$ state ($1 < n$).

• Option C ($k \le n^2$) is not necessarily true since there exist NFAs where the minimal DFA requires exactly $2^n$ states, which is strictly greater than $n^2$ for $n \ge 5$.