GATE CS 2015 Set 3 Q18 — Regular Expressions and Finite Automata

The language $L = \Sigma^*0011\Sigma^*$ represents the set of all strings over $\Sigma = \{0, 1\}$ that contain the substring 0011.

Step 1: Construct the Minimal DFA for $L$

To recognize the substring 0011, we track the longest prefix of 0011 matched so far. The states can be defined as follows:

• $q_0$: Start state (no progress towards 0011)
• $q_1$: Matched 0
• $q_2$: Matched 00
• $q_3$: Matched 001
• $q_4$: Matched 0011 (Accepting state / Dead-end trap state)

The transition table for this DFA is:

This minimal DFA for $L$ has exactly $5$ states.

Step 2: Find the Minimal DFA for $\bar{L}$

By the properties of regular languages, the complement of a regular language $\bar{L}$ is recognized by a DFA obtained by swapping the accepting and non-accepting states of the minimal DFA for $L$:

• The set of states and transitions remains identical.
• The new accepting states are $\{q_0, q_1, q_2, q_3\}$.
• The new non-accepting state is $\{q_4\}$.

According to the Myhill-Nerode theorem, the equivalence relations $\equiv_L$ and $\equiv_{\bar{L}}$ are identical. Thus, the minimal DFA for $\bar{L}$ has the exact same number of states as the minimal DFA for $L$.

Therefore, the minimum number of states in a DFA that recognizes $\bar{L}$ is $5$.