NFA 跟 DFA浅析

NFA 和 DFA浅析

要深入了解正则表达式，必须首先理解有穷自动机。

有穷自动机（Finite Automate）是用来模拟实物系统的数学模型，它包括如下五个部分：

• 有穷状态集States
• 输入字符集Input symbols
• 转移函数Transitions
• 起始状态Start state
• 接受状态Accepting state(s)
  下图为一台有穷自动机
  
  
  可以看到，该自动机包含四个状态q0, q1, q2, q3，两个输入字符a, b，转移函数如图所示，起始状态为q0，接受状态为q3。
  
  有穷自动机，按照转移函数的不同，又可分为确定型有穷自动机（Determinism Finite Automate, DFA），与非确定型有穷自动机（Non-determinism Finite Automate, NFA）。
  非确定有穷自动机容许转移函数不确定，换句话说，对任意状态，输入任意一个字符，可以转移到0个，1个或者多个状态。
  下图是一台非确定有穷自动机，可以看到，对状态q0输入字符a，既可以转移到q0，也可以转移到q1，这就是“非确定”的意义所在。
  
  
  
  对某个自动机来说，如果从起始状态，接受一系列输入字符，可以转移到接受状态，即认为这一系列字符可以被自动机接受。
  
  如果两台自动机能够接受的输入字符串（或者叫做“正则语言”Regular Language）完全相同，则这两台自动机是等价的。
  可以证明，对于每一个非确定有穷自动机，都存在与之等价的确定型有穷自动机（证明略）。
  
  正则表达式就是建立在自动机的理论基础上的：用户写完正则表达式之后，正则引擎会按照这个表达式构建相应的自动机（可能是NFA，也可能是DFA，但它们必定是等价的），若输入一串文本之后，自动机抵达了接受状态，则这串文本可以“匹配”用户指定的正则表达式。
  
  下面是同一个正则表达式 a|ab 对应的NFA和DFA
  NFA
  
  
  DFA
  

  
  
  
  
  在Mastering Regular Expression中，Friedl首先分析了NFA和DFA的区别，DFA比较快，但不提供Backtrack（回溯）功能，NFA比较慢，但提供了Backtrack功能。
  在分析两种引擎的匹配过程时，Friedl指出，NFA是基于表达式的（Regex-Directed），而DFA是基于文本的（Text-Directed）。
  举例来说，对于正则表达式 to(nite|knight|night)，NFA在匹配最开始两个字符（to）之后，剩下的三个组件（component）是 nite, knight 和 night，于是正则引擎会依次尝试这三个选择分支（每次尝试一个）；而DFA在匹配最开始两个字符之后，会将剩下的三个选择拆分作字符，并行尝试，也就是说，匹配 to 之后，先匹配 k 或者 n ，如果 k 不能匹配，则放弃 knigth 所在的分支，再匹配 i ，再匹配 t 或 g ……这样继续下去，直到匹配结束。
  
  不幸的是，Friedl对匹配过程的分析，是完全错误的——引擎的不同，是指构建的自动机的不同，而不是匹配算法的不同！
  DFA引擎在任意时刻必定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，所以，NFA引擎必须记录所有的可能路径（trace multiple possible routes through the NFA），NFA之所以能够提供Backtrack的功能，原因就在这里。
  传统的NFA匹配算法是带回溯的深度优先搜索（backtracking depth-first search，就是上文所说的Regex-Based过程），而新的PCRE算法提供了效率更高的广度优先搜索，可以同时保持所有可能的NFA状态（请参考http://www.cl.cam.ac.uk/Teaching/current/RLFA/，尤其是Lecture Notes的section 2.2）。
  
  Friedl的错误就在这里，他混淆了应用PCRE算法的NFA与DFA的匹配过程。
  需 要指出的是，即使应用PCRE算法，NFA的速度仍然低于DFA，这是由NFA需要同时保存多种可能的性质决定的。从理论上说，如果我们不需要应用 Backtrack，完全可以从NFA构造出等价的DFA，再进行匹配，这样能大大提高速度——代价是，DFA需要更多的空间。

  原文地址：http://www.cnblogs.com/u2usoft/archive/2006/06/06/419003.html