这个 NFA 是否正确地接受以 00 结尾的输入?

Is this NFA correctly accepting inputs that end with a 00?

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

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

是的,它是给定定义的正确 NFA。

But if the input would be 001 we would on some path also end up in the acceptance state (z2) but it would not be possible to go back to another state when reading the last character, the one. That would mean, a wrong input was accepted.

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

编辑:

... an NFA accepts a string w if it is possible to make any sequence of choices of next state, while reading the characters of w and go from the start state to any accepting state.

摘自 John E. Hopcroft、Rajeew Motwani、Jeffret D. Ullman 着的自动机理论、语言和计算导论一书(2006 年,第 59 页)。