First time here? Checkout the FAQ!
0 votes
Is there any method to check equivalence of two regular expressions other than checking all strings of two set?

I mean sometimes I may miss a string.
asked in Theory of Computation by (143 points)   | 36 views
Hmm, you can try making DFAs of the two REs and then minimize them, If you get identical DFAs then the REs are equal
Yaa I thought that but that would take a lot of time right?

I mean lot according to time for each question in GATE??
For exam point of view u can check using some string which is covered by one regular expression but not other..One such string is sufficient to prove that the two regular expressions are not equivalent ..

Or in some cases u can also reduce one regular expression to the other one using standard regular expression identities..

This thing comes with good practice..:)
Yaa using Identities may help!!

Please log in or register to answer this question.

Related questions

Top Users Sep 2017
  1. Habibkhan

    7096 Points

  2. Warrior

    2574 Points

  3. Arjun

    2412 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points

26,115 questions
33,691 answers
31,098 users