最近我一直在思考有限状态机 (FSM)，以及如何在软件中实现它们(编程语言无关紧要)。
我的理解是确定性状态机被广泛使用(解析器/词法分析器、编译器等)，但是非确定性状态机有什么问题呢？
我知道可以将所有非确定性状态机转换为确定性状态机(甚至以编程方式)。那不是我的意思。我还认为非确定性状态机的实现要复杂得多。
无论如何，实现非确定性状态机是否任何有意义？有什么我不知道的特殊应用吗？ 这样做的原因是什么？也许优化和专用的非确定性状态机更快？
最佳答案
大多数正则表达式引擎使用非-确定性自动机，因为它们提供了更大的灵 active 。 DFA 受到的限制要多得多。看看一些实现，您就会看到这一点。 Microsoft 甚至在其 .NET 文档中强调了这一事实 Regex类:
The .NET Framework regular expression engine is a backtracking regular expression matcher that incorporates a traditional Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl.
Matching behavior (第一段)——本文还提供了使用 NFA 而不是更高效的 DFA 的基本原理。
关于algorithm - 软件开发中的非确定性有限状态机？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/198581/