DFA&NFA（簡易比較）

1.曆史

正規表達式萌芽于1940年代的神經生理學研究，由著名數學家Stephen Kleene第一個正式描述。具體地說，Kleene歸納了前述的神經生理學研究，在一篇題為《正則集代數》的論文中定義了“正則集”，并在其上定義了一個代數系統，并且引入了一種記号系統來描述正則集，這種記号系統被他稱為“正規表達式”。在理論數學的圈子裡被研究了幾十年之後，1968年，後來發明了UNIX系統的Ken Thompson第一個把正規表達式用于計算機領域，開發了qed和grep兩個實用文本處理工具，取得了巨大成功。在此後十幾年裡，一大批一流計算機科學家和黑客對正規表達式進行了密集的研究和實踐。在1980年代早期，UNIX運動的兩個中心貝爾實驗室和加州大學伯克利分校分别圍繞grep工具對正規表達式引擎進行了研究和實作。與之同時，編譯器“龍書”的作者Alfred Aho開發了Egrep工具，大大擴充和增強了正規表達式的功能。此後，他又與《C程式設計語言》的作者Brian Kernighan等三人一起發明了流行的awk文本編輯語言。到了1986年，正規表達式迎來了一次飛躍。先是C語言頂級黑客Henry Spencer以源代碼形式釋出了一個用C語言寫成的正規表達式程式庫（當時還不叫open source），進而把正規表達式的奧妙帶入尋常百姓家，然後是技術怪傑Larry Wall橫空出世，釋出了Perl語言的第一個版本。自那以後，Perl一直是正規表達式的旗手，可以說，今天正規表達式的标準和地位是由Perl塑造的。Perl 5.x釋出以後，正規表達式進入了穩定成熟期，其強大能力已經征服了幾乎所有主流語言平台，成為每個專業開發者都必須掌握的基本工具。

2.引用

了解DFA和NFA

正規表達式引擎分成兩類，一類稱為DFA（确定性有窮自動機），另一類稱為NFA（非确定性有窮自動機）。兩類引擎要順利工作，都必須有一個正則式和一個文本串，一個捏在手裡，一個吃下去。DFA捏着文本串去比較正則式，看到一個子正則式，就把可能的比對串全标注出來，然後再看正則式的下一個部分，根據新的比對結果更新标注。而NFA是捏着正則式去比文本，吃掉一個字元，就把它跟正則式比較，比對就記下來：“某年某月某日在某處比對上了！”，然後接着往下幹。一旦不比對，就把剛吃的這個字元吐出來，一個個的吐，直到回到上一次比對的地方。

DFA與NFA機制上的不同帶來5個影響：

1. DFA對于文本串裡的每一個字元隻需掃描一次，比較快，但特性較少；NFA要翻來覆去吃字元、吐字元，速度慢，但是特性豐富，是以反而應用廣泛，當今主要的正規表達式引擎，如Perl、Ruby、Python的re子產品、Java和.NET的regex庫，都是NFA的。

2. 隻有NFA才支援lazy和backreference等特性；

3. NFA急于邀功請賞，是以最左子正則式優先比對成功，是以偶爾會錯過最佳比對結果；DFA則是“最長的左子正則式優先比對成功”。

4. NFA預設采用greedy量詞（見item 4）；

5. NFA可能會陷入遞歸調用的陷阱而表現得性能極差。

我這裡舉一個例子來說明第3個影響。

例如用正則式/perl|perlman/來比對文本 ‘perlman book’。如果是NFA，則以正則式為導向，手裡捏着正則式，眼睛看着文本，一個字元一個字元的吃，吃完 ‘perl’ 以後，跟第一個子正則式/perl/已經比對上了，于是記錄在案，往下再看，吃進一個 ‘m’，這下糟了，跟子式/perl/不比對了，于是把m吐出來，向上彙報說成功比對 ‘perl’，不再關心其他，也不嘗試後面那個子正則式/perlman/，自然也就看不到那個更好的答案了。

如果是DFA，它是以文本為導向，手裡捏着文本，眼睛看着正則式，一口一口的吃。吃到/p/，就在手裡的 ‘p’ 上打一個鈎，記上一筆，說這個字元已經比對上了，然後往下吃。當看到 /perl/ 之後，DFA不會停，會嘗試再吃一口。這時候，第一個子正則式已經山窮水盡了，沒得吃了，于是就甩掉它，去吃第二個子正則式的/m/。這一吃好了，因為又比對上了，于是接着往下吃。直到把正則式吃完，心滿意足往上報告說成功比對了 ‘perlman’。

由此可知，要讓NFA正确工作，應該使用 /perlman|perl/ 模式。

通過以上例子，可以了解為什麼NFA是最左子式比對，而DFA是最長左子式比對。實際上，如果仔細分析，關于NFA和DFA的不同之處，都可以找出道理。而明白這些道理，對于有效應用正規表達式是非常有意義的。

正規表達式的形式定義故意非常精簡，避免定義多餘的量詞 ? 和 +，它們可以被表達為: a+ = aa* 和 a? = (a|ε)。有時增加補算子 ~ ；~R 訓示在 Σ* 上的不在 R 中的所有字元串的集合。補算子是多餘的，因為它使用其他算子來表達(盡管計算這種表示的過程是複雜的，而結果可能指數性的增大)。

這種意義上的正規表達式可以表達正則語言，精确的是可被有限狀态自動機接受的語言類。但是在簡潔性上有重要差別。某類正則語言隻能用大小指數增長的自動機來描述，而要求的正規表達式的長度隻線性的增長。正規表達式對應于喬姆斯基層級的類型-3文法。在另一方面，在正規表達式和不導緻這種大小上的爆炸的非确定有限狀态自動機(NFA)之間有簡單的映射；為此 NFA 經常被用作正規表達式的替代表示。

我們還要在這種形式化中研究表達力。如下面例子所展示的，不同的正規表達式可以表達同樣的語言: 這種形式化中存在着備援。

有可能對兩個給定正規表達式寫一個算法來判定它們所描述的語言是否本質上相等，簡約每個表達式到極小确定有限自動機，确定它們是否同構（等價）。

這種備援可以消減到什麼程度? 我們可以找到仍有完全表達力的正規表達式的有趣的子集嗎? Kleene 星号和并集明顯是需要的，但是我們或許可以限制它們的使用。這提出了一個令人驚奇的困難問題。因為正規表達式如此簡單，沒有辦法在文法上把它重寫成某種規範形式。過去公理化的缺乏導緻了星号高度問題。最近 Dexter Kozen 用克萊尼代數公理化了正規表達式。

很多現實世界的“正規表達式”引擎實作了不能用正規表達式代數表達的特征。

目前正則引擎支援的語言種類：

引擎類型	程式
DFA	awk(大多數版本)、egrep（大多數版本）、flex、lex、MySQL、Procmail
傳統型 NFA	GNU Emacs、Java、grep（大多數版本）、less、more、.NET語言、PCRE library、Perl、PHP（所有三套正則庫）、Python、Ruby、set（大多數版本）、vi
POSIX NFA	mawk、Mortice Lern System's utilities、GUN Emacs（明确指定時使用）
DFA/NFA混合	GNU awk、 GNU grep/egrep、 Tcl