GATE CSE 2026 Session 1 Q26: Impossible minimal DFA sizes for a 6-state NFA

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 the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, D (official GATE 2026 final answer key)

Concept used: The subset construction gives a DFA with at most $2^n$ states for an $n$ -state NFA.

First step: Compute the upper bound $2^6 = 64$ and reject anything larger.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key