The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
50 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 (295 points) | 50 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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,834 questions
36,686 answers
90,617 comments
34,640 users