Which one of the following regular expressions represents the language: the…
2016
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive \(0s\) and two consecutive \(1s\)?
- A.
((0 + 1)*0011(0 + 1)* + (0 + 1)*1100(0 + 1)*)
- B.
((0 + 1)*(00(0 + 1)*11 + 11(0 + 1)*00)(0 + 1)*)
- C.
((0 + 1)*00(0 + 1)* + (0 + 1)*11(0 + 1)*)
- D.
(00(0 + 1)*11 + 11(0 + 1)*00)
Attempted by 133 students.
Show answer & explanation
Correct answer: B
Key idea: the string must contain both the substring "00" (two consecutive 0s) and the substring "11" (two consecutive 1s). The order can be either one first.
Allow any prefix: (0+1)*
Require both substrings in either order: 00(0+1)*11 or 11(0+1)*00
Allow any suffix: (0+1)*
Putting this together gives the regular expression: (0+1)*(00(0+1)*11 + 11(0+1)*00)(0+1)*
This is equivalent to writing the two cases with explicit prefixes and suffixes as a union: (0+1)*00(0+1)*11(0+1)* + (0+1)*11(0+1)*00(0+1)*
Therefore the given expression (0+1)*(00(0+1)*11 + 11(0+1)*00)(0+1)* correctly describes the language.
A video solution is available for this question — log in and enroll to watch it.