GATE CS 2025 Set 1 | Question 28

MSQ · 1 mark

A regular language \(L\) is accepted by a non-deterministic finite automaton (NFA) with \(n\) states. Which of the following statement(s) is/are FALSE?

  1. Option A: \(L\) may have an accepting NFA with \(\lt n\) states.
  2. Option B: \(L\) may have an accepting DFA with \(\lt n\) states.
  3. Option C: There exists a DFA with \(\le 2^{n}\) states that accepts \(L\).
  4. Option D: Every DFA that accepts \(L\) has \(\gt 2^{n}\) states. (correct)

Answer

(D)

Explanation

The question asks for the FALSE statements.

  • (A) True statement: a smaller NFA can exist. For example, if the given NFA (with \(n \ge 2\)) accepts every string, a 1-state NFA also accepts \(L\).
  • (B) True statement: in the same example a 1-state DFA accepts \(L\), so a DFA with fewer than \(n\) states is possible.
  • (C) True statement: the subset construction turns any \(n\)-state NFA into an equivalent DFA with at most \(2^{n}\) states.
  • (D) False: by (C), some DFA for \(L\) has at most \(2^{n}\) states, so not every DFA can have more than \(2^{n}\).

Answer: D