nfa - 这个 NFA 是否正确接受以 00 结尾的输入？

Question

在一次讲座中，据说这个 NFA 接受以两个零或输入 = 0 结尾的输入：https ://ibb.co/9Wt0j7J 。字母表是 {0,1}

但是如果输入是 001，我们会在某些路径上也最终处于接受状态 (z2)，但是在读取最后一个字符时不可能回到另一个状态。这意味着接受了错误的输入。所以，我的问题是：在不改变任何东西的情况下，NFA 真的构造正确吗？如果是，为什么？如果没有其他箭头指向另一个状态，我是否可以假设我们进入“空（不可见）状态（错误状态而没有明确提及）”或类似的状态？

Answer 1

是的，对于给定的定义，它是正确的 NFA。

但是如果输入是 001，我们会在某些路径上也最终处于接受状态 (z2)，但是在读取最后一个字符时不可能回到另一个状态。这意味着接受了错误的输入。

如果你输入 001，它不会接受它，因为 NFA 会检查所有可能的路径并消除卡住的路径。所以你会在前两个0之后进入z2，但是在读到1之后，它会卡住并被淘汰。

编辑：

... NFA 接受字符串 w 如果可以对下一个状态进行任何选择序列，同时读取 w 的字符并从开始状态进入任何接受状态。

摘自John E. Hopcroft、Rajeew Motwani、Jeffret D. Ullman（2006 年，第 59 页）的《自动机理论、语言和计算导论》一书。