我试图通过给出两种语言 L1 和 L2 来确定它们是否等效（L1 = L2）来找出算法是什么。
正如我发现的那样，想出一个令人惊讶的困难，尽管我很确定它需要首先转换为 DFA，然后将它们中的每一个都减少到最小的 DFA ..
另外，我知道如果 L1 - L2 和 L2 - L1 为空，则 L1 = L2。
这里有理论好的人吗？
问问题
238 次
2 回答
1
这是一个概念上简单的答案（假设 L1 和 L2 是常规的）。
1) 分别为 L1 和 L2 找到 DFA D1 和 D2。
2) 通过交换接受/不接受状态从 D1 和 D2 构造 D'1 和 D'2（请注意，D'1 完全接受 ~L1 并且 D'2 接受 ~L2，其中 ~ 表示“补码”）
3) 使用标准乘积构造 3 次，生成一个完全接受 (L1 intersect ~L2) 并集 (L2 intersect ~L1) 的 DFA
4) 检查第 3 部分中的 DFA 是否接受任何字符串，方法是检查每个接受状态是否可从起始状态到达。
5) 如果来自第 3 部分的 DFA 接受任何字符串，则 L1 <> L2。否则，L1=L2
您可以使用大量启发式方法来加快速度，但从概念上讲，这可能是最简单的算法。第 3 部分中产品构造的一个很好的参考是 Dexter Kozen 的“Automata and Computability”。
于 2010-11-12T22:08:13.783 回答
1
您可以在此处找到用于测试 re 相等性的合理有效算法的描述：
http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf
挖掘文章的参考资料以找到其他可能效率较低但更易于实施的解决方案。
于 2010-10-14T10:44:34.897 回答