edited by
20,618 views
57 votes
57 votes

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?

  1. $(0+1 )^ *0011 (0+1)^* +(0+1)^*1100(0+1)^*$
  2. $(0+1)^* (00(0+1)^*11+11(0+1)^*00)(0+1)^*$
  3. $(0+1)^*00(0+1)^* + (0+1)^*11 (0+1)^*$
  4. $00(0+1)^*11 +11(0+1)^*00$
edited by

4 Answers

Best answer
129 votes
129 votes

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

edited by
8 votes
8 votes
  1. $(0+1 )^ *0011 (0+1)^* +(0+1)^*1100(0+1)^*$  $\rightarrow$ Strings containing $0011$ or $1100$ as a substring.
  2. $(0+1)^* (00(0+1)^*11+11(0+1)^*00)(0+1)^*$  $\rightarrow$ Strings having two consecutive $0$s AND $1$s
  3. $(0+1)^*00(0+1)^* + (0+1)^*11 (0+1)^*$  $\rightarrow$ Strings having two consecutive $0$s OR $1$s
  4. $00(0+1)^*11 +11(0+1)^*00$ $\rightarrow$ Strings starting with $00$ and ending with $11$ or vice versa.

Option $B.$ is correct.

2 votes
2 votes
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.
0 votes
0 votes
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
Answer:

Related questions