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)

    Oops,

    i think i used one step wrong:
    empty string + p = p
    erom formula nei……

    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
              • Views706 times
              • Answers6 answers
              • Followers1 follower
              Question and answer is powered by AnsPress