25

I need a library which will take in two regular expressions and determine whether they are isomorphic (i.e. match exactly the same set of strings or not) For example a|b is isomorphic to [ab]

As I understand it, a regular expression can be converted to an NFA which in some cases can be efficiently converted to a DFA. The DFA can then be converted to a minimal DFA, which, if I understand it correctly, is unique and so these minimal DFA's can then be compared for equality. I realize that not all regular expression NFA's can be efficently transformed into DFA's (especially when they were generate from Perl Regexps which are not truly "regular") in which case ideally the library would just return an error or some other indication that the conversion is not possible.

I see tons of articles and academic papers on-line about doing this (and even some programming assignments for classes asking students to do this) but I can't seem to find a library which implements this functionality. I would prefer a Python and/or C/C++ library, but a library in any language will do. Does anyone know if such a library? If not, does someone know of a library that gets close that I can use as a starting point?

Robᵩ
  • 163,533
  • 20
  • 239
  • 308
user1255384
  • 303
  • 2
  • 8
  • 3
    No. It's part of a research project. But this isn't the core of the project so I'd rather not spend the time to roll my own if I don't have to. – user1255384 Mar 07 '12 at 18:37
  • 2
    I was just kidding. This is a very good question. So +1. –  Mar 07 '12 at 18:43
  • Actually, the minimal DFAs shouldn't be directly compared for equality, but they can be compared for graph isomorphism to determine equivalence. – Fred Foo Mar 07 '12 at 21:05

2 Answers2

10

Haven't tried it, but Regexp:Compare for Perl looks promising: two regex's are equivalent if the language of the first is a subset of the second, and vice verse.

user1071136
  • 15,636
  • 4
  • 42
  • 61
  • 1
    I checked this out and it looks like it does exactly what I want. I can't tell how it's doing it from a cursory look over the code, but it worked in all the simple cases on which I tested it. Thanks for the pointer! – user1255384 Mar 08 '12 at 18:40
1

The brics automaton library for Java supports this. It can be used to convert regular expressions to minimal Deterministic Finite State Automata, and check if these are equivalent:

public static void isIsomorphic(String regexA, String regexB) {
    Automaton a = new RegExp(regexA).toAutomaton();
    Automaton b = new RegExp(regexB).toAutomaton();
    return a.equals(b);
}

Note that this library only works for regular expressions that describe a regular language: it does not support some more advanced features, such as backreferences.

ChrisBlom
  • 1,262
  • 12
  • 17