Skip to content
GATETECH
Official PYQ · 2016Set 1 · Q18Regular Expressions and Finite AutomataMCQ1 mark

GATE CS 2016 Set 1 Q18 — Regular Expressions and Finite Automata

Explain with AI

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

Choose one option
View worked solution

Answer: B

The language consists of all binary strings that contain both 00 and 11 as substrings. These two substrings can appear in either order:

  1. 00 appears before 11: This is represented by the regular expression: (0+1)∗00(0+1)∗11(0+1)∗(0+1)^* 00 (0+1)^* 11 (0+1)^*
  2. 11 appears before 00: This is represented by the regular expression: (0+1)∗11(0+1)∗00(0+1)∗(0+1)^* 11 (0+1)^* 00 (0+1)^*

Combining both cases using the union (++) operator, we get:

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

By factoring out the common prefix (0+1)∗(0+1)^* and common suffix (0+1)∗(0+1)^*, we get the equivalent expression:

(0+1)∗(00(0+1)∗11+11(0+1)∗00)(0+1)∗(0+1)^* \big(00(0+1)^*11 + 11(0+1)^*00\big) (0+1)^*

This matches Option B.

Why other options are incorrect:

  • Option A: Requires 00 and 11 to be immediately adjacent to each other (i.e., as 0011 or 1100). It fails to generate strings like 001011001011 where they are separated.
  • Option C: Represents strings containing 00 or 11 (or both). For example, it generates 0000, which does not contain consecutive 11's.
  • Option D: Forces the string to start with 00 or 11 and end with the other. It fails to generate strings like 100110100110 which has arbitrary prefix and suffix.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Regular Expressions and Finite Automata questions