From: Eivind Eklund <eeklund@...>
Date: 2004-10-22T00:38:00+09:00
Subject: Re: Regexp equality

On Wed, 20 Oct 2004 09:06:10 +0900, Lloyd Zusman <ljz@asfast.com> wrote:
> Not only is it a tall order to determine whether any two regex's will
> match exactly the same set of strings, but in the general case, I'm
> pretty sure that this question is undecidable.

As far as I can tell: If you run Antimirov's algorithm for NFA
construction, you can compare each extracted partial derivative and
see if it is equal.  If all extracted partial derivatives are equal,
your regular expressions are identical.  If any differ - they're
different.

Eivind.
-- 
Hazzle free packages for Ruby?
RPA is available from http://www.rubyarchive.org/