为什么在DFA上使用NFA

Question

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

我可以很容易地从正则表达式转换为NFA到DFA，我可以理解。

但是由于所有的NFA都可以转换为DFA（我敢肯定）在UNIX中的grep命令使用正则表达式来确定匹配的字符串，最常用的有限自动机，DFA或NFA是什么？根据我的经验（不是很多），DFA在表示常规语言时通常要简单得多，而且也是确定性的，因此应该总是选择超过NFA。

NFA分支到多个结果，需要递归功能，只是看起来更尴尬。

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

我的问题...为什么学习/使用两个。对我而言，DFA似乎完全没问题。

感谢您的任何答案！

Answer 1

DFA通常更快，更具可扩展性。确定和最小化NFA有时代价很高。所以如果只使用一次自动机，它可以被跳过。

的NFA（汤普森的NFA，Glushkov-的NFA，位并行的NFA）的优点是：

• 它们可以更简洁地表示
• 它们可以记录子匹配（例如，用于正则表达式替换）
• 他们可以在飞行翻译成一个非最小化DFA

此外，在共同的编程语言中使用正则表达式-的NFA（回溯-NFA，如在Python，Perl和Java中，.NET，而不是grep的） ：

• 比上部的NFA更慢
• 支持贪心，nongreedy和possesive模式
• 但可以使用向前看符号/ lookbehinds
• 并且可以使用反向引用（和这些不能被转换为DFA）

编译器几乎总是使用最小化的DFA来进行lexing。正则表达式搜索使用DFA或混合DFA/NFA（后者用于子匹配识别）。在编程语言中使用的NFA类型是最强大的（关于特性），但也是最慢的。

Answer 2

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