[Haskell-cafe] Re: ANN: weighted-regexp-0.1.0.0
sebf at informatik.uni-kiel.de
Wed Jul 28 11:41:27 EDT 2010
>>> Oh, by the way, with noMatch, eps, alt and seq_ RegExp is itself a
>> Yes, but it's hard to define an Eq instance for arbitrary regular
>> expressions that reflects equivalence of regexps.
> How hard is this exactly?
The standard algorithm to decide regexp equivalence transforms both
expressions into DFAs and checks whether they are equivalent. DFAs can
be checked for equivalence by forming their in-equivalence-product and
checking whether the result DFA does not accept any input. See
This algorithm is quadratic in the sizes of the DFAs but they can
themselves be exponentially large in the sizes of the regexps.
I don't know whether there is more efficient way to decide regexp
Underestimating the novelty of the future is a time-honored tradition.
More information about the Haskell-Cafe