要深入了解正則表達式，必須首先理解有窮自動(dòng)機。
有窮自動(dòng)機（Finite Automate）是用來(lái)模擬實(shí)物系統的數學(xué)模型，它包括如下五個(gè)部分：
- 有窮狀態(tài)集States
- 輸入字符集Input symbols
- 轉移函數Transitions
- 起始狀態(tài)Start state
- 接受狀態(tài)Accepting state(s)
下圖為一臺有窮自動(dòng)機
可以看到，該自動(dòng)機包含四個(gè)狀態(tài)q0, q1, q2, q3，兩個(gè)輸入字符a, b，轉移函數如圖所示，起始狀態(tài)為q0，接受狀態(tài)為q3。
有窮自動(dòng)機，按照轉移函數的不同，又可分為確定型有窮自動(dòng)機（Determinism Finite Automate, DFA），與非確定型有窮自動(dòng)機（Non-determinism Finite Automate, NFA）。
非確定有窮自動(dòng)機容許轉移函數不確定，換句話(huà)說(shuō)，對任意狀態(tài)，輸入任意一個(gè)字符，可以轉移到0個(gè)，1個(gè)或者多個(gè)狀態(tài)。
下圖是一臺非確定有窮自動(dòng)機，可以看到，對狀態(tài)q0輸入字符a，既可以轉移到q0，也可以轉移到q1，這就是“非確定”的意義所在。
對某個(gè)自動(dòng)機來(lái)說(shuō)，如果從起始狀態(tài)，接受一系列輸入字符，可以轉移到接受狀態(tài)，即認為這一系列字符可以被自動(dòng)機接受。
如果兩臺自動(dòng)機能夠接受的輸入字符串（或者叫做“正則語(yǔ)言”Regular Language）完全相同，則這兩臺自動(dòng)機是等價(jià)的。
可以證明，對于每一個(gè)非確定有窮自動(dòng)機，都存在與之等價(jià)的確定型有窮自動(dòng)機（證明略）。
正則表達式就是建立在自動(dòng)機的理論基礎上的：用戶(hù)寫(xiě)完正則表達式之后，正則引擎會(huì )按照這個(gè)表達式構建相應的自動(dòng)機（可能是NFA，也可能是DFA，但它們必定是等價(jià)的），若輸入一串文本之后，自動(dòng)機抵達了接受狀態(tài)，則這串文本可以“匹配”用戶(hù)指定的正則表達式。
下面是同一個(gè)正則表達式 a|ab 對應的NFA和DFA
NFA
DFA
在
Mastering Regular Expression中，Friedl首先分析了NFA和DFA的區別，DFA比較快，但不提供Backtrack（回溯）功能，NFA比較慢，但提供了Backtrack功能。
在分析兩種引擎的匹配過(guò)程時(shí)，Friedl指出，NFA是基于表達式的（Regex-Directed），而DFA是基于文本的（Text-Directed）。
舉例來(lái)說(shuō)，對于正則表達式 to(nite|knight|night)，NFA在匹配最開(kāi)始兩個(gè)字符（to）之后，剩下的三個(gè)組件（component）是 nite, knight 和 night，于是正則引擎會(huì )依次嘗試這三個(gè)選擇分支（每次嘗試一個(gè)）；而DFA在匹配最開(kāi)始兩個(gè)字符之后，會(huì )將剩下的三個(gè)選擇拆分作字符，并行嘗試，也就是說(shuō)，匹配 to 之后，先匹配 k 或者 n ，如果 k 不能匹配，則放棄 knigth 所在的分支，再匹配 i ，再匹配 t 或 g ……這樣繼續下去，直到匹配結束。
不幸的是，Friedl對匹配過(guò)程的分析，是完全錯誤的——引擎的不同，是指構建的自動(dòng)機的不同，而不是匹配算法的不同！
DFA引擎在任意時(shí)刻必定處于某個(gè)確定的狀態(tài)，而NFA引擎可能處于一組狀態(tài)之中的任何一個(gè)，所以，NFA引擎必須記錄所有的可能路徑（trace multiple possible routes through the NFA），NFA之所以能夠提供Backtrack的功能，原因就在這里。
傳統的NFA匹配算法是帶回溯的深度優(yōu)先搜索（backtracking depth-first search，就是上文所說(shuō)的Regex-Based過(guò)程），而新的PCRE算法提供了效率更高的廣度優(yōu)先搜索，可以同時(shí)保持所有可能的NFA狀態(tài)（請參考
http://www.cl.cam.ac.uk/Teaching/current/RLFA/，尤其是Lecture Notes的section 2.2）。
Friedl的錯誤就在這里，他混淆了應用PCRE算法的NFA與DFA的匹配過(guò)程。
需要指出的是，即使應用PCRE算法，NFA的速度仍然低于DFA，這是由NFA需要同時(shí)保存多種可能的性質(zhì)決定的。從理論上說(shuō)，如果我們不需要應用 Backtrack，完全可以從NFA構造出等價(jià)的DFA，再進(jìn)行匹配，這樣能大大提高速度——代價(jià)是，DFA需要更多的空間。
