检查两个正则表达式是否相等/同构的库

Question

我需要一种库，它将接受两个正则表达式并确定它们是否同构（即完全匹配相同的字符串集或不匹配）。 例如，a | b与[ab]同构。

据我所知，正则表达式可以转换为NFA，然后在某些情况下可以有效地转换为DFA。然后，可以将DFA转换为最小DFA，如果我理解正确，则该最小DFA是唯一的，因此这些最小DFA可以进行比较以检查它们是否相等。我意识到，并非所有正则表达式NFA都可以有效地转换为DFA（特别是当它们是从Perl Regexps生成时，这些Regexps并不真正“常规”），在这种情况下，理想情况下，该库将返回错误或其他指示表明转换不可能。

我看到网上有很多关于这个问题的文章和学术论文（甚至有一些为了让学生完成这个任务的编程作业），但我似乎找不到实现此功能的库。我更喜欢Python和/或C/C++库，但是任何语言的库都可以。有没有人知道这样的库？如果没有，是否有人知道一个接近的库，可以作为起点使用？

- user1255384

---

不行，这是一个研究项目的一部分。但这不是该项目的核心，所以如果不必要，我不想花时间自己开发。 - user1255384

我只是开玩笑而已。这是一个非常好的问题。所以加一。 - user405725

实际上，最小化的DFA不应该直接进行相等比较，但是它们可以通过图同构进行比较以确定等价性。 - Fred Foo

Answer 1

我没有尝试过，但Perl的Regexp:Compare看起来很有前途： 如果第一个正则表达式的语言是第二个正则表达式的子集，那么两个正则表达式是相���的，反之亦然。

- user1071136

---

我检查了一下，看起来它正好符合我的要求。从快速浏览代码中，我无法确定它是如何实现的，但在我测试的所有简单情况下都运行良好。感谢指引！ - user1255384

Answer 2

Java的brics自动机库支持此功能。它可用于将正则表达式转换为最小确定有限状态自动机，并检查它们是否等效：

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

请注意，此库仅适用于描述正则语言的正则表达式：不支持一些更高级的功能，如反向引用。

- ChrisBlom