On Thu, 21 Oct 2004 15:37:57 +0000, Eivind Eklund <eeklund / gmail.com> wrote:
> 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.

I should probably include some suitable references so somebody can run
off an implement this:

Subtyping with Antimirov's algorithm:
http://www.inf.uni-konstanz.de/dbis/teaching/current/pathfinder/download/hohenade-ausarbeitung.pdf

Partial derivatives of regular expressions and finite automata
http://citeseer.ist.psu.edu/antimirov95partial.html

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