为了找到一个同步词，我总是使用反复试验，这对于小型 DFA 来说很好，但在大型 DFA 上就没那么有用了。然而，我想知道的是，是否存在一种用于确定同步词的算法，或者是否有一种方法能够判断一个同步词不存在。（而不是仅仅说“我找不到一个，因此一个不存在”，这绝不是一个证明）。
我已经在谷歌上环顾了一下，到目前为止，我只是遇到了一些方法来确定同步词长度的上限和下限将基于状态的数量，但这对我没有帮助。
问问题
291 次
1 回答
0
同步词长度上限的存在立即意味着存在一种（非常慢的）算法来找到一个：只需列出所有长度小于上限的字符串并测试每个字符串是否是同步词。如果其中任何一个存在，则存在同步词，如果都不存在，则不存在同步词。但是，这是指数级的缓慢，因此不建议在大型 DFA 上使用。
David Eppstein 设计了一个多项式时间算法来查找 DFA 中的同步词，尽管我对这个算法不是很熟悉。
希望这可以帮助！
于 2013-11-17T18:48:32.573 回答