From: Jamis Buck Date: 2004-10-20T23:58:19+09:00 Subject: Re: Regexp equality Lloyd Zusman wrote: > James Edward Gray II writes: > > >>On Oct 19, 2004, at 1:53 PM, Jamis Buck wrote: >> >> >>>Is there a way to test regexen for equality based on the strings they >>>would match? >> >>Wow. I bet that's a pretty tall order. Pulling from the current Ruby >>Quiz, here are several ways to write a regex to match 1..12: >> >>1|2|3|4|5|6|7|8|9|10|11|12 >> >>\d|1[012] >> >>1?[12]|[03-9] >> >>You're certainly not going to be able to compare like patterns that way. >>Maybe some internal representation, but I would but super impressed to >>see that. >> >>Not at all saying I don't like the idea, just that it's a tall order. > > > 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. > > If I'm not mistaken, I believe that this can be shown to be a reduction > of the Halting Problem. > > In other words, short of feeding every possible character string to both > regex's and comparing the two sets of matches, I don't think that there > is an algorithmic way to measure equivalence of two regex's which don't > have the same external representation. I realize that particular question is most likely impossible to answer for the general case. What I was wanting, though, was to be able to know whether /\/blah/ is equal to %r{/blah}. Surely that's not too hard? As I said, though, converting them both to strings gives the same result, so the strings, at least, are comparable with expected results. - Jamis -- Jamis Buck jgb3@email.byu.edu http://www.jamisbuck.org/jamis