Question

Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?

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

Hint:

For GATE questions: An NFA with $n$ states can result in a DFA with \textbf{at most $2^n$ states}. Any option strictly greater than $2^n$ is impossible.

Answer 1

The Correct Option is C

The question deals with Non-deterministic Finite Automaton (NFA) and its equivalent Deterministic Finite Automaton (DFA). We are asked to determine which of the provided options cannot be the number of states in a minimal DFA that is equivalent to an NFA with 6 states.

An NFA with \(n\) states can have a maximum of \(2^n\) states in its equivalent DFA. In this scenario, the NFA has 6 states, which implies that the maximum number of states in the corresponding DFA is \(2^6\). Let's calculate this:

• \(2^6 = 64\)

This means that the DFA can have at most 64 states. Any number of states in the DFA equivalent to this NFA will be less than or equal to this number. Now let's evaluate the options:

1. 1 state: This is possible if the NFA transitions can be reduced to a DFA with a single state.
2. 32 states: This is possible as it is less than or equal to the maximum limit of 64.
3. 65 states: This is NOT possible because 65 exceeds the maximum possible states (64) that a DFA equivalent to this NFA can have.
4. 128 states: This is also not possible as it is more than the allowed maximum of 64.

Thus, the only valid answer that represents a number of states that cannot possibly be in the minimal DFA equivalent to this NFA is \(65\) because it exceeds the calculated maximum of 64 states.

Answer 2

Step 1: Recall the NFA to DFA conversion rule.
An NFA with $n$ states can be converted into an equivalent DFA using the subset construction method.
The maximum number of states in the resulting DFA is: \[ 2^n \] Step 2: Apply the rule for the given NFA.
Given number of NFA states: \[ n = 6 \] Maximum possible number of DFA states: \[ 2^6 = 64 \] Thus, the equivalent DFA (before minimization) can have at most 64 states.
Step 3: Consider DFA minimization.
After minimization, the number of states in the DFA can be any number from 1 up to 64, depending on the language recognized.
However, it cannot exceed 64.
Step 4: Analyze the given options.
(A) 1: Possible (for example, if the language is $\Sigma^*$ or $\emptyset$).
(B) 32: Possible, since $32<64$.
(C) 65: Not possible, as it exceeds the maximum limit of $64$.
(D) 128: Also exceeds $64$, but the smallest such impossible option is 65.
Step 5: Conclusion.
The number of states in a minimal DFA equivalent to a 6-state NFA cannot be: \[ \boxed{65} \]