intersection - 如何将两个相交的 DFA 转换为最小 DFA

Question

我有以下问题：有两个确定性有限自动机应该相交并转换为单个最小确定性有限自动机。有没有算法可以做到这一点？

我知道我可以通过创建两个自动机的笛卡尔积并将结果转换为 DFA 来创建 NFA，但这是一个耗时的过程。有没有更简单的方法来创建两个自动机的交集？

顺便说一句：这是解决方案：

我尝试了我下面描述的方法，但我无法想象如何获得解决方案：计算两个 DFA 的补码为我的两个新 DFA 提供了恰好两个接受状态。现在我必须将它们组合起来并最小化它们，但是我从哪里可以得到第三个接受状态呢？

Answer 1

据我所知，没有“直接”算法可以做到这一点。你可以这样做

• 最小化两个输入 DFA，
• 计算他们的笛卡尔积（顺便说一下，它产生另一个 DFA，而不是 NFA），然后
• 最小化结果。

最小化两个输入 DFA 并不是绝对必要的，但它可以帮助提高效率。如果你有一个 n-state 和一个 m-state DFA，它们的笛卡尔积将有 O(mn) 个状态。DFA 最小化算法运行时间为 O(k ² )，其中 k 是 DFA 中的状态数，因此如果原始 DFA 的大小为 n 和 m，则计算笛卡尔积然后最小化将花费时间 O(m ² n ² )，而最小化，然后计算笛卡尔积，然后再次最小化需要时间 O(m ² + n ² + m' ² n' ² )，其中 m' 和 n' 是最小化 DFA 的大小。

希望这可以帮助！