GATE 2016 CS – Question 28

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

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$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $(0+1)^*(00(0+1)^*11 + 11(0+1)^*00)(0+1)^*$

Explanation

The string needs both a "00" and a "11", in either order, with anything in between and around them. Option B says that. Option A forces them to be next to each other, option C uses a union so only one of them is required, and option D forces the string to start with one pair and end with the other.