有没有办法找出两个任意正则表达式是否等价？对我来说看起来很复杂，但可能有一些 DFA 简化机制之类的？
问问题
7622 次
4 回答
10
要测试等价性，您可以计算表达式的最小 DFA并进行比较。
于 2009-02-18T09:35:37.660 回答
10
等式的可测试性是正则表达式的经典属性之一。（注意，如果你真的在谈论 Perl 正则表达式或其他一些技术上非常规的超级语言，这不成立。）
将你的 RE 转换为广义有限自动机 A 和 B，然后构造一个新的自动机 AB，使得 A 的接受状态到 B 的起始状态的转换为零，并且 B 的接受状态反转。这给了你一个自动机，它接受 A 接受的所有字符串，除了 B 接受的所有字符串。
对 BA 做同样的事情，并将两者都简化为纯 FA。如果 FA 没有可从起始状态访问的接受状态，则它接受空语言。如果你能证明 AB 和 BA 都是空的，你就证明了 A = B。
Edit嘿，我不敢相信没有人注意到那里的巨大错误——当然是故意的：-p
所描述的自动机 AB 将接受前半部分被 A 接受而后半部分不被 B 接受的字符串。构建所需的AB 是一个稍微棘手的过程。我无法想到它，但我确实知道它是明确定义的（并且可能涉及创建状态以表示 A 中的接受状态和 B 中的非接受状态的产物）。
于 2009-02-18T10:03:12.600 回答
2
这实际上取决于您所说的正则表达式的含义。正如其他发帖者所指出的，将这两个表达式减少到它们的最小 DFA 应该可以工作，但它只适用于纯正则表达式。
现实世界的正则表达式库中使用的一些结构（尤其是反向引用）赋予它们表达非正则语言的能力，因此 DFA 算法不适用于它们。例如，正则表达式 :([a-z]*) \1匹配由空格分隔的相同单词的两次出现（a aandb b但不是b anor a b）。有限自动机根本无法识别这一点。
于 2009-02-18T10:05:18.650 回答
1
这两个 Perlmonks 线程讨论了这个问题（具体来说，请阅读 blokhead 的回复）：
于 2009-02-18T08:49:51.373 回答