Let N be an NFA with n states and let M be the minimized DFA with m states…

Key fact: The subset construction turns an NFA with n states into a DFA whose states correspond to subsets of the NFA states.

• There are at most 2^n subsets of an n-element set, so the constructed DFA has at most 2^n states.

• Minimizing that DFA can only decrease (or keep) the number of states, so the number m of states in the minimized DFA satisfies m ≤ 2^n.

Therefore the statement "m ≤ 2^n" is necessarily true.

Why the other statements are not necessarily true:

• The claim that n ≤ m is false in general: an NFA can be larger than the minimal DFA for the same language. Example: an NFA with two states that accepts every string (Σ*) yields a minimized DFA with one state, so n > m is possible.

• The claim that the minimized DFA has exactly one accepting state is false: minimal DFAs can have multiple accepting states depending on the language (for instance, a language whose acceptance depends on a modulo count can produce multiple accept states).

• The equality m = 2^n is not guaranteed: 2^n is an upper bound. Many NFAs produce far fewer reachable/distinguishable subsets; for example, an NFA that recognizes Σ* gives a minimized DFA with 1 state, not 2^n.