ACE TOC Test

Question

 

Which of the following regular expression represent the set of all the strings not containing $100$ as a substring ?

• A. $0^*(1^*0)^*$
• B. $0^*1010^*$
• C. $0^*1^*01^*$
• D. $0^*(10+1)^*$

Comments

Ref here :GATE CSE 1997

Answer 1

for option A:    $0^{*}(1^{*}0)^{*}$

$0^{0}(1^{*}0)^{2} = (1^{*}0)(1^{*}0) = 100 \Rightarrow$ here $100$ exists as a substring.

for option B:    $0^{*}1010^{*}$

$0^{0}1010^{2} = 10100 \Rightarrow$ here $100$ exists as a substring.

for option C:    $0^{*}1^{*}01^{*}$

Here no combination will give $100$ as substring as there can be only one 0 followed by a 1.

edit(thanks for pointing out my mistake): 

Option C will not contain set of all strings not containing $100$ as substring. eg. string $1010$ does not contain $100$ as substring but is not defined by option C

for option D:    $0^{*}(10+1)^{*}$

Here too after every 0 there can be 0 or more 1s and we cannot get a one followed by two consecutive zeroes.

eg. $0^{3}(10+1)^{2} = 000(10+1)(10+1) = (0001010, 000101, 000110, 00011)$

So option D is correct choice

 

Comments

@Pratik.patil read my comment again!!

---

@Pratik.patil see the question, they are asking

$\color{Cyan}\text{“Set of all string which does not contain 100 as substring”}$

but, $0^{*} 1^{*}01^{*}$ does $NOT$ contain all the strings which “does not contain 100 as substring”

Ex $:$ “$\epsilon$” 

So $Option \ C$ also $\color{Red} \text{Wrong}\ !$ 

---

$\color{Red}\text{Wrong}$

Answer 2

D

in A we can make the 100 (0* is E and (1*0)(1*0)(1*0) => 100)

in B last 10* is there so,100 will come
in C 100 wont come but the language contain E(Epsilon) but opton wont support

in D it accepts the language which is correct answer

Comments

in c , yes this should be right but in  option C doesnot  generate all string related to this like 110