GATE CSE 2016 Set 1 | Question: 18

Question

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

• 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$

Comments

thanks bro

---

@GovindYadav29 don’t forget the last (0+1)*. At last it can generate 00 by having prefix as 0011.

---

A . The set of string that contains 0011 or 1100 as a substring 

B  The set of string that contains either both 00 and11 OR 11 and 00 as a substring

C  The set of strings that contains only 00 OR 11 as a substring 

D the set of strings that start with 00 and end with 11 OR start with 11 and end with 00

Answer 1

Set of all binary strings having two consecutive $0$s and two consecutive $1$s 

Anything $00$  Anything $11$Anything  + Anything $11$ Anything $00$ Anything

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

And it is same after taking common. 

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

So, option B is answer.

Neither they said Both are immediate nor they give a predefined order, so it should be as above

Comments

It will not accept any string starting with 01 or 10 . E.g. '010011'

---

Is 0101001111 a valid string for the given question?

---

Yes.  0101001111

Answer 2

• A. $(0+1 )^ *0011 (0+1)^* +(0+1)^*1100(0+1)^*$  $\rightarrow$ Strings containing $0011$ or $1100$ as a substring.
• B. $(0+1)^* (00(0+1)^*11+11(0+1)^*00)(0+1)^*$  $\rightarrow$ Strings having two consecutive $0$s AND $1$s
• C. $(0+1)^*00(0+1)^* + (0+1)^*11 (0+1)^*$  $\rightarrow$ Strings having two consecutive $0$s OR $1$s
• D. $00(0+1)^*11 +11(0+1)^*00$ $\rightarrow$ Strings starting with $00$ and ending with $11$ or vice versa.

Option $B.$ is correct.

Comments

why not option A ??

If the qsn is meant for atleast.

---

option A is incorrect because we do not want $00$ and $11$ combined. We can't generate $110100$ using it which is a valid string.

---

How will you generate 101001110 using option B?

---

@Satbir,@2021,@tusharp,@Praveen Saini

How option B generate 100101101?

---

$1$ from $(0+1)^*$

$    00 \    10\     11$  from  $00(0+1)^*11$

$01$ from  the last $(0+1)^*$

Answer 3

Option A doesn’t generate string “001011” as it has two consecutive 0’s and two consecutive 1’s.
Option C generates string “00” which doesn’t have two consecutive 1’s.
Option D doesn’t generate string “00110” which has two consecutive 0’s and two consecutive 1’s.

Answer 4

option a tells us about immediate concustive eg 0011 or 1100 ,it is accepted but not part of a language, option c says only about language such 001000 or 1101010 but not 00110011 so not c . option d cannot accept 10011 or 01100 so b is correct