On 5/24/2013 11:20 AM, Orchid Win7 v1 wrote:
> Suppose I give you two arbitrary regular expressions. Are they equivalent?

It depends on what you specifically mean by "regular expression", but 
probably this problem is PSPACE-complete.  From what I can tell is 
generally solved by converting each regexp into a DFA and checking if 
they are isomorphic.

> Does there exist an algorithm to determine whether two regexes are
> equivalent? What complexity class does this algorithm live in? What does
> "equivalent" even mean in this context? What about if one expression
> matches a subset of the other? Or a superset? Or in general two
> partially-overlapping sets?

There exists a Perl library to do some related computations of this 
sort, although it will sometimes fail to detect an equivalence (but I 
think never detects a false equivalence).

http://search.cpan.org/~vbar/Regexp-Compare-0.17/lib/Regexp/Compare.pm

Post a reply to this message