computation-theory - 在非确定性有限自动机 (NFA) 中，当有两个或多个转换时，如何选择下一个分支/转换？

Question

对于 NFA，当有 2 个或多个转换状态时，机器如何决定采取哪个转换？

我只能找到“猜测和验证”方法，我们认为系统是千里眼的，并且总是使用二叉树选择正确的路径。

这是唯一的方法吗？我们是否也可以认为它同时存在于两个州？

标签： computation-theorynfa

Answer 1

您可以将其视为尝试所有可能的选项，如果存在从初始状态到接受状态的路径，则 NFA 接受该词。