最近我一直在考虑有限状态机(FSM)，以及如何在软件中实现它们（编程语言无关紧要）。
我的理解是确定性状态机被广泛使用（解析器/词法分析器、编译器等），但非确定性状态机有什么问题？
我知道可以将所有非确定性状态机转换为确定性状态机（甚至以编程方式）。那不是我的意思。我还认为非确定性状态机的实现要复杂得多。
无论如何，实现非确定性状态机是否有意义？有什么我不知道的特殊应用吗？这样做的原因是什么？也许优化和专门的非确定性状态机更快？
Christoph Schiessl
问问题
4425 次
8 回答
8
大多数正则表达式引擎使用非确定性自动机，因为它们提供了更大的灵活性。DFA 受到更多限制。看看一些实现，你会看到这一点。微软甚至在他们的 .NET Regex类文档中强调了这一事实：
.NET Framework 正则表达式引擎是一个回溯正则表达式匹配器，它结合了传统的非确定性有限自动机 (NFA) 引擎，例如 Perl、Python、Emacs 和 Tcl 使用的引擎。
匹配行为（第一段）——本文还提供了使用 NFA 而不是更有效的 DFA 的理由。
于 2008-10-13T18:44:18.430 回答
6
如您所知，NFA 和 DFA 在计算上是等价的。这是自动机理论中最早的定理之一。有一些算法可以将一个转换为另一个（与下推或图灵机不同）。
所以。为什么一个比另一个？因为用 NFA 表示给定问题比等效的 DFA 容易得多。
编辑：就实际计算机器而言，DFA 会走得更快，因为它们不必回溯。但是它们会占用更多的内存来表示。（内存与 CPU 的权衡）
于 2008-10-13T18:52:25.263 回答
1
我的建议 = 看看Adrian Thurstons Ragel的手册。
有一些直接生成 DFA 的简单方法，但我相信它们只支持有限范围的运算符——基本上是 EBNF 通常的嫌疑人。Ragel 使用非确定性方法从更简单的自动机组成复杂的自动机，然后使用 epsilon 消除和最小化来创建有效的确定性自动机。无论您需要多少奇怪的运算符，到最小确定性自动机的转换总是相同的，并且每个运算符的实现都通过使用非确定性方法保持简单。
于 2009-09-28T12:37:06.573 回答
0
Cayuga在底层利用非确定性有限状态机进行复杂事件处理。好吧，看起来他们称之为“用于事件监控的有状态发布/订阅”，但我相信它是 CEP。
我相信他们的一些论文甚至讨论了他们为什么使用自动机模型。您可能想浏览他们的网站。
...卡尤加自动机，从标准的非确定性有限自动机扩展而来。
于 2008-10-13T18:45:40.333 回答
0
很多时候，创建 NFA 然后使用它要容易得多（唯一的区别是您拥有一组状态而不是一个状态）。如果你想快速获得它，你可以做 DFA，但不要忘记，做它的时间是指数级的（因为生成的自动机可以指数级地变大！）。
另一方面，如果你想做一个补语，你别无选择，你需要一个 det。变体。
这就是为什么否定不在正则表达式引擎中，仅在类（[^...]）中的原因，您可以确定自动机是确定性的。
于 2008-12-16T13:50:31.510 回答
0
如果我错了，请纠正我，但从我的编译器类中，我记得有时你根本不能使用 DFA，因为它会导致状态“爆炸”。
于 2009-06-26T16:03:14.933 回答
0
我认为选择非确定性有限自动机的主要原因是实际获得选择的匹配。使用确定性版本可能更难做到这一点。
如果您只想知道它们是否匹配，并且没有其他细节，我认为编译成有限自动机会更好。
于 2009-06-26T16:23:55.033 回答