nfa - 对这个 NFA 句子感到困惑

Question

在我的教科书中“在这些情况下，与这些状态相对应的 NFA 存在的线程简单地死了”是什么意思？

Answer 1

A, B, C, D考虑具有状态、输入字母表{0}和由下式给出的转移函数的非确定性有限自动机

canGoFrom(A, 0) = {B, C}
canGoFrom(B, 0) = {}
canGoFrom(C, 0) = {D}
canGoFrom(D, 0) = {}

也就是说，它看起来有点像这样：

    A
   / \
  B   C
       \
        D

所有边缘都指向下方并带有标签0。假设这D是接受状态。

假设您现在要检查输入字符串00是否被自动机接受。

您从一个线程开始，读数头指向 first 0，并且处于 start 状态A。当你读到第一个零时，NFA 可以进行两次转换，并且它必须同时进行所有可能的转换，因此 NFA 存在的线程分为两个线程：一个现在处于 state B，另一个处于 state C。

现在自动机必须消耗第二个零。因为存在的第二个线程canGoFrom(C, 0) = {D}，它很高兴地从接受状态过渡C到接受状态D，没有进一步分裂。然而，存在的第一根线canGoFrom(B, 0) = {}，也就是它无处可去。在这种情况下，NFA 存在的第一个主线就这样死掉了。它不再对决定是否接受输入做出任何贡献。

如果存在的所有线程都死了，则不接受输入。

在这里，存在的第二个线程达到了接受状态D，因此输入被接受。