sgi*_*ons 6 theory proof state-machine fsm
是否存在总是需要有限时间的两个(确定性)有限状态机的等价性的一般证明？也就是说,给定两个FSM,你能证明给定相同的输入它们总是产生相同的输出而不需要实际执行FSM(可能是非终止的吗？).如果确实存在这样的证据,那么时间复杂度是多少？
ago*_*nst 11
有证据,虽然我不知道.寻找Sipser关于这个主题的教科书,这就是我所知道的.
改变我的记忆:基本上,对于给定的DFA,存在唯一的最小DFA,并且存在始终终止的最小化算法.最小化A和B,并查看它们是否具有相同的最小DFA.我不知道最小化的复杂性,虽然它不是太糟糕(我认为它的多项式).图同构很难计算,但因为有一个特殊的起始节点,所以希望它可能更容易一些.你可能甚至不需要图同构,说实话.
但不,你不需要实际运行DFA,只需分析它们的结构.