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

Question

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

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

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

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

Answer 1

大多数正则表达式引擎使用非确定性自动机，因为它们提供了更大的灵活性。DFAs的限制要大得多。看看一些实现，您将看到这一点。微软甚至在他们的.NET 正则表达式类文档中强调了这一事实：

.NET框架正则表达式引擎是一个回溯正则表达式匹配器，它结合了传统的非确定性有限自动机(NFA)引擎，如Perl、Python和Tcl所使用的引擎。

匹配行为 (第一段)- this文章还提供了使用NFA的理由，而不是更有效的DFA。

Answer 2

如你所知，NFAs和DFAs在计算上是等价的。这是自动机理论中最早的定理之一。有一些算法可以相互转换(不像下推或图灵机器)。

所以。为什么是一个而另一个？因为NFA对给定问题的表示要比等效的DFA容易得多。

编辑:从实际计算机器的角度来看，DFAs将运行得更快，因为他们不需要回溯。但是他们需要更多的记忆来表达。(Mem对CPU的权衡)

Answer 3

我的建议是看一下禤浩焯·瑟斯顿·拉格尔的手册。

有一些简单的、直接生成DFA的方法，但我认为它们只支持有限的操作范围--基本上是EBNF通常的嫌疑人。Ragel使用非确定性方法从简单的自动机合成复杂自动机，然后使用epsilon消去和最小化来创建有效的确定性自动机。无论您需要多少个wierd操作符，向最小确定性自动机的转换总是相同的，并且每个操作符的实现都通过使用非确定性方法保持简单。