algorithm - 软件开发中的非确定性有限状态机？

Question

最近我一直在思考有限状态机 (FSM)，以及如何在软件中实现它们(编程语言无关紧要)。

我的理解是确定性状态机被广泛使用(解析器/词法分析器、编译器等)，但是非确定性状态机有什么问题呢？

我知道可以将所有非确定性状态机转换为确定性状态机(甚至以编程方式)。那不是我的意思。我还认为非确定性状态机的实现要复杂得多。

无论如何，实现非确定性状态机是否任何有意义？有什么我不知道的特殊应用吗？这样做的原因是什么？也许优化和专用的非确定性状态机更快？

Answer 1

大多数正则表达式引擎使用非-确定性自动机，因为它们提供了更大的灵 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 的基本原理。