NFA与DFA相比的优缺点？

NFA优于DFA：表示使用较少的内存。NFA与DFA相比的优缺点？

与NFA相比NFA的缺点：较慢地达到答案。

有没有其他的优点或缺点？

2011-02-04 crowso

内存和速度之间的折衷？这是闻所未闻的！ – 2011-02-04 03:10:51

我认为你已经完全掌握了主要的权衡。 NFA可以具有更高的内存效率，因为它们可以在O（n）空间中编码O（2 ⁿ）不同的配置，而同一语言的DFA可能需要指数空间。你同样正确，NFA有更慢的更新;大多数用于模拟NFA的算法花费O（n）时间来计算DFA的状态转换（其中n是状态数）与O（1）时间。

这两者之间还有一些其他差异。对于初学者来说，DFA通常更易于编码，因为对于每一对状态和符号，都只有一个转换。这自然适用于转换表的多维数组。相比之下，NFA（或更糟糕的，ε-NFA）通常需要更复杂的表示，因为任何状态都可能有大量的转换。然而，NFA确实具有这样的优点，即使用NFA从复杂结构到自动机的许多转换更简单。例如，从正则表达式中匹配自动机的规范构造会生成一个ε-NFA而不是DFA，因为转换最好是通过递归地构建更小的＆ε-NFA，然后使用＆epsilon;将它们连接在一起来表示。可以直接将正则表达式转换为DFA，但这样做要困难得多。类似地，通过探索句柄识别自动机如何在NFA方面而非在DFA方面工作，许多用于生成LR（k）解析器的算法可以被更直观地激励（尽管用于生成这些解析器的大多数算法直接去往DFA而不是NFA ）。

希望这会有所帮助！

来源

2011-02-04 03:28:36 templatetypedef

NFA表示更紧凑，但DFA更易于模拟。当NFA减少到DFA时，通常情况下指数大小会增加

来源

2011-02-04 03:29:33

NFA与DFA相比的优缺点？

回答

相关问题