Let \(L⊆\{0,1\}^∗\) be an arbitrary regular language accepted by a minimal DFA…

Correct answer: the complement of L, i.e. {0,1}* – L.

Reason (intuitive): Complementation on a deterministic complete automaton simply swaps accepting and rejecting states. The transition graph and the distinguishability of states remain the same, so the DFA after swapping acceptance still has k states and recognizes the complement.

Formal argument (Myhill–Nerode):

• Minimal DFA states correspond to equivalence classes of the relation ≡_L (two prefixes are equivalent if no suffix distinguishes them for membership in L).

• If two prefixes x and y are distinguishable for L, there exists a suffix z with exactly one of xz or yz in L. After complementing, exactly one of xz or yz is in the complement, so distinguishability is preserved.

• Hence the equivalence relation (and number of equivalence classes) is unchanged, so the minimal DFA for the complement has the same number k of states.

Why the other operations do not necessarily preserve k:

• Removing a single string from L can merge equivalence classes if that string was the only witness distinguishing some prefixes, so the minimal DFA size can decrease.

• Adding a string to L can create new distinguishing suffixes and increase the number of equivalence classes, so the minimal DFA size can increase.

• Concatenation can significantly change the structure of distinguishability between prefixes and often increases the minimal DFA size; it does not have to remain k.

Therefore, only the complement operation must necessarily be accepted by a minimal DFA with k states.