The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+24 votes

Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring?

  1. $0^*(1+0)^*$
  2. $0^*1010^*$
  3. $0^*1^*01^*$
  4. $0^*(10+1)^*$
asked in Theory of Computation by Veteran (59.8k points)
edited by | 5.3k views

4 Answers

+35 votes
Best answer

 "A regular expression denoting a language (set of strings) means it should generate all string in L and not generate any string not in L"

  1. - generates $100$
  2. doesn't generate $0$ (start trying strings in lexicographic order- $0, 1, 00, 01, 10,$...)
  3. doesn't generate $1$
  4. is the answer
answered by Veteran (379k points)
edited by
Epsilon, is also present in the language which is not generated by option b and c so they can be ruled out easily.
Better to start checking  lexicographic order from Epsilon onwards
Doesn’t option (b) also generate 100 ? Because of the last 2 digits in the expression ?
10* which can be 1 or 10 or 100 ....
+8 votes
question says  that does not contain substring 100  . it means except 100 as substring all other string will be accepted and 100 containing substring will be rejected as u see option A and B generate 100  so A nd B is wrong . and c is wrong bcz it must be accept null , 1 etc but it can't so wrong  but D will generate all possible string except 100 as substring
answered by Loyal (5.4k points)
+4 votes

method 1: draw the dfa and get the regular expression 

method 2:by verification

answered by Junior (847 points)
–4 votes
C. seems to be more appropriate than D.
answered by Boss (19.9k points)

(c) doesn't generate  01011

C option doesnt generate null string which is also a possible answer.

Arjun sir ,plz explain once again why option C is wrong ?

01010*1*01* , it can generate 01011 

@radha from c) we are not able to generate $\epsilon$ or $1$ (that doesn't contain $100$)

 Praveen Saini sir but question is only about 100.

Answer should be c and d becoz both will never generate 100 as a substring

question is different.

we need regular expression that generate all strings "those does not contain 100"

i.e , epsilon or 1 should be generated from option C
As sir defines the definition itself in answer,

string 1010 which does not have a substring of 100 should be accepted by option C.we should able to generate that but we cant do that with option C that's why option D will be correct...

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

47,241 questions
51,468 answers
66,754 users