GATE CS 2015 Set 3 Q.28 (CS Q.18): Regular Expressions, Finite Automata and Regular Languages

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{L}$ (complement of $L$ )?

Official answer and solution

Official answer: B
From: Official GATE 2015 answer key

Solution

Construct the minimal DFA for L and invert accepting states to obtain the minimal DFA for the complement language.

The language $L = \Sigma^* 0011 \Sigma^*$ contains all binary strings that contain 0011 as a substring.

A minimal DFA recognizing $L$ requires 5 states tracking prefixes of 0011:

State $q_0$ : $\epsilon$ (no progress towards 0011)
State $q_1$ : matched 0
State $q_2$ : matched 00
State $q_3$ : matched 001
State $q_4$ : matched 0011 (accepting dead state / trap state for substring presence)

To recognize the complement language $\overline{L}$ (all strings not containing 0011 as a substring), we convert the minimal DFA of $L$ by swapping accepting and non-accepting states (making $q_0, q_1, q_2, q_3$ accepting and $q_4$ non-accepting).

Because complementation on a minimal complete DFA preserves state distinguishability, the resulting DFA for $\overline{L}$ remains minimal with exactly 5 states.

Final answer

Common trap

Forgetting that inverting final and non-final states of a complete minimal DFA yields a minimal DFA for the complement without adding any extra states.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 28 of 65, printed as CS Q.18
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source