我正在寻找一份关于DFA和NFA引擎的非技术性解释，重点在于它们的能力和限制方面。
DFA和NFA引擎：它们的能力和限制有什么区别？
50
- blunders
3
http://en.wikipedia.org/wiki/Deterministic_finite-state_machine - SilentGhost
8@SilentGhost，我知道这篇文章并不涉及太多数学内容，但是它依赖于读者了解所有未被解释的数学符号。就像许多维基百科文章一样，它是由一位非常熟悉该主题的人编写的，他们无法从初学者的角度看待它，不过我们要面对的事实是，大部分读者都是初学者。 - Andrew S
1这绝对是我见过的关于DFAs和NFAs的最好解释。简而言之，DFAs和NFAs具有相同的能力和限制，但使用NFAs的某些实现性能较差。 - Timmmm
5个回答
82
确定有限状态自动机（DFAs）和非确定有限状态自动机（NFAs）具有完全相同的能力和限制。唯一的区别是符号表示上的便利性。
有限自动机是一种处理器，它拥有状态并读取输入，每个输入字符都可能将其置于另一个状态。例如，状态可能是“刚读了两个连续的C”或“正在开始一个单词”。这些通常用于快速扫描文本以查找模式，例如对源代码进行词法分析以将其转换为标记。
确定有限状态自动机一次只处于一个状态，这是可实现的。而非确定有限状态自动机可以同时处于多个状态：例如，在一个语言中，标识符可以以数字开头，可能会有一个状态“正在读取数字”和另一个状态“正在读取标识符”，当读取以“123”开头的内容时，NFA可以同时处于这两个状态。实际应用哪个状态取决于它是否在单词结束之前遇到了非数字字符。
现在，我们可以将“正在读取数字或标识符”表达为一个状态本身，突然间我们不需要NFA了。如果我们将NFA中的状态组合表示为状态本身，则可以得到具有更多状态但执行相同操作的DFA。
这只是一个易于阅读、编写和处理的问题。DFAs本身更容易理解，但NFAs通常较小。
有限自动机是一种处理器，它拥有状态并读取输入，每个输入字符都可能将其置于另一个状态。例如，状态可能是“刚读了两个连续的C”或“正在开始一个单词”。这些通常用于快速扫描文本以查找模式，例如对源代码进行词法分析以将其转换为标记。
确定有限状态自动机一次只处于一个状态，这是可实现的。而非确定有限状态自动机可以同时处于多个状态：例如，在一个语言中，标识符可以以数字开头，可能会有一个状态“正在读取数字”和另一个状态“正在读取标识符”，当读取以“123”开头的内容时，NFA可以同时处于这两个状态。实际应用哪个状态取决于它是否在单词结束之前遇到了非数字字符。
现在，我们可以将“正在读取数字或标识符”表达为一个状态本身，突然间我们不需要NFA了。如果我们将NFA中的状态组合表示为状态本身，则可以得到具有更多状态但执行相同操作的DFA。
这只是一个易于阅读、编写和处理的问题。DFAs本身更容易理解，但NFAs通常较小。
- David Thornley
1
1好的，一篇现已删除的答案将NFA与DFA混淆了。我以前见过人们这样做，显然这是因为一本有用的书，或者至少是这样声称的：http://fanf.livejournal.com/37166.html - Eamon Nerbonne
17
这里是微软给出的非技术性答案：
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】
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】
- james.garriss
4
17MSDN文章有误导性；NFA和DFA同样强大。NFA算法不需要回溯(其最坏情况是指数行为)。需要回溯的原因是因为“正则表达式”比常规语言更强大(例如，反向引用)，因此不能通过规范的NFA/DFA来建模。这里提供一个良好实现的NFA算法示例，它不使用回溯：http://swtch.com/~rsc/regexp/regexp1.html - Rufflewind
关于灾难性回溯的话题：http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016 - Eamon Nerbonne
如果你坚持标准定义，那么这篇微软文章实际上是错误的：一个NFA根本不会回溯。某些回溯自动机如果从NFA开始实现会更容易，也许这篇文章指的就是这样的实现方式。 - toolforger
这里提供非回溯NFA算法的参考实现：https://github.com/iter-tools/regex。最简单的想法是将其看作是模式的演变。消耗输入字符会消除一些不能匹配的模式分支，并改变（可能）其他仍然可以匹配的分支。如果您从模式
b|.a|abc开始，应用输入a将得到模式a|bc。应用输入b将得到模式c。此时，模式将在下一个字符是c时匹配。 - conartist67
这是一个简单的、非技术性的解释，摘自Jeffrey Friedl的书《精通正则表达式》。
注意：
虽然这本书通常被认为是“正则表达式圣经”，但似乎有一些争议，即在DFA和NFA之间所做的区分是否正确。我不是计算机科学家，也不理解真正的“正则”表达式背后的大部分理论，无论是确定性还是不确定性的。在争议开始后，我删除了这个答案，但自那以后它已经被引用到其他答案的评论中。我非常感兴趣进一步讨论这个问题——Friedl真的错了吗？或者我理解Friedl的意思错了吗（但我昨晚重新阅读了那一章，就像我记得的那样...）？
编辑：看来Friedl和我确实错了。请查看Eamon下面的优秀评论。
原始答案：
一个DFA引擎逐个字符地扫描输入字符串，并尝试（并记住）正则表达式在此处可能匹配的所有可能方式。如果它到达字符串的末尾，则声明成功。
想象一下字符串AAB和正则表达式A*AB。现在我们逐个字母地遍历我们的字符串。
A:- 第一分支：可以通过
A*匹配。 - 第二分支：可以通过忽略
A*（允许零次重复）并使用正则表达式中的第二个A进行匹配。
- 第一分支：可以通过
A:- 第一分支：可以通过扩展
A*进行匹配。 - 第二分支：无法通过
B进行匹配。第二分支失败了。但是： - 第三分支：可以通过不扩展
A*并使用第二个A进行匹配。
- 第一分支：可以通过扩展
B:- 第一分支：无法通过扩展
A*或继续在正则表达式中移动到下一个标记A进行匹配。第一分支失败了。 - 第三分支：可以匹配。太好了！
- 第一分支：无法通过扩展
DFA 引擎从不在字符串中回溯。
一个NFA引擎逐个字符地扫描正则表达式，并在字符串上尝试所有可能的排列，必要时进行回溯。如果它到达了正则表达式的末尾，它就会宣布成功。
想象一下与之前相同的字符串和相同的正则表达式。我们现在逐个字符地扫描正则表达式：
A*：匹配AA。记住回溯位置0（字符串的开头）和1。A：不匹配。但是我们有一个可以返回并重试的回溯位置。正则表达式引擎向后移动一个字符。现在A匹配。B：匹配。到达正则表达式的末尾（还剩一个回溯位置）。太好了！
- Tim Pietzcker
10
3这个答案不准确 - 灾难性回溯与NFA / DFA区分是正交的。而您描述的DFA实际上是一个NFA（使用典型的状态叠加） - DFA始终只存在于一个状态中，因此是“确定性的”，而NFA可能存在于多个状态中，因此是非确定性的。 - Eamon Nerbonne
7从某种意义上说，这只是术语。尽管如此，DFA是确定性的（正如名称所示），而NFA是非确定性的（同样如名称所示）。这有一个相当直观的原因：DFA总是处于精确的一个状态，并且当遇到一个字符时，该字符总是对应于唯一的（确定的）下一个状态。所以，你的第一个解释是一个很好的正则表达式算法，但它不是DFA - 明显地，正如你所描述的，可能会有多个选项，直到字符串结束才知道哪个是“最佳”的。 - Eamon Nerbonne
5你的第二个算法标记为NFA引擎，确实是一种可能的NFA实现。它解决了与你的第一个（也是NFA）算法相同的歧义问题，但是不同的是，它只选择一个选项，并根据需要进行回溯。因此，它确实是一个NFA，但它不是唯一可能的NFA，就像你的第一种方法展示的那样：它用不同的方式处理同样的非确定性。我想你可以称这个为回溯NFA引擎，以区分这两种算法。 - Eamon Nerbonne
3最后值得注意的是，任何有限状态自动机（FSA）中，正如其名称所示，状态是有限的——更具体地说，在将任何相关信息嵌入状态之后，该元组仍然需要具有有限数量的选项。这意味着严格来说，与Perl兼容的引擎并不真正是任何类型的FSA，既不是DFA也不是NFA：毕竟，您可以包括任意长度的向后引用，并且存在无限数量的任意长度字符串。 - Eamon Nerbonne
3这个区别对性能非常重要，因为无限状态空间意味着你无法预编译 NFA，也不能使用第一种算法高效地执行它。在一般情况下，回溯算法会在面对正则表达式（在实践中很常见）时失败，导致灾难性的回溯。 - Eamon Nerbonne
显示剩余5条评论
4
NFA和DFA都是有限自动机，正如它们的名称所示。
两者都可以表示为一个起始状态、一个成功（或“接受”）状态（或一组成功状态）和一个列出转换的状态表。
在DFA的状态表中，每个<state₀, input>键将转移到一个且仅一个state₁。
在NFA的状态表中，每个<state₀, input>将转移到一组状态。
当你拿到一个DFA，将其重置为起始状态，给它一系列输入符号，你将准确地知道它处于哪个结束状态以及它是否是一个成功状态。
然而，当你拿到一个NFA时，对于每个输入符号，它将查找可能结果状态的集合，并（理论上）随机地、“非确定性地”选择其中一个。如果存在一系列随机选择导致该输入字符串的某个成功状态，则称该NFA成功。换句话说，你需要假装它总是能够正确地选择。
计算机学科早期的一个问题是，由于其神奇性质，NFAs是否比DFAs更强大，最终的答案是不是，因为任何NFA都可以被转化成等价的DFA。 它们的能力和限制完全相同。
对于那些想知道真实的、非神奇的NFA引擎如何“神奇地”为给定符号选择正确的后继状态的人，this page介绍了两种常见的方法。
- BenGoldberg
1
“then the DFA is said to succeed for that string” 这句话是不是应该改成“NFA”呢？ - Scratte
0
我认为Jan Goyvaerts在《正则表达式，完整教程》一书中给出的解释最实用。请参阅PDF文件的第7页：
https://www.princeton.edu/~mlovett/reference/Regular-Expressions.pdf
在第7页提到的其他要点中，有两种正则表达式引擎：文本导向引擎和正则表达式导向引擎。杰弗里·弗里德尔称它们分别为DFA和NFA引擎。...某些非常有用的功能，例如惰性量词和反向引用，只能在正则表达式导向引擎中实现。
- RBV
1
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接