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 \(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
Verified By Collegedunia
The Correct Option is B, D
Solution and Explanation
Step 1: Recall the subset construction bound.
Converting an NFA with \(n\) states to an equivalent DFA is done by the subset construction, where each DFA state corresponds to a subset of the \(n\) NFA states. There are exactly \(2^n\) possible subsets, so the DFA built this way has at most \(2^n\) states. For \(n=6\), that upper bound is \(2^6 = 64\).
Step 2: Relate this bound to the minimal DFA.
The minimal DFA equivalent to \(M\) is obtained by merging equivalent (indistinguishable) states of any DFA that accepts the same language, including the subset-construction DFA. Merging states can only decrease or keep the same the state count, never increase it. Hence the minimal DFA can have at most as many states as the subset-construction DFA, i.e. at most 64 states. Also, a DFA needs at least 1 state (even the automaton accepting everything or nothing has exactly 1 minimal state), so the minimal DFA state count lies in the range \([1, 64]\).
Step 3: Test each option against the range \([1,64]\).
(A) 32: satisfies \(1 \le 32 \le 64\), so it is achievable -- an NFA can certainly be constructed (with 6 states over a suitable alphabet) whose minimal equivalent DFA has exactly 32 states.
(B) 65: exceeds 64, so no equivalent DFA, minimal or otherwise, can ever reach this many states. This value can never occur.
(C) 1: satisfies \(1 \le 1 \le 64\); for example, an NFA whose language is the entire alphabet's Kleene star has a 1-state minimal DFA. Achievable.
(D) 128: exceeds 64 (in fact it is \(2^7\), not \(2^6\)), so it can never be the state count of any DFA built from a 6-state NFA. This value can never occur.
Step 4: Conclusion.
The values that CANNOT be the number of states in the minimal DFA are 65 and 128, corresponding to options (B) and (D).
\[ \boxed{\text{Cannot be: (B) 65 and (D) 128}} \]
Converting an NFA with \(n\) states to an equivalent DFA is done by the subset construction, where each DFA state corresponds to a subset of the \(n\) NFA states. There are exactly \(2^n\) possible subsets, so the DFA built this way has at most \(2^n\) states. For \(n=6\), that upper bound is \(2^6 = 64\).
Step 2: Relate this bound to the minimal DFA.
The minimal DFA equivalent to \(M\) is obtained by merging equivalent (indistinguishable) states of any DFA that accepts the same language, including the subset-construction DFA. Merging states can only decrease or keep the same the state count, never increase it. Hence the minimal DFA can have at most as many states as the subset-construction DFA, i.e. at most 64 states. Also, a DFA needs at least 1 state (even the automaton accepting everything or nothing has exactly 1 minimal state), so the minimal DFA state count lies in the range \([1, 64]\).
Step 3: Test each option against the range \([1,64]\).
(A) 32: satisfies \(1 \le 32 \le 64\), so it is achievable -- an NFA can certainly be constructed (with 6 states over a suitable alphabet) whose minimal equivalent DFA has exactly 32 states.
(B) 65: exceeds 64, so no equivalent DFA, minimal or otherwise, can ever reach this many states. This value can never occur.
(C) 1: satisfies \(1 \le 1 \le 64\); for example, an NFA whose language is the entire alphabet's Kleene star has a 1-state minimal DFA. Achievable.
(D) 128: exceeds 64 (in fact it is \(2^7\), not \(2^6\)), so it can never be the state count of any DFA built from a 6-state NFA. This value can never occur.
Step 4: Conclusion.
The values that CANNOT be the number of states in the minimal DFA are 65 and 128, corresponding to options (B) and (D).
\[ \boxed{\text{Cannot be: (B) 65 and (D) 128}} \]
Was this answer helpful?
0
0
Top GATE CS Theory of Computation Questions
- Consider the following context-free grammar \(G\), where \(S\), \(A\), and \(B\) are the variables (non-terminals), \(a\) and \(b\) are the terminal symbols, \(S\) is the start variable, and the rules of \(G\) are described as:
\[ S \to aaB \mid Abb \] \[ A \to a \mid AaA \] \[ B \to b \mid bB \] Which ONE of the languages \(L(G)\) is accepted by \(G\)? - A regular language \(L\) is accepted by a non-deterministic finite automaton (NFA) with \(n\) states. Which of the following statement(s) is/are FALSE?
- Consider the following two languages over the alphabet \( \{a, b\} \): \[ L_1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ { and } \beta \in \{a, b\}^+ \} \] \[ L_2 = \{ \alpha \beta \alpha \mid \alpha \in \{a\}^+ { and } \beta \in \{a, b\}^+ \} \] Which ONE of the following statements is CORRECT?
- Consider the following two languages over the alphabet \( \{a, b, c\} \), where \( m \) and \( n \) are natural numbers. \[ L_1 = \{ a^m b^{m+n} c^{m+n} \mid m, n \geq 1 \} \] \[ L_2 = \{ a^m b^n c^{m+n} \mid m, n \geq 1 \} \] Which ONE of the following statements is CORRECT?
Consider the following deterministic finite automaton (DFA) defined over the alphabet, \( \Sigma = \{a, b\} \). Identify which of the following language(s) is/are accepted by the given DFA.
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions