最近，我一直在考虑有限状态机(FSM)，以及如何在软件中实现它们(编程语言无关紧要)。
我的理解是确定性状态机得到了广泛使用(解析器/词法分析器，编译器等)，但是非确定性状态机怎么了？
我知道可以将所有非确定性状态机转换为确定性状态机(甚至可以通过编程)。那不是我的意思。我还认为非确定性状态机的实现要复杂得多。
无论如何，实现非确定性状态机对有意义吗？有我不知道的特殊应用程序吗？
这样做的原因可能是什么？也许优化的专用非确定性状态机更快？
最佳答案
大多数正则表达式引擎使用不确定性自动机，因为它们提供了更大的灵活性。 DFA受到更多限制。看看一些实现，您会看到的。 Microsoft甚至在.NET Regex类的文档中强调了这一事实:
Matching behavior(第一段)-本文还提供了使用NFA而非更有效的DFA的基本原理。