Question

Let \(L \subseteq \{0,1\}^*\) be an arbitrary regular language accepted by a minimal DFA with \(k\) states. Which one of the following languages must necessarily be accepted by a minimal DFA with \(k\) states?

• A. \(L - \{01\}\)
• B. \(L \cup \{01\}\)
• C. \(\{0,1\}^* - L\)
• D. \(L \cdot L\)

Hint:

Complementing a DFA preserves the number of states—only accepting and rejecting states are swapped.

Answer 1

The Correct Option is C

Step 1: Recall closure properties of regular languages.
Regular languages are closed under complement, union, difference, and concatenation. However, closure does not imply that the minimal DFA size remains the same.

Step 2: Analyze option (C): Complement of \(L\).
The language \(\{0,1\}^* - L\) is the complement of \(L\).
To obtain a DFA for the complement, we only need to swap accepting and non-accepting states of the minimal DFA for \(L\).

Step 3: Minimality of the complemented DFA.
Complementing a DFA does not change the number of states, and minimality is preserved because distinguishability of states remains unchanged.
Hence, the complement of \(L\) is necessarily accepted by a minimal DFA with exactly \(k\) states.

Step 4: Eliminate other options.
(A) Removing a single string may reduce or increase the number of states.
(B) Adding a string may require additional states.
(D) Concatenation generally increases the number of states.

Step 5: Conclusion.
Only the complement of \(L\) must be accepted by a minimal DFA with exactly \(k\) states.

Final Answer: (C)