theory - 有限时间内两个 FSM 等价的一般证明？

Question

是否存在两个（确定性）有限状态机的等价性且总是需要有限时间的一般证明？也就是说，给定两个 FSM，你能否证明给定相同的输入，它们总是会产生相同的输出，而实际上不需要执行 FSM（这可能是非终止的？）。如果确实存在这样的证明，那么时间复杂度是多少？

Answer 1

有证据，虽然我不知道。查找 Sipser 关于该主题的教科书，这就是我知道的地方。

搜寻我的记忆：基本上，对于给定的 DFA，有一个唯一的最小 DFA，并且有一个总是终止的最小化算法。最小化 A 和 B，看看它们是否具有相同的最小 DFA。我不知道最小化的复杂性，尽管它还不错（我认为它是多项式）。图同构很难计算，但是因为有一个特殊的起始节点，它可能会更容易一些。老实说，您甚至可能不需要图同构。

但是不，您不需要实际运行 DFA，只需分析它们的结构即可。

Answer 2

假设您有两个具有 O( n ) 状态的 FSM。然后你可以制作一个大小为 O( n ² ) 的 FSM，它只识别它们接受语言的对称差异。（创建一个 FSM，其状态对应于一对状态，每个 FSM 一个。然后在每个步骤中，同时更新该对的每个部分。新 FSM 中的状态是接受状态，当且仅当该对中的一个是一个接受状态。）现在最小化这个 FSM，看看它是否与拒绝一切的平凡单态 FSM 相同。最小化具有m个状态的 FSM 需要时间 O( m log m )，因此总体而言，您可以在 O( n ² log n ) 时间内完成所有操作。

@Agor 正确地指出，Sipser 是这类事情的一个很好的参考。我回答的关键点是，即使指数很小，你也可以在多项式时间内做到这一点。