The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+27 votes
6k views

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)^*$
in Theory of Computation by Veteran (52.1k points)
edited by | 6k views

4 Answers

+37 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
by Veteran (416k points)
edited by
+17
Epsilon, is also present in the language which is not generated by option b and c so they can be ruled out easily.
+2
Better to start checking  lexicographic order from Epsilon onwards
+2
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 ....
0
I can't understand why option C is wrong.

here also we can't generate a string which contains 100 as substring
0

@MRINMOY_HALDER-Can you generate epsilon(empty language) from option C?

0

so except strings having 100 as a substring, all of sigma* should be in the language???

+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
by Loyal (5.5k points)
+5 votes

method 1: draw the dfa and get the regular expression 

method 2:by verification

by Junior (903 points)
–3 votes
C. seems to be more appropriate than D.
by Boss (19.9k points)
0

(c) doesn't generate  01011

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

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

01010*1*01* , it can generate 01011 

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

 Praveen Saini sir but question is only about 100.

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

+2
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
0
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
49,845 questions
54,784 answers
189,425 comments
80,435 users