47

我正在寻找关于 DFA 与 NFA 引擎之间差异的非技术解释，基于它们的功能和限制。

4

5 回答 5

79

确定性有限自动机 (DFA) 和非确定性有限自动机 (NFA) 具有完全相同的功能和限制。唯一的区别是符号方便。

有限自动机是具有状态并读取输入的处理器，每个输入字符都可能将其设置为另一种状态。例如，一个状态可能是“连续读两个 C”或“正在开始一个单词”。这些通常用于快速扫描文本以查找模式，例如对源代码进行词法扫描以将其转换为标记。

确定性有限自动机一次处于一种状态，这是可以实现的。非确定性有限自动机一次可以处于多个状态：例如，在标识符可以以数字开头的语言中，可能存在“读取数字”状态和“读取标识符”状态，以及NFA 可能在读取以“123”开头的内容时同时出现在两者中。实际应用哪个状态取决于它是否在单词结尾之前遇到了非数字的东西。

现在，我们可以将“读取数字或标识符”表达为状态本身，突然我们就不需要 NFA。如果我们将 NFA 中的状态组合表示为状态本身，我们得到的 DFA 的状态比 NFA 多得多，但它做同样的事情。

这是一个更容易阅读或写作或处理的问题。DFA 本身更容易理解，但 NFA 通常更小。

于 2010-10-20T15:40:13.147 回答
17

这是来自 Microsoft 的非技术性回答：

DFA 引擎以线性时间运行，因为它们不需要回溯（因此它们不会两次测试相同的字符）。他们还可以保证匹配尽可能长的字符串。但是，由于 DFA 引擎只包含有限状态，它不能匹配带有反向引用的模式，并且因为它不构造显式扩展，它不能捕获子表达式。

传统的 NFA 引擎运行所谓的“贪婪”匹配回溯算法，以特定顺序测试正则表达式的所有可能扩展并接受第一个匹配。因为传统 NFA 为成功匹配构建了正则表达式的特定扩展，所以它可以捕获子表达式匹配和匹配反向引用。然而，由于传统的 NFA 回溯，如果状态是通过不同的路径到达的，它可以多次访问完全相同的状态。因此，在最坏的情况下，它可能会以指数方式缓慢运行。因为传统的 NFA 接受它找到的第一个匹配项，所以它也可以让其他（可能更长的）匹配项未被发现。

POSIX NFA 引擎类似于传统的 NFA 引擎，不同之处在于它们会继续回溯，直到可以保证找到可能的最长匹配。因此，POSIX NFA 引擎比传统 NFA 引擎慢，并且在使用 POSIX NFA 时，您不能通过更改回溯搜索的顺序来偏爱较短的匹配而不是较长的匹配。

传统的 NFA 引擎受到程序员的青睐，因为它们比 DFA 或 POSIX NFA 引擎更具表现力。尽管在最坏的情况下它们可能运行缓慢，但您可以使用减少歧义和限制回溯的模式引导它们在线性或多项式时间内找到匹配项。

[http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx]

于 2011-01-26T20:19:35.310 回答
7

一个简单的、非技术性的解释，转述自 Jeffrey Friedl 的书Mastering Regular Expressions。

警告：

虽然这本书通常被认为是“正则表达式圣经”，但对于这里对 DFA 和 NFA 的区分是否真的正确，似乎存在一些争议。我不是计算机科学家，我不理解“常规”表达式背后的大部分理论，无论是否具有确定性。争议开始后，我因此删除了这个答案，但从那时起，它在其他答案的评论中被引用。我很想进一步讨论这个问题——弗里德尔真的错了吗？还是我弄错了弗里德尔（但我昨天晚上重读了那一章，就像我记得的一样……）？

编辑：看来弗里德尔和我确实错了。请在下面查看 Eamon 的精彩评论。

原答案：

DFA 引擎逐个字符地遍历输入字符串，并尝试（并记住）此时正则表达式可以匹配的所有可能方式。如果它到达字符串的末尾，则声明成功。

想象一下字符串AAB和正则表达式A*AB。我们现在一个字母一个字母地遍历我们的字符串。

  1. A：

    • 第一个分支：可以匹配A*。
    • 第二个分支：可以通过忽略A*（允许零重复）并A在正则表达式中使用第二个来匹配。

  2. A：

    • 第一个分支：可以通过扩展来匹配A*。
    • 第二个分支：不能被B. 第二个分支失败。但：
    • 第三个分支：可以通过不扩展A*而使用第二个A来匹配。

  3. B：

    • 第一个分支：无法通过扩展A*或在正则表达式中移动到下一个标记来匹配A。第一个分支失败。
    • 第三支：可以匹配。万岁！

DFA 引擎永远不会在字符串中回溯。

NFA 引擎逐个标记地遍历正则表达式标记，并尝试字符串上所有可能的排列，必要时回溯。如果它到达正则表达式的末尾，则声明成功。

想象一下与以前相同的字符串和相同的正则表达式。我们现在逐个令牌地遍历我们的正则表达式令牌：

  1. A*: 匹配AA。记住回溯位置 0（字符串的开头）和 1。
  2. A: 不匹配。但是我们有一个回溯位置，我们可以返回并重试。正则表达式引擎后退一个字符。现在A匹配。
  3. B： 火柴。正则表达式结束（有一个回溯位置备用）。万岁！
于 2010-10-20T15:05:09.747 回答
4
于 2016-10-22T23:44:32.783 回答
0

我发现Jan Goyvaerts的 The Complete Tutorial 正则表达式中给出的解释是最有用的。请参阅此 PDF 第 7 页：

https://www.princeton.edu/~mlovett/reference/Regular-Expressions.pdf

在第 7 页提出的其他要点中，有两种正则表达式引擎：文本导向引擎和正则表达式导向引擎。Jeffrey Friedl 分别称它们为 DFA 和 NFA 引擎。 ...某些非常有用的功能，例如惰性量词和反向引用，只能在正则表达式导向的引擎中实现。

于 2016-04-26T20:43:24.040 回答