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

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

$(0 + 1)^* 0011(0 + 1)^* + (0 + 1)^* 1100(0 + 1)^*$

$(0 + 1)^* (00(0 + 1)^* 11 + 11(0 + 1)^* 00)(0 + 1)^*$

$(0 + 1)^* 00(0 + 1)^* + (0 + 1)^* 11(0 + 1)^*$

$00(0 + 1)^* 11 + 11(0 + 1)^* 00$

Official answer and solution

Official answer: B
From: Official GATE 2016 answer key

Solution

Construct a regular expression ensuring the presence of both substrings 00 and 11 in either order.

The condition requires that any valid string contains both the substring 00 and the substring 11.

In any such string, either 00 appears before 11, or 11 appears before 00:

If 00 appears before 11: The string has the form $(0 + 1)^* 00 (0 + 1)^* 11 (0 + 1)^*$ .
If 11 appears before 00: The string has the form $(0 + 1)^* 11 (0 + 1)^* 00 (0 + 1)^*.$

Factoring out the outer $(0 + 1)^*$ terms yields:

(0 + 1)^* (00 (0 + 1)^* 11 + 11 (0 + 1)^* 00) (0 + 1)^*

Comparing with other options:

Option A requires 00 and 11 to be immediately adjacent (0011 or 1100), missing strings like 001011.
Option C uses addition ( $+$ ), which represents strings having two consecutive 0s OR two consecutive 1s.
Option D omits arbitrary leading and trailing bits.

Final answer

Common trap

Choosing option A, which enforces adjacent substrings 0011 or 1100 and omits intervening characters.

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

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
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