Let L be the language represented by the regular expression $\Sigma^* 0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\overline{\text{L}}$ (complement of L)?

The language $L = \Sigma^* 0011 \Sigma^*$ consists of all binary strings that contain the substring $0011$.

The minimal complete DFA for language $L$ requires $5$ states corresponding to the length of the longest prefix of $0011$ matched so far:

1. State $q_0$: $\epsilon$ matched (start state)

2. State $q_1$: $0$ matched

3. State $q_2$: $00$ matched

4. State $q_3$: $001$ matched

5. State $q_4$: $0011$ matched (accepting/dead state for $L$)

To construct the minimal DFA for the complement language $\overline{L}$:

• We keep the exact same state set and transition function of the minimal complete DFA for $L$, and invert the final states (non-accepting states become accepting, and accepting states become non-accepting).

• Since complementing the accepting states in a minimal complete DFA results in a minimal DFA for the complement language, the number of states remains unchanged.

Hence, the correct option is (B).