GATE CS 2025 Set 1 Q18 — Regular and Context-free Languages

We are given that a regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Let us analyze each statement to identify which one is FALSE:

• Option A: $L$ may have an accepting NFA with $< n$ states.
  True. If the given NFA is not minimal, we can find a smaller equivalent NFA. For example, if $L = \Sigma^*$ and we are given an NFA with $n = 3$ states, there exists an equivalent NFA with $1$ state (since $1 < 3$).
• Option B: $L$ may have an accepting DFA with $< n$ states.
  True. Similar to Option A, if $L = \Sigma^*$ and the given NFA has $n = 3$ states, the minimal DFA for $L$ requires only $1$ state (since $1 < 3$).
• Option C: There exists a DFA with $\leq 2^{n}$ states that accepts $L$.
  True. By the standard subset construction algorithm, any NFA with $n$ states can be converted into an equivalent DFA with at most $2^n$ states.
• Option D: Every DFA that accepts $L$ has $> 2^{n}$ states.
  False. This directly contradicts the subset construction theorem (Option C), which guarantees the existence of a DFA with at most $2^n$ states.

Thus, only statement D is false.