NFA相比DFA的优势在于：使用更少的内存来表示。
NFA相对于DFA的劣势在于：需要更长时间才能得出答案。
还有其他的优势或劣势吗？
2个回答
8
我认为你已经很好地掌握了主要的权衡。NFAs可以更节省内存，因为它们可以在O(n)空间中编码O(2n)个不同的配置，而对于相同的语言，DFA可能需要指数级的空间。同样，你正确指出NFAs更新速度较慢；大多数模拟NFAs的算法需要O(n)时间来计算状态转换（其中n是状态数），而DFA只需O(1)时间。
这两者之间还有一些其他的区别。首先，DFAs通常更容易编码，因为每对状态和符号只有一个转换。这自然地适用于多维数组的转换表。相比之下，NFA（或更糟的，ε-NFA）通常需要更复杂的表示，因为任何状态都可能有大量的转换。但是，NFAs具有许多优点，例如许多从复杂结构到自动机的变换用NFAs会更简单。例如，从正则表达式生成匹配自动机的规范构造生成ε-NFA而不是DFA，因为最好通过递归地构建较小的ε-NFA，然后使用ε-moves将它们连接在一起来表示转换。直接将正则表达式转换为DFA是可能的，但是这 considerably more difficult to do so.同样，许多生成LR(k)解析器的算法可以更直观地通过探索如何使用NFAs而不是DFAs来工作的处理识别自动机来激发，尽管大多数生成这些解析器的算法直接转到DFA而不是NFA。
希望这有所帮助！
这两者之间还有一些其他的区别。首先，DFAs通常更容易编码，因为每对状态和符号只有一个转换。这自然地适用于多维数组的转换表。相比之下，NFA（或更糟的，ε-NFA）通常需要更复杂的表示，因为任何状态都可能有大量的转换。但是，NFAs具有许多优点，例如许多从复杂结构到自动机的变换用NFAs会更简单。例如，从正则表达式生成匹配自动机的规范构造生成ε-NFA而不是DFA，因为最好通过递归地构建较小的ε-NFA，然后使用ε-moves将它们连接在一起来表示转换。直接将正则表达式转换为DFA是可能的，但是这 considerably more difficult to do so.同样，许多生成LR(k)解析器的算法可以更直观地通过探索如何使用NFAs而不是DFAs来工作的处理识别自动机来激发，尽管大多数生成这些解析器的算法直接转到DFA而不是NFA。
希望这有所帮助！
- templatetypedef
1
NFA表示更加紧凑，但DFA更容易模拟。通常情况下，当NFA被转化为DFA时，大小会呈指数级增长。
- Foo Bah
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接