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

Hey Praveen, thanks for the answer.

I am not able to understand why option D is wrong.

can you explain?

---

try to derive string 010011 or 011100

---

Thank you.

---

Excellent Explanation

Thanks Praveen Saini

---

Nice ans

---

Really Great Explaination.

---

In exam what is the easiest way to think of a string that won't be derivable from given options ?

---

@arjun sir 

having two consecutive 00's and two consecutive 11's 

does it mean that 00 must be followed by 11

---

No!! it simply means that there must be 00 and 11 in the string irrespective of what comes before or after or in between the string.

---

@2019 having 2 consecutive 00 then consecutive 11 means 00 is followed by 11,
if or and "and" is mention then the maximum time they have no relation,

---

option a : break 0011 or 1100 - 000111

option c : It generates 1001

option d: it stops once condition is satisfied but there can be more input like 00110

Hence option b.

---

@Pratik Agrawal

Option D says all strings starting and ending with two consecutive 0's and two consecutive 1's. 

Question isn't asking for starting and ending part, it's asking the general case of "two consecutive 00's and two consecutive 11's" . Option D is more restricted form of the question asked.

---

the set of all binary strings having two consecutive 0's and two consecutive 1's

this means what -

1. exactly 2 consecutive 0's & 2 consecutive 1's

2. atleast "     "            "            "              "

3.only     "                  "                   "                " ,  nothing bother about other.

which one is meant by the question 

---

atleast 2 consecutive 0s and 2 consecutive 1's should be there and we can have 11 before 00 also.

---

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

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