GATE CSE 2009 | Question: 15

Question

Which one of the following languages over the alphabet $\{0,1\}$ is described by the regular expression: $(0+1)^*0(0+1)^*0(0+1)^*$?

• A. The set of all strings containing the substring $\text{00}$
• B. The set of all strings containing at most two $\text{0}$'s
• C. The set of all strings containing at least two $\text{0}$'s
• D. The set of all strings that begin and end with either $\text{0}$ or $\text{1}$

Answer 1

Correct Option: C

Counter example for other choices:

• A. $1010$ is accepted which doesn't contain $00$
• B. $000$ is accepted
• C. is the answer.
• D. $01$ is not accepted

Answer 2

a) all string contain substring 00

regular expression = Anything 00 Anything  = (0+1)*00(0+1)*  

b)all string contain atmost two 0's

regular expression = only 2 zeros  + only 1 zero  + No zero = Anthing 0 Anything 0 Anything + Anything 0 Anything  + Anything = 1*01*01* + 1*01* + 1* 

here anything means that is made of only 1's bcoz we have to restrict 0 (only two or less) so anything cannot include 0.

c) all string contain atleast two 0's

regular expression = Anything 0 Anything 0 Anything = (0+1)*0(0+1)*0(0+1)*

d) all strings that begin and end with either 0 or 1

regular expression = either 0 or 1  Anything either 0 or 1 = (0+1)(0+1)*(0+1)

Comments

All are same for strings containing atleast 2 0's.

---

I think in (d) reg ex should be  (0+1)(0+1)*

Answer 3

The regular expression has two 0′s surrounded by (0+1)* which means accepted strings must have at least 2 0′s.

So, C is the answer

Answer 4

Option A is false, as the regular expression generates string “010” which doesn’t have “00” as substring.

Option B is false, as we can have the string “000” from the given regular expression, which has more than two 0’s.

Option D is false, as we cannot generate the string “01” from the given regular expression and according to option D, string “01” must be generated by regular expression, which clearly shows option D is not correct language as per regular expression.