为什么使用NFA而不是DFA

Question

我目前正在研究一些计算理论，正如所暗示的那样，这是非常理论的。

我可以很容易地将正则表达式转换为NFA，我可以理解这一点。

但是由于所有的NFA都可以转换为DFA，并且(我非常确定) UNIX中的grep命令使用正则表达式来确定匹配的字符串，那么最常用的有限自动机、DFA还是NFA是什么呢？

根据我的经验(不是很多)，DFA在表示常规语言时通常要简单得多，而且也是确定性的，所以应该总是选择NFA。

NFA分支到多个结果，需要递归函数，对我来说似乎更笨拙。

我知道编译器是有限自动机的另一个实际应用。

我的问题..。为什么两者都要学习/使用呢？DFAs在我看来完全没问题。

谢谢你的回答！

Answer 1

DFA通常更快，可伸缩性更强。确定和最小化NFA有时代价很高。因此，如果自动机只使用一次，则可以跳过它。

NFA(Thompson-NFA、Glushkov-NFA、位并行NFA)的优点是：

• 它们可以更简洁地表达
• 它们可以记录子匹配(例如，对于正则表达式替换)
• 它们可以动态转换为非最小化的DFA

此外，在常见编程语言中使用的正则表达式-NFA(回溯-NFA，例如在Python、Perl、Java、.NET中，而不是grep中)：

• 甚至比上层DFA更慢
• 支持贪婪、非贪婪和占有模式
• 但可以使用DFA可以使用反向引用(并且这些引用不能转换为

)

编译器几乎总是使用最小化的DFA进行词法分析。正则表达式搜索使用DFA或混合DFA/DFA(后者用于子匹配识别)。编程语言中使用的NFA是最强大的(就功能而言)，但也是最慢的。

Answer 2

我认为将回归转换为NFA比DFA更简单。很难直接将回归转换为DFA。