我目前正在研究一些计算理论，正如所暗示的那样，它是非常理论化的。
我可以很容易地将正则表达式转换为 NFA，再转换为 DFA，我能理解这一点。
但是由于所有 NFA 都可以转换为 DFA，并且(我很确定)UNIX 中的 grep 命令使用正则表达式来确定匹配的字符串，所以最常用的有限自动机是 DFA 还是 NFA？
根据我的经验(不多)，DFA 在表示常规语言时通常更易于使用，而且具有确定性，因此应始终选择 NFA。
NFA 分支到多个结果，需要递归函数，而且对我来说似乎更尴尬。
我知道编译器是有限自动机的另一种实际应用。
我的问题……为什么要学习/使用两者。 DFA 对我来说似乎非常好。
感谢您的回答!
最佳答案
DFA 通常速度更快且可扩展性更强。确定和最小化 NFA 有时代价高昂。所以如果自动机只使用一次就可以跳过。
NFAs(Thompson-NFAs、Glushkov-NFAs、位并行NFAs)的优点是:
- 可以更简洁地表达
- 他们可以记录子匹配(例如正则表达式替换)
- 它们可以即时转换为非最小化 DFA
此外，常见编程语言中使用的 Regex-NFA(Backtracking-NFA，例如在 Python、Perl、Java、.NET 中，不在 grep 中):
- 甚至比上层 NFA 慢
- 支持贪婪、非贪婪和占有模式
- 但可以使用前瞻/后视
- 并且可以使用反向引用(并且这些不能转换为 DFA)
编译器几乎总是使用最小化的 DFA 进行词法分析。正则表达式搜索使用 DFA 或混合 DFA/NFA(后者用于子匹配识别)。编程语言中使用的 NFA 是最强大的(就功能而言)，但也是最慢的。
关于regex - 为什么使用 NFA 而不是 DFA，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33260936/