The Gateway to Computer Science Excellence
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.
in Theory of Computation by (235 points) | 82 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.

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
50,737 questions
57,405 answers
105,467 users