GATE CSE
First time here? Checkout the FAQ!
x
0 votes
36 views
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

    7194 Points

  2. Warrior

    2686 Points

  3. Arjun

    2594 Points

  4. rishu_darkshadow

    2568 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,164 questions
33,743 answers
79,994 comments
31,124 users