960
技海無涯：正則表達式相關的知識和技術(4)——自動機（完結篇）
自動機
自動機，顧名思義，就是能夠自動完成事情的“機器”。但是為什麼要用自動機，什麼又叫“自動”呢？
我們看看普通的處理方式，簡單的就是if了，例如：判斷某字符串是否是“Hello,Word”,我們都會這麼寫：
if（str == “Hello,Word”）
普通的比較可以滿足大部分的場景，但對於正則表達式這種比較的話，普通的if就完全不能滿足了，例如a*b|c，可以是如下字符串：
ab
aab
aaaab
c
………….
這種情況我們不可能采用普通的if來判斷了，因為不可能窮舉所有的字符串。所以我們要另辟蹊徑，自動機就應運而生了。
我們這裏講的自動機有兩個：一個是確定有限自動機，又叫DFA；一個叫不確定有限自動機，又叫NFA。由於自動機的核心就是通過“狀態”和“狀態變遷”實現的，所以自動機又叫狀態機。
1) NFA
為什麼叫不確定自動機呢？就是因為存在“不確定性”了。
什麼不確定呢？就是一個輸入可能對應多個狀態轉換，所以就不確定了。
通過NFA來識別字符串的過程很簡單，即每輸入一個字符，都判斷當前的狀態集中哪些狀態上有此字符的轉換，然後把所有轉換後的狀態又記錄下來，依此循環，直到字符輸入結束或者狀態機結束。
不知道大家有沒有發現，NFA的識別過程其實非常類似將NFA轉換到DFA的子集構造算法的過程。如下圖：
NFA識別過程，假如識別aabb
（1）初始狀態：0，1，2，4，7
（2）輸入a，轉換到如右的狀態：3, 6, 7, 1 , 2 ,4,
（3）輸入a，轉換到如右的狀態：8, 3, 6 , 7, 1, 2, 4
（4）輸入b，轉換到如右的狀態：9, 5, 6, 7, 1, 2, 4
（5）輸入b，轉換到如右的狀態：10, 5, 6, 7, 1, 2, 4
由於此時已經沒有輸入字符了，而且最終狀態10也包含進來了，因此aabb就接受了。
NFA->DFA的子集構造算法：
（1）初始狀態：0，1，2，4，7（第一個子集）
（2）輸入a，轉換到如右的狀態：3, 6, 7, 1 , 2 ,4（第二個子集）
（3）輸入a，轉換到如右的狀態：8, 3, 6 , 7, 1, 2, 4（第三個子集）
………………………..(依次類推)…………………………………………..
2) DFA.
介紹到這裏，相信大家都已經明白DFA的概念了。
所謂確定，就是指一個輸入隻能對應一個轉換。
而DFA來識別字符串就更簡單了，由於轉換是確定的，所以直接將輸入字符輸入進行轉換即可。
3) NFA和DFA比較.
複雜度：當然是DFA高了；
速度：當然是DFA快了
到這裏正則表達式係列相關知識也就結束了，當然我在這裏知識提綱挈領，讓大家能夠從整體上把握這些相關的東東，不至於上來就被一堆術語和名詞弄暈了，同時也把關鍵的地方點了一下，希望能夠起到讓大家茅塞頓開的效果。
當然更加詳細和深入的研究還需要各位自己深入鑽研了，推薦《編譯原理（龍書）》和《精通正則表達式》兩本書。
最後更新：2017-04-02 03:13:28