Which of the following four regular expressions are equivalent ?

TOC
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.

    Debasish Ray Chawdhuri answered
      0
      Somak Sengupta (anonymous)

      (i) and (iii) are equivalent.

      Somak Sengupta answered
        0
        Debasish Ray Chawdhuri (anonymous)

        i and iv I guess.

        Debasish Ray Chawdhuri answered
          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

          Somak Sengupta answered
            0
            Debasish Ray Chawdhuri (anonymous)

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

            Debasish Ray Chawdhuri answered
              Add image to editor add image from link

              Question stats

              • Active
              • Views776 times
              • Answers6 answers
              • Followers1 follower
              Question and answer is powered by AnsPress