The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
The regular expression denoting the set of all strings not containing two consecutive 1's is given by

A)     (0+10)*(EPSILON+0)

B)      (1+01)*

C)    (0+10)*(EPSILON+1)

D)    (EPSILON+0)(001)*(EPSILON+0)
asked in Theory of Computation by (17 points) | 32 views
Is the answer c?
I'm also getting option  C but it is not the answer given
I guess option c is right because

Option A : We cannot generate string 1,01,or 101 etc

Option B : We cannot generate string 0 , 10 and so on

Option D : We cannot generate string 1, 10 etc

take the complement of the dfa that you will make for dfa accepting 11 and write the reg. expression. u will easily get option C

The answer is c.

(a+b)* has all the combinations of a and b.

so in (0+10)*(EPSILON + 1), you will have all combinations of 00,01,10 but not 11. Also you will preserve the empty string and the single length strings 0 and 1.

1 Answer

0 votes
option c
answered ago by Junior (769 points)

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

38,103 questions
45,601 answers
49,195 users