Which state counts cannot be the minimal DFA equivalent to a 6-state NFA?

65 and 128 cannot be the number of states. A 6-state NFA can produce at most 2^6 = 64 states in the equivalent DFA via subset construction. Any value greater than 64 is impossible for the minimal DFA.

What is the maximum number of states in a DFA equivalent to an n-state NFA?

The maximum number of states in a DFA equivalent to an n-state NFA is 2^n. This comes from the subset construction algorithm, where each DFA state corresponds to a subset of NFA states, and there are 2^n possible subsets.

Can a minimal DFA have fewer states than the original NFA?

Yes. The minimal DFA can have as few as 1 state (for trivial languages like the empty language or Sigma-star). The number of states in the minimal DFA can range from 1 to 2^n where n is the number of NFA states.

Why does a 6-state NFA give at most 64 states in a DFA?

Using subset construction, each DFA state is a subset of the NFA states. A 6-state NFA has 2^6 = 64 possible subsets of states. Each subset becomes one DFA state, so the maximum is 64. Some subsets may be unreachable, making the actual DFA smaller.

NFA to DFA: States That Cannot Exist for 6-State NFA

Computer Sciences > GATE 2026 SET-1 > Finite Automata

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 𝑀 ?

128

Correct : a,d

The key rule is: an NFA with n states can be converted to a DFA with at most 2ⁿ states using the subset construction algorithm.
For a 6-state NFA: maximum DFA states = 2⁶ = 64.
The minimal DFA can have anywhere from 1 to 64 states.
Checking each option:
• A: 65 - 65 > 64 → CANNOT happen
• B: 1 - 1 ≤ 64 → CAN happen (e.g., NFA for Σ* gives a 1-state DFA)
• C: 32 - 32 ≤ 64 → CAN happen
• D: 128 - 128 > 64 → CANNOT happen
So the answers that cannot be the number of states in the minimal DFA are A (65) and D (128).

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev