edited by
37,236 views
64 votes
64 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)^*$
edited by

8 Answers

Best answer
73 votes
73 votes

 "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
edited by
21 votes
21 votes

method 1: draw the dfa and get the regular expression 

method 2:by verification

19 votes
19 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
1 votes
1 votes
£* {0,1}  = {€, 0,1 ,01 ,11 , 000, 001, 010, 100, 011,101,110,111,.............}

And language L containing sub- string 100 I.e L =(0+1)*100

If we subtract £* -L then we get only those string which not having substring as 100

£*-L = {€, 0, 1, 00, 11, 10,01, 000, 001, 010, 011, 101, 110, 111,............ }

Let's check options ,

A) false beacse It can not generate string 01 but it is present in £*-L hence option A fails

B) it produce sub-string 100 in 10100 string so it fails and it can not produce € so it fails

C) unable to produce € hence it fails

D) it produce all string over £*-L hence option D correct
Answer:

Related questions

38 votes
38 votes
5 answers
1
21 votes
21 votes
1 answer
2
Kathleen asked Sep 29, 2014
4,792 views
Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.Which of the following statements is true?$T(n) = O...
24 votes
24 votes
1 answer
3
Kathleen asked Sep 29, 2014
14,258 views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...