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

edited | 6k views

"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$
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???

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)

method 1: draw the dfa and get the regular expression

method 2:by verification

by Junior (903 points)
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...

1
2