NFA是否有最终状态？

我试图证明所有的NFA都可以转换成一个最终状态，但我不知道如何/如果我必须处理0最终状态的情况。NFA是否有最终状态？

2016-09-28 Alex

正式的定义（在维基百科上，我不想抽出我的书）似乎表明这组最终状态可能是空的。所以，除非你有一个断开的NFA（即断开最终状态），否则你不能将它转换为单终态NFA。无论如何，我认为你可以指定“对于所有具有> 0最终状态的NFA”，就像这个问题在这里：http://cs.stackexchange.com/q/14555/29703。在这一点上，cs.stackexchange可能是这个问题的一个更好的地方。 –

由于空集是所有其他集的子集，因此我的书中也没有说明需要成为最终状态。 –

一切都取决于你的定义，但通常为：

的设定受理状态可能为空
并非所有国家都必须在到达从初始状态

任何NFA不接受状态相当于一个具有两种状态的DFA：初始的非接受状态，在所有输入上循环;以及在所有输入上自行循环的无法接受的接受状态。

来源

2016-09-28 13:11:09 Patrick87

NFA是否有最终状态？

回答

相关问题