edited by
18,979 views
56 votes
56 votes

The regular expression $0^*(10^*)^*$ denotes the same set as

  1. $(1^*0)^*1^*$
  2. $0+(0+10)^*$
  3. $(0+1)^*10(0+1)^*$
  4. None of the above
edited by

12 Answers

0 votes
0 votes
B and C are not giving me choice on no of 1's. They are providing 10 as packs. So leave them.

Option A is good
0 votes
0 votes

This Question is very simple, Only thing we do approaches to the problem in wrong way.

L = 0*(10*)* : To do this type of problem always expand * As precedence of operator is [(*) >( .) > (+)]. Now you will never do this wrong.

hence the L =  0*(10*)* can be expanded like this ->

= 0*{ e + (10*) + (10*)(10*) + (10*)(10*)(10*) +..........}

Now after this just take Alphabet(A) = { 0, 1} and find the what are the strings present in A* or {0,1} * can also be obtain by L = 0*(10*)*.

You will find that L = {0, 1} * = A *.( Which is also a STANDARD RESULT, if you want, you can remember this)

 Ex -  We can generate 100 from L by doing like this -> 0*(10*) = e.(100) = 100.

SIMILARLY by doing the same way,

M = (1*0)*1* 

= {e + (1*0) + (1*0)(1*0) + (1*0)(1*0)(1*0) + ..........} 1*  

By doing the same way you can easily find that it is also equal to {0,1}* or A*. 

Ex - We can also generate 100 from M also in this way -> just take (1*0)(1*0) = (10)(1*0) = (10)(0) = 100.

Hence Both M and L are equal . 

 

 

0 votes
0 votes

Given REX = 0*(10*)* generates Σ* and the minimum string is ε.

Option A : it generates Σ*

Option B  : Two adjacent 1’s cannot be generated because of 10.

Option C : minimum string is 01, hence not the answer.

Hence, Option A is the answer.

0 votes
0 votes

One Useful trick for these questions – U have to check only whether the given expression is making (a+b)*  or not  coz it is  $\sum_{}^{} *$   so unroll the expression and check  if u can make these three things 1) a 2) b 3) * (on the whole expression) then it is sufficient to make it   $\sum_{}^{} *$  .  don’t Remember such properties .

Answer:

Related questions