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

Step 1: Recall the subset construction (powerset construction) used to convert an NFA to an equivalent DFA. If the NFA has \(n\) states, the DFA built by subset construction has one state for every subset of the NFA states, giving at most \(2^n\) states.

Step 2: Here \(n = 6\), so the DFA from subset construction has at most \(2^6 = 64\) states. Minimization only merges equivalent states and never creates new ones, so the minimal DFA equivalent to M can have at most 64 states.

Step 3: Check each option against this bound of 64.

• 32: since 32 <= 64 and 32 = 2^5, a 6-state NFA can realize a minimal DFA with 32 states. Achievable.
• 65: since 65 > 64, no 6-state NFA can ever produce a minimal DFA with 65 states. NOT achievable.
• 1: an NFA accepting every string, or accepting no string, minimizes to a single-state DFA. Achievable.
• 128: since 128 = 2^7 > 64, this also exceeds the theoretical maximum. NOT achievable.

Step 4: The values that CANNOT be the size of the minimal DFA are 65 and 128, matching options B and D.

\[ \boxed{\text{Options B (65) and D (128) cannot occur}} \]