10

有人能比我简洁地向 SO 社区描述 NFA 到 DFA 的转换算法吗？（最好是 500 字或更少。）我看到的图表和讲座只会混淆我以为我曾经知道的东西。我最有信心从状态图中生成初始 NFA 转换表，但在那之后，我失去了 epsilons 和子集中的 DFA。

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

2) 在我下面示例的第 {2,3} 行第 0 列中，就 NFA 的状态图而言，{2,3} 是什么意思？（对不起，我必须在图片中思考。）我认为这将是 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" ];
}

在这里呈现形式：

渲染点图

注意：该表缺少有关州接受度的任何信息，因此图表也是如此。

4

3 回答 3

12

当您从 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 中的接受状态。

我希望我足够清楚。

于 2010-12-15T15:38:58.280 回答
4

核心思想大概是理解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 状态时动态生成它们并缓存它们。一旦创建了一定数量的状态，就会丢弃最近最少使用的状态，从而限制缓存的大小。

于 2010-12-15T15:37:04.140 回答
0

假设输入 NFA 为 (S, Q, q0, T, F) 其中 S 是输入符号集，Q 是状态集，q0 是开始状态，T 是转换集，F 是集的接受状态。每个转换都是一个三元组 (q, s, r)，其中 q 和 r 是状态，s 是长度为 0 或 1 的字符串。

对于任何有限字符串 s，令 D(s) 是所有状态的集合，这些状态可以从 q0 沿着一条转换路径到达，该转换路径的标签连接在一起形成 s。

该算法需要做的是构造一个确定性自动机，其状态是 Q 的子集，并且对于任何字符串 s，DFA 将最终处于状态 D(s)。

如果是这种情况，那么任何包含 NFA 接受状态的 DFA 状态都应该是 DFA 的接受状态。

考虑空字符串 epsilon；D( “” ) 将是 q0 的 epsilon-closure，即您可以从 q0 到达的所有状态，仅遵循用空字符串标记的转换。我们称其为 Set Q0。（在您的示例中为 D(“”)={1}。）现在我们“探索”该状态，这意味着：对于每个输入符号 a，您找出该符号的转换应该从状态转到哪里。这会导致您发现更多需要在 DFA 中的状态。（在您的示例中 S={0,1}，因此这些状态将是 D(“0”)={1} 和 D(“1”)={2}。但 D(“0”) 与D{“”); 所以它不是新的。因此，现在唯一已发现但尚未探索的状态是 D(“1”)。) 继续探索状态，直到没有更多已发现但尚未探索的状态。

于 2020-09-28T15:11:46.220 回答