GATE CS 2025 (Forenoon) — Question 28

Theory of Computation (TOC)Regular Expressions & Finite Automata (DFA/NFA Min)MSQ1 markMedium

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. A
    \( L \) may have an accepting NFA with \( < n \) states.
  2. B
    \( L \) may have an accepting DFA with \( < n \) states.
  3. C
    There exists a DFA with \( \le 2^n \) states that accepts \( L \).
  4. D
    Every DFA that accepts \( L \) has \( > 2^n \) states.
Practise the full 2025-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Regular Expressions & Finite Automata (DFA/NFA Min)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group