Question Details

Which of the following cannot be the number of states in the minimal DFA equivalent to the NFA of 6 states?

Options

A

1

B

32

C

65

D

128

Show Answer

Correct Answer :

Option C

65

Option D

128

Solution :

The correct options are 65 and 128.

To understand why these cannot be the number of states, let us analyze the relation between the number of states in a Non-Deterministic Finite Automaton (NFA) and its equivalent Minimal Deterministic Finite Automaton (DFA).

Given that the NFA has n = 6 states, the power set construction method allows us to construct an equivalent DFA. Since the set of states of the DFA is a subset of the power set of the NFA states, the maximum number of states in the equivalent DFA (before minimization) is:
2 n = 2 6 = 64

Thus, any DFA equivalent to a 6-state NFA can have at most 64 states. Minimizing a DFA can only decrease (or keep equal) the number of states, but it cannot increase them. Therefore, the number of states in the minimal DFA equivalent to a 6-state NFA must be at most 64.

Let us evaluate the given options against this upper limit of 64 states:
1. 1: This is less than or equal to 64, so it is a possible number of states.
2. 32: This is less than or equal to 64, so it is a possible number of states.
3. 65: Since 65 > 64, it is impossible for the minimal DFA to have 65 states.
4. 128: Since 128 > 64, it is impossible for the minimal DFA to have 128 states.

Consequently, the values 65 and 128 cannot be the number of states in the minimal DFA equivalent to the 6-state NFA.

Unlock Our Free Library

Access expert-curated educational resources and study materials—completely free.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...