为什么使用 NFA 而不是 DFA

Question

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

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

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

根据我的经验（不多），在表示常规语言时，DFA 通常更容易使用，并且也是确定性的，因此应始终选择 NFA。

NFA 会分支到多个结果，需要递归函数，而且对我来说似乎更尴尬。

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

我的问题...为什么要学习/使用两者。DFA 对我来说似乎非常好。

感谢您的任何答复！

Answer 1

DFA 通常速度更快且可扩展性更强。确定和最小化 NFA 有时成本高昂。因此，如果自动机仅使用一次，则可以跳过它。

NFA（Thompson-NFA、Glushkov-NFA、位并行 NFA）的优点是：

• 它们可以更简洁地表达
• 他们可以记录子匹配（例如用于正则表达式替换）
• 它们可以即时转换为非最小化的 DFA

此外，常见编程语言中使用的Regex-NFA（回溯-NFA，例如Python、Perl、Java、.NET，而不是grep）：

• 甚至比上层 NFA 还要慢
• 支持贪婪、非贪婪和占有模式
• 但可以使用前瞻/后瞻
• 并且可以使用反向引用（并且这些不能转换为 DFA）

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