Let \(N\) be an NFA with n states. Let \(k\) be the number of states of a…

GATE · 2018 · CS · Computer Science & IT

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

  1. A.

    k≥2nk \geq 2^n

  2. B.

    k≥nk \geq n

  3. C.

    k≤n2k \leq n^2

  4. D.

    k≤2nk \leq 2^n

Attempted by 469 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…