25

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

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

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

4

2 回答 2

10

还没有尝试过，但是Regexp:Compare for Perl 看起来很有希望：如果第一个语言是第二个的子集，则两个正则表达式是等效的，反之亦然。

于 2012-03-07T20:33:48.817 回答
1

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);
}

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

于 2013-07-17T22:14:16.243 回答