Question

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite
alphabet.
Which of the following options CANNOT be the number of states in the minimal
deterministic finite automaton (DFA) that is equivalent to 𝑀 ?

• A. 32
• B. 65
• C. 1
• D. 128

Hint:

A DFA obtained from an n-state NFA via subset construction has at most \(2^n\) states, so a 6-state NFA can never yield a minimal DFA with more than 64 states.

Answer 1

The Correct Option is B, D

An NFA with \(n\) states can be simulated by a DFA whose states are subsets of the NFA's state set. There are \(2^n\) possible subsets, so the subset-construction DFA has at most \(2^n\) states, and minimizing it can only reduce this count, never increase it.

With \(n = 6\) here, the ceiling on the number of states in any DFA equivalent to this NFA, including the minimal one, is \(2^6 = 64\).

Now test the four given numbers against this ceiling of 64.

\(32 \le 64\) is possible, for example a 6-state NFA over a binary alphabet can realize a minimal DFA with exactly 32 states.

\(1 \le 64\) is possible, this happens whenever the recognized language is either everything or nothing.

\(65 > 64\) is impossible, it exceeds the maximum number of subsets of a 6-element set.

\(128 > 64\) is impossible for the same reason, since \(128 = 2^7\) would need at least 7 NFA states in the worst case, not 6.

So the two values that can never be the state count of the minimal DFA are 65 and 128.