Question

Let N be an NFA with n status and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?

• A. $m=2^n$
• B. $n\le m$
• C. M has one accept state
• D. $m\le 2^n$

Answer 1

The correct option is D $m\le 2^n$

A State in a DFA will be subset of the set of states of the equivalent NFA.

The maximum number of states in the equivalent DFA of an NFA with n number of states will be $2^n$

So, number of states in eqivalent DFA $\le 2^n$