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

Question

是否存在两个总是需要有限时间的(确定性)有限状态机的等效性的通用证明？也就是说，给定两个FSM，您是否可以证明给定相同的输入，它们将始终产生相同的输出，而无需实际执行FSM(这可能是非终止的？)。如果确实存在这样的证明，那么时间复杂度是多少？

Answer 1

有一个证据，尽管我不知道。寻找有关此主题的Sipser教科书，这就是我从中得知的内容。

充实我的内存:基本上，给定DFA有一个唯一的最小DFA，并且有一个总是终止的最小化算法。最小化A和B，并查看它们是否具有相同的最小DFA。我不知道最小化的复杂性，尽管它并不算太糟(我认为它是多项式的)。图同构很难计算，但是由于有一个特殊的起始节点，因此它可能会更容易些。老实说，您甚至可能不需要图同构。

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