# Which of the following four regular expressions are equivalent ?

0

Which of the following four regular expressions are equivalent ?
(e = empty string)
(i) (00)*(e+0)
(ii) (00)*
(iii) 0*0*
(iv) 0(00)*

Ravi Garg edited question

0
Debasish Ray Chawdhuri (anonymous)

Guys I have finally come to the correct solution: (i) & (iii)
(00)*(e+0)
= even no. of 0’s and ( empty string or 0)
= (00)*e + (00)*0 [Using distributive law]
= (00)* + (00)*0 [Using Re=eR=R]
= Even no. of 0’s OR Odd No. of Zeroes [Since, + is OR]
Hence the only option which gives this is
(iii) 0*0*
Option (ii) (00)* -> Even no. of 0’s
Option (iv) 0(00)* -> Odd no. of Zeroes.

0
Somak Sengupta (anonymous)

(i) and (iii) are equivalent.

0
Debasish Ray Chawdhuri (anonymous)

i and iv I guess.

0
Somak Sengupta (anonymous)

No, its (i) and (iii)

(00)*(e+0)= any number of zeros(even+0dd)+ empty string
(00)*= empty string + even number of zeros
0*0*=any number of zeros+empty string
0(00)*=odd n of zeros

0
Debasish Ray Chawdhuri (anonymous)

Hey Somak Sengupta,
(00)*(e+0) = (00)*0 [ e+P = P ]
(00)*0 = 0(00)* [ (PQ)*P = P(QP)* ]
This way (i) & (iv) are equivalent.