blu*_*ers 38 regex finite-automata dfa nfa
我正在寻找基于其功能和限制的DFA与NFA引擎之间差异的非技术性解释.
Dav*_*ley 70
确定性有限自动机(DFAs)和非确定性有限自动机(NFA)具有完全相同的能力和局限性.唯一的区别是符号方便.
有限自动机是具有状态和读取输入的处理器,每个输入字符可能将其设置为另一个状态.例如,状态可能是"只读取连续两个C"或"正在开始一个单词".这些通常用于快速扫描文本以查找模式,例如对源代码进行词汇扫描以将其转换为标记.
确定性有限自动机一次处于一种状态,这是可实现的.非确定性有限自动机一次可以处于多个状态:例如,在标识符可以以数字开头的语言中,可能存在"读取数字"状态而另一个状态"读取标识符",以及在阅读以"123"开头的内容时,NFA可能同时处于同一时间.实际应用的状态取决于它是否在单词结尾之前遇到了不是数字的东西.
现在,我们可以将"读取数字或标识符"表示为一个州本身,突然间我们不需要NFA.如果我们将NFA中的状态组合表示为状态本身,我们就会得到一个DFA,其状态比NFA多得多,但它们也会做同样的事情.
这是一个更容易阅读或写作或处理的问题.DFA本身更容易理解,但NFA通常更小.
jam*_*iss 14
以下是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]
一个简单的,非技术性的解释,从Jeffrey Friedl的着作" 掌握正则表达式"一书中解释.
CAVEAT:
虽然这本书通常被认为是"正则表达",但是在DFA和NFA之间的区别是否真的是正确的,似乎存在一些争议.我不是计算机科学家,我不理解真正是"常规"表达背后的大多数理论,无论是否具有确定性.在争议开始之后,我因此而删除了这个答案,但从那以后它在评论中引用了其他答案.我会非常有兴趣进一步讨论这个问题 - 弗里德尔真的错了吗？或者我得到弗里德错了(但我昨天晚上重读那一章,就像我记得的那样......)？
编辑:看来弗里德尔和我确实是错的.请查看以下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: 火柴.达到了正则表达式的结束(有一个回溯位置).万岁!