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

Question

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

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

我在网上看到了大量的文章和学术论文（甚至还有一些课程的编程作业要求学生这样做），但我似乎找不到一个实现这个功能的库。我更喜欢Python和/或C/C++库，但是任何语言的库都可以。有人知道这样的图书馆吗？如果没有，有人知道有一个图书馆离我很近，我可以用它作为起点吗？在

Answer 1

Java的brics automaton library也支持这一点。您可以使用它将正则表达式转换为DFA检查这些表达式是否等效。在

Answer 2

虽然没有尝试过，但是Perl的Regexp:Compare看起来很有前途：如果第一个regex的语言是第二个regex的子集，那么两个regex是等价的，反之亦然。在