The GATE Grind

GATE 2026 CS (CS1) – Question 26

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple select

Let $M$ be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in any minimal deterministic finite automaton (DFA) equivalent to $M$?

  1. 32
  2. 65
  3. 1
  4. 128

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 65; (D) 128

Explanation

For any NFA with $k$ states, the standard subset construction produces an equivalent DFA with states corresponding to subsets of the NFA's states. Since a set of $k$ states has exactly $2^k$ subsets, any equivalent DFA has at most $2^k$ states.

For $k = 6$ states:
$$\text{Maximum possible states in equivalent minimal DFA} \le 2^6 = 64$$

Evaluating the choices:
- 1 state is achievable (e.g. if the NFA accepts $\Sigma^*$).
- 32 states is achievable ($32 \le 64$).
- 65 states is impossible ($65 > 64$).
- 128 states is impossible ($128 > 64$).

Therefore, 65 and 128 CANNOT be the number of states. Options (B) and (D) are correct.