我认为你几乎已经掌握了主要的权衡取舍.NFA可以更高效地记忆,因为它们可以在O(n)空间中编码O(2 n)个不同的配置,而同一语言的DFA可能需要指数空间.你同样正确的是,NFA的更新速度较慢; 大多数用于模拟NFA的算法花费O(n)时间来计算状态转换(其中n是状态数)与DFA的O(1)时间.
两者之间还存在一些其他差异.对于初学者来说,DFA通常更容易编码,因为对于每对状态和符号,只有一个转换.这自然适用于转换表的多维数组.相比之下,NFA(或更糟的是,ε-NFA)通常需要更复杂的表示,因为任何状态都可能存在大量的转换.然而,NFA确实具有以下优点:从复杂结构到自动机的许多转换对于NFA而言更简单.例如,来自正则表达式的匹配自动机的规范构造产生ε-NFA而不是DFA,因为通过递归地构建较小的ε-NFA然后使用ε-移动将它们连接在一起来最好地表达变换.可以直接将正则表达式转换为DFA,但这样做要困难得多.类似地,许多用于生成LR(k)解析器的算法可以通过探索句柄识别自动机如何在NFA方面而不是在DFA方面更直观地推动(尽管用于生成这些解析器的大多数算法直接转到DFA而不是NFA) ).
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
1972 次 |
| 最近记录： |