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