edited by
37,234 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

0 votes
0 votes

I think a simple way will be to take all the binary strings of size 3 i.e. 000, 001, 010, 011, 100, 101, 110, 111 and check them in all in all the regular expressions. One can find that only D accepts all the string, leaving 100. So, D is the answer. All we need is one of the 7 binary strings that the expression does not accepts. 

A does simply accepts 100 so not the answer, 

B  only accepts 101 so not the answer

C will not accepts 011, 111, etc

D is left, hence it is the answer.

0 votes
0 votes

The exam centric approach can be found in the following image :

 

The formal method to prove why D is right choice is in the following image :

0 votes
0 votes

The exam centric approach can be found in the following image :

 

The formal method to prove why D is right choice is in the following image :

 

–3 votes
–3 votes
C. seems to be more appropriate than D.
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,257 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$...