The Gateway to Computer Science Excellence
+20 votes
1.8k views

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)^*$?

  1. The set of all strings containing the substring $\text{00}$
  2. The set of all strings containing at most two $\text{0}$'s
  3. The set of all strings containing at least two $\text{0}$'s
  4. The set of all strings that begin and end with either $\text{0}$ or $\text{1}$
in Theory of Computation by Veteran (52.2k points)
edited by | 1.8k views

4 Answers

+30 votes
Best answer

(C) is the answer.

Counter example for other choices:

  1. $1010$ is accepted which doesn't contain $00$
  2. $000$ is accepted
  3. is the answer.
  4. $01$ is not accepted
by Veteran (430k points)
edited by
+12 votes

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)

by Veteran (57k points)
+1
All are same for strings containing atleast 2 0's.
0 votes
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
by Loyal (9.9k points)
0 votes

A) All strings containing the substrings '00' is FALSE :::: This regular expression can also generate {1010,10101,11010.....}, which doesn't contain '00' as substring.

B) All strings containing at most two 0's is FALSE :::: Because RE can also generate {000,1000.....}

C) All strings containing at least two 0's is TRUE

D) All strings that begin and end with either 0 or 1 is FALSE :::: RE can't generate {01,10...}

by (439 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,252 answers
198,061 comments
104,698 users