Question 19

Let $M = (Q, \Sigma, \delta, q_0, F)$ be a minimal DFA accepting language $L$, where $|Q| = k$.

The complement of $L$, given by $\{0,1\}^* - L = \overline{L}$, is recognized by the DFA $M' = (Q, \Sigma, \delta, q_0, Q \setminus F)$, obtained simply by swapping accepting and non-accepting states while keeping the exact same state set $Q$ and transition function $\delta$.

Because indistinguishability of states is symmetric (two states $p$ and $q$ are distinguishable in $M$ if and only if they are distinguishable in $M'$ by the exact same strings), $M'$ is also minimal. Hence, the minimal DFA for $\{0,1\}^* - L$ must necessarily have exactly $k$ states.

For operations like adding or subtracting a single word $\{01\}$, or concatenation $L \cdot L$, the minimal DFA size can increase or decrease significantly depending on $L$.