Question:medium
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 \(M\)?
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 \(M\)?
Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to \(M\)?
Show Hint
An NFA with n states can only ever be determinized into subsets of its state set, so no equivalent DFA (minimal or not) can exceed \(2^n\) states; here \(2^6 = 64\) is the hard ceiling.
Updated On: Jul 22, 2026
- 32
- 65
- 1
- 128
Show Solution
The Correct Option is B, D
Solution and Explanation
Step 1: Think of it as a pigeonhole problem.
Every state reachable in the determinized version of $M$ (built by tracking the exact set of NFA states the automaton could currently be in) is labelled by a subset of $M$'s 6 states. There are only $2^6 = 64$ distinct subsets that exist at all, so no matter how $M$'s transitions are wired, the determinized automaton can never be forced to use more than 64 distinct labels/states. This is a pigeonhole ceiling, not a typical-case estimate -- it is absolute.
Step 2: Minimality only removes states, it never adds them.
Minimization works by collapsing states of a DFA that are behaviourally indistinguishable (same accept/reject outcome for every possible future input) into a single state. Starting from at most 64 states and only ever merging some of them together can only bring the count down to somewhere between 1 and 64; it is structurally impossible to end up with more states after minimization than before it.
Step 3: Screen the four candidate counts against the ceiling of 64.
32 is comfortably below 64, so there is no obstruction to a suitably designed 6-state NFA needing exactly 32 states after minimization.
1 is the smallest possible DFA size and is trivially reachable (e.g. an NFA that accepts every string, or one that accepts no string, minimizes to a single state).
65 is one more than the ceiling of 64, so it is unreachable under any circumstances.
128 equals $2^7$, which would be the ceiling for a 7-state NFA, not a 6-state one; for $n=6$ it overshoots the true ceiling of 64 by double, so it is also unreachable.
Step 4: State the impossible set.
$\[ \boxed{\text{65 and 128 (options B and D) can never be the minimal DFA size for a 6-state NFA}} \]$
Every state reachable in the determinized version of $M$ (built by tracking the exact set of NFA states the automaton could currently be in) is labelled by a subset of $M$'s 6 states. There are only $2^6 = 64$ distinct subsets that exist at all, so no matter how $M$'s transitions are wired, the determinized automaton can never be forced to use more than 64 distinct labels/states. This is a pigeonhole ceiling, not a typical-case estimate -- it is absolute.
Step 2: Minimality only removes states, it never adds them.
Minimization works by collapsing states of a DFA that are behaviourally indistinguishable (same accept/reject outcome for every possible future input) into a single state. Starting from at most 64 states and only ever merging some of them together can only bring the count down to somewhere between 1 and 64; it is structurally impossible to end up with more states after minimization than before it.
Step 3: Screen the four candidate counts against the ceiling of 64.
32 is comfortably below 64, so there is no obstruction to a suitably designed 6-state NFA needing exactly 32 states after minimization.
1 is the smallest possible DFA size and is trivially reachable (e.g. an NFA that accepts every string, or one that accepts no string, minimizes to a single state).
65 is one more than the ceiling of 64, so it is unreachable under any circumstances.
128 equals $2^7$, which would be the ceiling for a 7-state NFA, not a 6-state one; for $n=6$ it overshoots the true ceiling of 64 by double, so it is also unreachable.
Step 4: State the impossible set.
$\[ \boxed{\text{65 and 128 (options B and D) can never be the minimal DFA size for a 6-state NFA}} \]$
Was this answer helpful?
0
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems