4.8k 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 | 4.8k 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$
4. is the answer
answered by Veteran (363k points)
edited by
+12
Epsilon, is also present in the language which is not generated by option b and c so they can be ruled out easily.
+1
Better to start checking  lexicographic order from Epsilon onwards
+1
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 ....
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.3k points)

method 1: draw the dfa and get the regular expression

method 2:by verification

answered by Junior (787 points)
C. seems to be more appropriate than D.
answered by Boss (19.7k points)
–1

(c) doesn't generate  01011

+6
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

+5
@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

+1
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