2,464 views
3 votes
3 votes
The regular expression 0*(10*)* denotes the same set as

(A) (1*0)*1*

(B) 0 + (0 + 10)*

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

(D) none of these

5 Answers

Best answer
5 votes
5 votes

The best method to solve this kind of problem is that to solve it by taking string as example. You just check that what is the string which can be generated by one RE, which can not be generated by other. And for this don't take a long string as example. Take most basic string, that will give you answer most of the time. For example lets solve the above problem.

The smallest string can be generated from the given RE (0*(10*)*) is "epsilon".

For this only option (C) is incorrect. Because option C ((0 + 1)* 10(0 + 1)*) can never generate "epsilon" string. 

Given RE can generate "1", but option B, can not generate "1" hence option B is wrong

Option (A) generates all the strings which can be generated by the given RE. Hence Option A will be the correct answer. 

selected by
8 votes
8 votes
it should be option (A).

0*(10*)* = (1*0)*1*
2 votes
2 votes

it should be opt (a).

0*(10*)* =∈,0,1,10,010,0010,100...........

a. (1*0)*1*= ∊,1,0,10,110,101,1011,110.......it is generating same set of strings by using shifting property

b. 0 + (0 + 10)* = 0,10,010 .......... it is not generating ∈

c. (0 + 1)* 10(0 + 1)* = 10,010........... it is not generating ∈

2 votes
2 votes
(a+b)*=a*(b.a*)*=b*(a.b*)*

1*(0.1*)*

p(q.p)*=(p.q)*p

(1*.0)*.1*

option A)

Related questions

2 votes
2 votes
1 answer
1
himgta asked Jul 8, 2018
1,838 views
Which one of the Regular Expression given defines the same language as defined by R = (a + b)* (aa + bb) (a + b)* ?(a) (a (ba)* + b (ab)*) (a + b)*(b) (a (ba)* + b (ab)*)...
1 votes
1 votes
3 answers
3
rasto mapp asked Sep 2, 2017
371 views
Regular expression always generates a language.Is it true?Why?
2 votes
2 votes
1 answer
4