NFA与DFA相比有何优缺点？
NFA 相对于 DFA 的优势：表示使用更少的内存。
与 NFA 相比，NFA 的缺点： 得出答案的速度较慢。
还有其他优点或缺点吗？
NFA advantages over a DFA: the representation uses less memory.
NFA disadvantages compared to an NFA: Slower to arrive at an answer.
Are there any other advantages or disadvantages?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为你已经基本明白了主要的权衡。 NFA 的内存效率更高，因为它们可以在 O(n) 空间中编码 O(2n) 种不同的配置，而同一语言的 DFA 可能需要指数空间。您同样正确地认为 NFA 的更新速度较慢；大多数模拟 NFA 的算法需要 O(n) 时间来计算状态转换（其中 n 是状态数），而 DFA 则需要 O(1) 时间。
两者之间还存在一些其他差异。对于初学者来说，DFA 通常更容易编码，因为对于每一对状态和符号来说，只有一个转换。这自然适合用于转换表的多维数组。相比之下，NFA（或更糟糕的是 ε-NFA）通常需要更复杂的表示，因为任何状态都可能存在大量转换。然而，NFA 确实有一个优点，即使用 NFA 可以使从复杂结构到自动机的许多转换变得更简单。例如，从正则表达式构建匹配自动机的规范结构会生成 ε-NFA 而不是 DFA，因为通过递归构建较小的 ε-NFA，然后使用 ε 移动将它们连接在一起，可以最好地表达变换。可以将正则表达式直接转换为 DFA，但这样做要困难得多。类似地，通过探索句柄识别自动机如何根据 NFA 而不是 DFA 工作，可以更直观地激发许多用于生成 LR(k) 解析器的算法（尽管大多数用于生成这些解析器的算法直接进入 DFA 而不是 NFA） ）。
希望这有帮助！
I think you've pretty much nailed the main tradeoffs on the head. NFAs can be more memory efficient because they can encode O(2n) different configurations in O(n) space, whereas a DFA for the same language might take exponential space. You're similarly correct that NFAs have slower updates; most algorithms for simulating NFAs take O(n) time to compute state transitions (where n is the number of states) vs O(1) time for DFAs.
There are a few other differences between the two. For starters, DFAs are usually easier to encode, since for each pair of state and symbol there's exactly one transition. This lends itself naturally to a multidimensional array for a transition table. By contrast, an NFA (or worse, an ε-NFA) usually requires a more complex representation because there can be a large number of transitions for any state. However, NFAs do have the advantage that many transformations from complex structures to automata are simpler with NFAs. For example, the canonical construction of a matching automaton from a regular expression generates an ε-NFA rather than a DFA, since the transformation is best expressed by recursively building up smaller ε-NFAs and then joining them together using ε-moves. It's possible to directly convert the regular expression to a DFA, but it's considerably more difficult to do so. Similarly, many algorithms for generating LR(k) parsers can be more intuitively motivated by exploring how the handle recognition automaton works in terms of NFAs rather in terms of DFAs (though most algorithms for generating these parsers go directly to the DFA rather than the NFA).
Hope this helps!
NFA 表示更紧凑，但 DFA 更容易模拟。当 NFA 简化为 DFA 时，大小通常会呈指数级增长
NFA representations are more compact, but DFA's are easier to simulate. Oftentimes there is an exponential size increase when an NFA is reduced to a DFA