The GATE Grind

GATE 2018 CS – Question 16

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

Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true?

  1. $k\ge2^n$
  2. $k\ge n$
  3. $k\le n^2$
  4. $k\le2^n$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $k\le2^n$

Explanation

Subset construction converts an $n$-state NFA into a DFA with at most $2^n$ states, and the minimal DFA is no larger, so $k\le2^n$. No lower bound holds in general.