GATE CS 1987 Q2j — Regular Expressions and Finite Automata

The given statement is FALSE (represented by 0).

Explanation:

When converting a Non-deterministic Finite Automaton (NFA) with $n$ states to an equivalent Deterministic Finite Automaton (DFA) using the subset construction method, the resulting DFA can have at most $2^n$ states.

However, the minimal DFA equivalent to the NFA does not always have $2^n$ states. The actual number of states in the minimal DFA depends on the language and the structure of the NFA:

• Worst-case: There are specific languages where the minimal DFA indeed requires $2^n$ states (for example, the language over $\{0,1\}$ where the $n$-th symbol from the end is $1$).
• Best-case: If the NFA is already deterministic and minimal, the equivalent minimal DFA has exactly $n$ states.

Since the minimal DFA does not always have $2^n$ states, the statement is false.