NFA到DFA转换的简洁描述？

Question

有人可以比我更简洁地向SO社区描述NFA到DFA的转换算法吗？(最好是500字以内.)我见过的图表和讲座只会让我以为我曾经认识的东西感到困惑.我最有信心从状态图生成初始NFA转换表,但之后,我丢失了epsilons和子集中的DFA.

1)在转换(delta)表中,哪一列代表新的DFA状态？它是生成状态的第一列吗？

2)在下面我的例子的第{2,3}行中,{2,3}在状态图方面对NFA的意义是什么？(对不起,我必须在图片中思考.)我认为这将是DFA中的"输入0回环"？

3)从表格到DFA或识别所得到的DFA的接受状态的任何简单的"经验法则"？

有限自治

delta  |  0    |  1     |
=======+=======+========+
{1}    |{1}    |{2}     |
{2}    |{3}    |{2,3}   |
{3}    |{2}    |{2,4}   |
{2,3}  |{2,3}  |{2,3,4} |
{2,4}  |{3,4}  |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4}  |{2,4}  |{2,4}   |

---

编辑:这是上面的点格式表,欢呼Regexident.

digraph dfa {
    rankdir = LR;
    size = "8,5"
/*  node [shape = doublecircle]; "1";*/
    node [shape = circle];

    "1" -> "1" [ label = "0" ];
    "1" -> "2" [ label = "1" ];

    "2" -> "3"   [ label = "0" ];
    "2" -> "2_3" [ label = "1" ];

    "3" -> "2"   [ label = "0" ];
    "3" -> "2_4" [ label = "1" ];

    "2_3" -> "2_3"   [ label = "0" ];
    "2_3" -> "2_3_4" [ label = "1" ];

    "2_4" -> "2_3"   [ label = "0" ];
    "2_4" -> "2_3_4" [ label = "1" ];

    "2_3_4" -> "2_3_4" [ label = "0" ];
    "2_3_4" -> "2_3_4" [ label = "1" ];
    "3_4" -> "2_4" [ label = "0" ];
    "3_4" -> "2_4" [ label = "1" ];
}

这里呈现的形式:

注意:该表缺少有关状态接受的任何信息,因此图表也是如此.

Answer 1

当您从NFA构造DFA时,您基本上可以找到NFA可以在一段时间内的那些状态集(如模拟NFA).首先,从开始状态开始,然后找到可以通过epsilon过渡到达的所有状态.这组状态形成了生成的DFA的开始状态.然后,您将跟踪此状态集的传出转换.这些可能导致另一个NFA状态,因为您发现状态可以通过epsilon输入再次到达,并且您将获得另一组NFA状态,这将是新的DFA状态.您完成此过程直到完成.

关键是,生成的DFA状态将成为兼容的旧NFA状态的集合(关于epsilon转换).这些集合也可能重叠,即没有错误.现在我可以回答你的问题:

1)第一列代表新的DFA状态.它显示了形成给定DFA状态的NFA状态集.

2)您的假设是正确的,这意味着在0输入上回送到状态{2,3}.

3)可以从该表中轻松构建DFA表,只需用字母命名状态即可.包含至少一个NFA接受状态的任何DFA状态也将成为DFA中的接受状态.

我希望我很清楚.

Answer 2

核心思想可能是理解DFA是一种叠加在NFA之上的机器。虽然 NFA 在节点数量或其与问题的关系方面更简单，但它的规则相当微妙且复杂（它会进入正确的状态，无论哪种状态）。dfa 就其包含的节点而言要复杂得多，但规则非常简单，因为任何给定输入都只有一个输出状态。

这种转变相当简单。DFA 中的每个状态都是 NFA 中状态的子集。DFA的起始状态是仅包含NFA的起始状态的集合，DFA的接受状态是其所有以NFA的接受状态为元素的状态。

DFA 中的过渡是唯一棘手的部分。NFA 是不确定的，因为给定输入的输出状态是一组状态，但 DFA 将相应的 NFA 状态集作为其自己的状态，表示自动机可能处于哪个 NFA 状态。因此输出任何给定输入的任何 DFA 状态的状态是该 DFA 状态的所有 NFA 状态的输出状态的 并集。

就实际实现而言，DFA 的状态人口本质上是 NFA 状态的幂集。IE，n 个 NFA 状态为 2^(n)。在实践中，它通常要小得多，但没有通用的方法来预测它的大小，因此一些实用的 NFA 到 DFA 实现会在到达 DFA 状态时动态生成它们并缓存它们。一旦创建了一定数量的状态，最近最少使用的状态就会被丢弃，从而限制了缓存的大小。