GATE CSE 2025 Session 1 Q28: False statements about NFA and DFA sizes

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?

Try it: multiple select: one or more correct options

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

Show answer and explanation

Answer: D (official GATE 2025 final answer key)

Concept used: Subset construction gives a DFA with at most $2^n$ states; the given NFA need not be minimal.

First step: The subset construction already gives a DFA with at most $2^n$ states, which directly contradicts one option.

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 2025 Session 1 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key