GATE CS 2018 Q6 — Regular Expressions and Finite Automata

To find the relationship between the number of states $n$ of an NFA $N$ and the number of states $k$ of its equivalent minimal DFA, we use the subset construction method:

1. Subset Construction: Given any NFA with $n$ states, we can construct an equivalent DFA where each state corresponds to a subset of the states of the NFA. Since a set of size $n$ has $2^n$ subsets, the constructed DFA has at most $2^n$ states.
2. Minimization: The minimal DFA is obtained by merging equivalent states of this DFA. Minimization can only decrease or maintain the number of states. Therefore, the number of states $k$ in the minimal DFA must satisfy:
   $$k \le 2^n$$

Let's evaluate why the other options are not necessarily true:

• Option A ($k \ge 2^n$): Incorrect. For many NFAs, the equivalent minimal DFA has far fewer than $2^n$ states. For example, an NFA accepting $\Sigma^*$ can have $n$ states, but its minimal DFA has only $1$ state.
• Option B ($k \ge n$): Incorrect. As shown in the example above, if $n > 1$ and the language is $\Sigma^*$, the minimal DFA has $1$ state, so $k = 1 < n$.
• Option C ($k \le n^2$): Incorrect. There are standard languages (such as those where the $n$-th symbol from the end is a specific character) where the minimal DFA requires exactly $2^n$ states. For $n \ge 3$, $2^n > n^2$, which violates $k \le n^2$.

Thus, the only statement that is necessarily true is $k \le 2^n$.