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

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

NET Framework正则表达式引擎是一个回溯正则表达式匹配器,它集成了传统的非确定性有限自动机(NFA)引擎,如Perl、Python、Emacs和Tcl使用的引擎。

Matching behavior

如您所知,NFA和DFA在计算上是等价的。这是自动机理论中最早的定理之一。有一些算法可以将一个转换为另一个(不同于下推或图灵机)。

编辑:

Adrian Thurstons Ragel

直接生成DFA的方法很简单,但我相信它们只支持有限范围的操作符——基本上是EBNF。Ragel使用非确定性方法从简单的自动机组成复杂的自动机,然后使用ε消去和最小化来创建高效的确定性自动机。无论需要多少wierd操作符,到最小确定性自动机的转换总是相同的,并且每个操作符的实现都通过使用非确定性方法保持简单。

Cayuga 在引擎罩下利用非确定性有限状态机进行复杂事件处理。看起来他们称之为“有状态发布/订阅事件监视”,但我相信这是CEP。

我相信他们的一些论文甚至讨论了他们为什么使用自动机模型。你可能想看看他们的网站。

viterbi algorithm 手术 Hidden Markov Models 就像NFA一样对待他们。不完全相同,但肯定相似。

它们在语音和文本识别等应用中很有用。

通常,创建NFA并使用它要容易得多(唯一的区别是您持有的是一组状态,而不是一个状态)。如果您想快速实现,可以制作DFA,但不要忘记,这样做的时间是指数级的(因为生成的自动机可以指数级地大!)。

另一方面,如果你想做一个补语,你别无选择,你需要一个变体。

我认为选择一个非确定性有限自动机的主要原因将是实际获得所选择的匹配。使用确定性版本可能要困难得多。

如果您只想知道它们是否匹配,而不想知道其他细节,那么我认为编译成有限自动机会更好。