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/