6,161 views
5 votes
5 votes
Consider the following regular expressions :

(i) ($(a/b)^{*}$     (ii) $(a^{*}/b^{*})^{*}$  (iii) $((\epsilon /a)b^{*})^{*}$

Which of the following statements are correct ?

(a) (i) ,(ii) are equal and (ii) , (iii) are not .

(b) (i) ,(ii) are equal and (i) , (iii) are not .

(c) (ii) ,(ii) are equal and (i) , (ii) are not .

(d) All are equal

 

Answer is given as (d) . .

 

But , my question is :

from (ii) $(a^{*}/b^{*})^{*}$ : I can derive $(a/\epsilon )^{*}$  , which can give me (a)* . Isn't it so ?

From (i) ($(a/b)^{*}$ : I can not separate a and b .

So , how can they all be equal ?

4 Answers

Best answer
10 votes
10 votes
1. (a + b)*      
2. (a* + b*)*     =(a+b) *  
3. ((null + a)b*)* = (b* + ab*)*
= ((null + b + bb + bbb + .....) + a(null + b + bb + bbb + .....))*
= (b + a + a(all string of b) + null + (all string of b except ))*  //rearranging b*
= (a +b + rest) *

= (a + b)* as anything of rest or their combination is already included in (a+b) *
So all are equal.
selected by
0 votes
0 votes
As of my knowledge a/b means either a or b,so we can select any one of them.
0 votes
0 votes
'/' : its a quotient operator

$\left ( a / b \right )^{*} \rightarrow \left ( \left \{ \right \} \right )^{*} \rightarrow \left ( \epsilon \right )$

$\left ( a^{*}/b^{*} \right )^{*}\rightarrow \left ( \epsilon \right )^{*}\rightarrow \left ( \epsilon \right )$

$\epsilon / a \rightarrow \left \{ \right \}$, $\left \{ \right \}b^{*} \rightarrow \left \{ \right \}$,$\left ( \left \{ \right \} \right )^{*}\rightarrow \left ( \epsilon \right )$
edited by

Related questions

0 votes
0 votes
1 answer
2