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

Comments

we can pump any number of 0's and 1's before and after both the 0's , so bounding 1's or 0's does not makes sense, atmost option eliminated.

the smallest string is 00 , that means # of 0's must be atleast 2 , i.e this language is set of all binary strings with atleast 2 0's

---

In case someone is confused in option A please read this 

Substring: a contiguous block of characters from a string, e.g., for "hello" → "ell" is a substring.

 

Subsequence: characters in the same order but not necessarily contiguous, e.g., for "hello" → "hlo" is a subsequence

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

​​​​​​C. As the regular expression will have atleast 2 0’s.

Answer 4

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 5

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.

Answer 6

Loos at the expression it is telling you that You can take anything but you have to take that Two zeroes which are already in the expression rather than that you can go for another zeroes also but two 0s are mandatory so C is the ans