GATE CS 2021 Set 2 Q9 — Regular Expressions and Finite Automata

To find which language must necessarily be accepted by a minimal DFA with exactly $k$ states, let us analyze the properties of the complement operation on DFAs.

1. Complement of a Language ($\{0,1\}^* - L$)

Let $M = (Q, \Sigma, \delta, q_0, F)$ be the minimal DFA accepting $L$ with $|Q| = k$ states.

The complement language $\overline{L} = \{0,1\}^* - L$ is accepted by the DFA $M' = (Q, \Sigma, \delta, q_0, Q \setminus F)$, which is obtained simply by swapping the accepting (final) and non-accepting states of $M$.

Proof of Minimality:

• Suppose $M'$ is not minimal, meaning there exists a DFA $M''$ accepting $\overline{L}$ with fewer than $k$ states.
• By swapping the final and non-final states of $M''$, we would obtain a DFA accepting $L$ with fewer than $k$ states.
• This directly contradicts the assumption that the minimal DFA for $L$ has $k$ states.

Thus, the minimal DFA for $\{0,1\}^* - L$ must have exactly $k$ states.

2. Counterexamples for Other Options

Let $L = \{0,1\}^*$. The minimal DFA for $L$ has $k = 1$ state (a single accepting state with self-loops on $0$ and $1$).

• Option A ($L - \{01\}$): The language is $\{0,1\}^* - \{01\}$. The minimal DFA for this language requires at least $3$ states to track and reject the string "01". Thus, the number of states changes.
• Option B ($L \cup \{01\}$): If we choose $L = \emptyset$, the minimal DFA has $k = 1$ state (a non-accepting state with self-loops). But $L \cup \{01\} = \{01\}$, which requires $4$ states in its minimal DFA.
• Option D ($L \cdot L$): If we choose $L = \{a\}$ over $\Sigma = \{a\}$, the minimal DFA has $k = 3$ states (start, accept, and dead state). The language $L \cdot L = \{aa\}$ requires $4$ states in its minimal DFA.

Therefore, only option C is guaranteed to have exactly $k$ states in its minimal DFA.