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