检查 2 个最小 DFA 是否等效
Check if 2 minimum DFA are equivalent
我有 2 个最小化 DFA，我需要检查它们是否等效。
如果它们是等价的，那么问题就是要找到一个有效的状态比较而不管不同的标签。在我的例子中，DFA 是 table，那么我需要找到将第一个 DFA 的行与第二个 DFA 的行相匹配的排列。
我还考虑过对 DFA 进行广度优先搜索并创建状态的最小访问字符串，然后将第一个列表与第二个列表进行比较（这应该与特定输入无关，例如： 001 和 110 可以互换）。
我对直接和低效的算法以及更复杂的算法都很感兴趣。
正确的方法是构建另一个 DFA：
L3=(L1-L2) U (L2-L1)
并测试 L3 是否为空。如果 L3 为空则 L1=L2，否则 L1<>L2
我找到了这些算法：
- Symmetric difference
- Table-filling algorithm
- Faster Table-Filling algorithm O(n^2)
- Hopcroft algorithm
- Nearly Linear algorithm by Hopcroft and Karp
完整的参考是：
我接受了这个回答，因为@abbaasi 的回答太不完整了。
我会接受任何其他有重大贡献的答案。
我记得最小的 DFA 是唯一的。所以如果你有2个最小化的DFA，我想你只需要检查它们是否相同。
我有 2 个最小化 DFA，我需要检查它们是否等效。
如果它们是等价的，那么问题就是要找到一个有效的状态比较而不管不同的标签。在我的例子中，DFA 是 table，那么我需要找到将第一个 DFA 的行与第二个 DFA 的行相匹配的排列。
我还考虑过对 DFA 进行广度优先搜索并创建状态的最小访问字符串，然后将第一个列表与第二个列表进行比较（这应该与特定输入无关，例如： 001 和 110 可以互换）。
我对直接和低效的算法以及更复杂的算法都很感兴趣。
正确的方法是构建另一个 DFA： L3=(L1-L2) U (L2-L1) 并测试 L3 是否为空。如果 L3 为空则 L1=L2，否则 L1<>L2
我找到了这些算法：
- Symmetric difference
- Table-filling algorithm
- Faster Table-Filling algorithm O(n^2)
- Hopcroft algorithm
- Nearly Linear algorithm by Hopcroft and Karp
完整的参考是：
我接受了这个回答，因为@abbaasi 的回答太不完整了。 我会接受任何其他有重大贡献的答案。
我记得最小的 DFA 是唯一的。所以如果你有2个最小化的DFA，我想你只需要检查它们是否相同。