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 ?

GATE 2018 Previous Year Paper Solution Question 6 – Computer Science

In this video question which was asked in the exam of GATE 2018 is discussed.

Question :- 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 ?
A. k ≥〖 n〗^2
B. k ≥ n
C. k ≤〖 n〗^2
D. k ≤〖 2〗^n

Solution is given in the video.