NFA 优于 DFA：表示使用更少的内存。
NFA 与 NFA 相比的缺点： 较慢地得出答案。
还有其他优点或缺点吗？
问问题
2541 次
2 回答
8
我认为您已经大致确定了主要的权衡取舍。NFA 的内存效率更高，因为它们可以在 O(n) 空间中编码 O(2 n ) 个不同的配置，而相同语言的 DFA 可能占用指数空间。您同样正确地认为 NFA 的更新速度较慢；大多数模拟 NFA 的算法需要 O(n) 时间来计算状态转换（其中 n 是状态数），而 DFA 需要 O(1) 时间。
两者之间还有一些其他差异。对于初学者来说，DFA 通常更容易编码，因为对于每一对状态和符号，只有一个转换。这自然适用于转换表的多维数组。相比之下，NFA（或更糟糕的是，ε-NFA）通常需要更复杂的表示，因为任何状态都可能存在大量转换。然而，NFA 确实具有这样的优势，即从复杂结构到自动机的许多转换使用 NFA 更简单。例如，从正则表达式匹配自动机的规范构造会生成 ε-NFA 而不是 DFA，因为通过递归构建较小的 ε-NFA，然后使用 ε-moves 将它们连接在一起，可以最好地表达转换。它' 可以将正则表达式直接转换为 DFA，但这样做要困难得多。类似地，通过探索句柄识别自动机如何根据 NFA 而不是根据 DFA 工作，可以更直观地激发许多生成 LR(k) 解析器的算法（尽管生成这些解析器的大多数算法直接使用 DFA 而不是 NFA ）。
希望这可以帮助！
于 2011-02-04T03:28:36.087 回答
1
NFA 表示更紧凑，但 DFA 更容易模拟。当 NFA 减少到 DFA 时，通常会出现指数大小的增长
于 2011-02-04T03:29:33.097 回答