NFA 識别記号的并行方法
之前的文章中寫過的 “用一個輸入字元串在一個 NFA 中逐個嘗試各種路徑、最終找到一條從初态到終态” 的方法被稱為“NFA識别記号的串行方法”，然而這種方法效率着實不高——一條路走不通，要退回去重新走（也就是回溯），進而産生大量的無效計算。
為了解決效率問題，我們可以改變思路，實作記号的并行識别——這種方式可以防止由于反複試探産生的回溯。
具體思路是：從起點開始，用同一個輸入字元同時去嘗試到下一步的所有可行的路徑。這樣立足于目前，把所有可能的下一步全都跳完一次，再把這些結果收集起來，就可以獲得一個”從目前起點開始所有可達的下一點的集合“。
此時我們雖然不知道這個集合中哪一個才是能夠滿足後續需求的（也就是能最終走向終态的），但至少這個集合中該有哪些元素，已經是确定的了。
接下來，再從上一步得到的集合中的所有點同時出發，每一個狀态都按照上面相同的方式去嘗試所有可達的下一狀态，然後将所有收集到的可達狀态再放入一個新的集合——這樣我們就獲得了從第二個狀态出發的可達狀态集合……如此往複，走遍所有的狀态，最後的終态節點就在最後一個可達狀态的集合中。
因為我們在每一步都考慮了下一步所有可能的轉移，是以收集到的狀态集合，就都是“确定”的了。
我們把一個個不确定下一步收集起來變成一個下一步集合，這樣就實作了将不确定的下一狀态确定化
NFA 上識别記号的确定化方法
NFA 的不确定性，是由于：1. 從一個狀态通過同樣的字元可以達到不同的下一狀态；2. 允許出現 ε 狀态轉移。
是以，為了消除這種不确定性就需要以下兩個步驟：
- 消除多于一個的下一狀态轉移： smove(S, a)，S 是狀态集合，a 是字母表裡的一個字元（不能是 ε ）；
- 消除 ε 狀态轉移：使用函數 ε-閉包(T)，狀态集 T 的 ε 閉包
- smove(S, a)：從狀态集 S 中的每個狀态出發，經過标記為 a 的邊，直接到達的下一狀态的全體；
- ε-閉包(T)：從狀态集 T 中的每個狀态出發，經過若幹次 ε 轉移，到達的狀态全體。（經過任意有限次 ε 的都算）
狀态集 T 的 ε-閉包(T)
定義：狀态集 T 的 ε-閉包(T) 是一個狀态集，其滿足：
-
T中所有的狀态屬于 ε-閉包(T)；
（經過若幹次 ε 轉移嘛，當然 0 次也是算的，零次轉移所能達到的當然就是所有的自身狀态）
-
如果 t 屬于 ε-閉包(T) 且 move(t, ε)=u，則 u 屬于 ε-閉包(T)；
（比如 t 是之前的 T 的元素經過 n 次空轉移到的狀态，這裡的 u 就是經過 n+1 次空轉移到的）
- 除此之外沒有其他狀态屬于 ε-閉包(T)
編譯原理筆記5：從正規式到詞法分析器（2）：NFA 記号識别、确定化、并行算法、子集法構造DFA
所有經過 ε 跳轉後抵達的狀态都是結果集中的一個元素。
ε-閉包算法
閉包U：是一個集合，其存儲閉包計算的結果；
棧：棧中的元素，就是目前還沒有考慮的狀态節點（需要我們去考慮從該處沿空邊出發的節點），沒有考慮空邊的狀态都要入棧，需要考慮更多空邊的時候，就從棧裡面往出取節點就行了。
function ε-閉包(T) is
begin
for T中的每個狀态t // T 是要計算閉包的集合
loop
将t加入U;// 先加入所有初狀态，它們也算閉包運算結果元素
push(t);// t是新加入的，當然沒有考慮過它連接配接的空邊，入棧
end loop;
while 棧非空 // 考慮經所有的狀态引出的空邊，能到達哪些狀态
loop // 對每一個狀态，找空邊所能到的所有下一狀态
pop(t); // 棧頂的拿出來，考慮從該狀态出發的空邊轉移情況
for 每個u=move(t, ε) //若存在u，可以從t經過空邊跳到
loop
if u不在U中 then //新跳到的這個 u 并沒有被加入 U
将u加入U;
push(u);//因為是新來的，故也沒考慮過它的空邊
end if;
end loop;
end loop;
return U;
end ε-閉包 例：
圖中的 U 代表我們最終傳回的的結果集合，其元素是在整個算法運作的過程中被逐漸添加的；Stack 是上面僞代碼中提到的“棧”，用來存儲運作時臨時儲存的待考慮狀态（也就是還沒被檢查所有下一狀态的狀态）。
NFA 并行算法
輸入：NFA N, x(EOF)， s0（NFA的初态），F（NFA的終态集）
輸出：若 N 接受 x，列印“yes”，否則"no"
方法：用下面的過程對 x 進行識别，其中 S 是一個狀态的集合
與前面的 模拟DFA 相比，有如下差別：
| 模拟DFA | 模拟NFA | |
|---|---|---|
| 開始 | 初态隻有一個（s0） | 初态是個集合（S） |
| 下一狀态轉移 | 得到下一個單一狀态 | 得到下一狀态集合 |
| 結束 | s is in F，即終态在終态集中 | S∩F ≠ Ø |
但模拟 DFA 與模拟 NFA 也有一個共同點，就是【算法與模式無關】：DFA 和 NFA 都是作為資料（參數）交給算法的，算法的運作與具體的自動機無關。
NFA 并行算法例：識别 abb 和 abab
所用的 NFA 如下圖所示
- 識别 abb：
- 計算初态集： ε-閉包( {0} ) = {0, 1, 2, 4, 7} 記作集合A
- 讀取到輸入字元 a，計算從 A 出發經過 a 到達的狀态集：ε-閉包( smove(A, a) ) = {8, 3, 6, 7, 1, 2, 4} 記作集合B，B 的詳細計算過程如下，寫的比較細，懂的可以直接略過。。
- 對集合 A 中的狀态 0，沒有從 0 開始的 a 轉移，無事發生，不需要填入集合 T；
- 對集合 A 中的狀态 1，沒有從 1 開始的 a 轉移，同樣不需要填入集合 T；
- 對集合 A 中的狀态 2，其經過一次 a 轉移，到達狀态 3，将 3 加入 T，現在 T = {3}；
- 對集合 A 中的狀态 4，沒有從該狀态開始的 a 轉移，不填入 T 集合；
- 對集合 A 中的狀态 7，其經過一次 a 轉移，到達狀态 8，将 8 加入 T，現在 T = {3, 8}；
至此， ε-閉包( smove(A, a) ) 中的 smove(A, a) 計算完成，其結果是 smove(A, a) = T = {3, 8}；
接下來，對 T 進行閉包運算：
- 3 經過一次空轉移，得到 6；
- 3 向右側進行一次空轉移，得到 7；
- 3 向左側進行一次空轉移，得到 1，再從這個 1 出發，進行空轉移，得到 2、4；
- 沒有從 8 開始的空轉移。
- 讀取到輸入字元 b，計算從 B 出發經過 b 到達的狀态集：ε-閉包( smove(B, b) )={9, 5, 6, 7, 1 , 2, 4}，記為集合 C（計算方法與上一步完全相同）；
- 讀取到輸入字元 b，計算從 C 出發經過 b 到達的狀态集：ε-閉包( smove(C, c) )={10, 5, 6, 7, 1, 2, 4}，記為集合 D （計算方法與前兩步完全相同）；
- 結束。計算 D∩{10} = {10}，終态集與結果集交際非空，接受。識别的路徑為 AaBbCbD
是以，我們可以确定， 初态和終态之間存在一條為 abb 的路徑。
但實際上，對abb的識别也可以認為是：
0 ε A aε B bε C bε D，即，通過一個輸入字元進行直接轉移後，再經過若幹次的空轉移，轉移到了下一下一狀态集。路徑上的标記是 ε*aε*bε*bε*，去掉空轉移就是 abb 了，即 ε*aε*bε*bε* = abb。
- 識别 abab
- 初态集： ε-閉包( {0} ) = {0, 1, 2, 4, 7} 記作 A
- 從 A 出發經 a 到達：ε-閉包( smove(A, a) ) = {8, 3, 6, 7, 1, 2, 4} ，記作 B
- 從 B 出發經 b 到達：ε-閉包( smove(B, b) ) = {5, 9, 6, 7, 1, 2, 4} ，記作 C
- 從 C 出發經 a 到達：ε-閉包( smove(C, a) ) = {8, 3, 6, 7, 1, 2, 4} ，等于 B
- 從 B 出發經 b 到達：ε-閉包( smove(B, b) ) = {5, 9, 6, 7, 1, 2, 4} ，等于 C
識别路徑為：A a B b C a B b C，由于 C ∩ {10} = Ø，是以不接受。
觀察上面的兩個識别過程可以發現，當我們使用同一個 NFA 去識别兩個字串時，産生了大量的重複計算（兩個例子的前三步是完全相同的，第二個例子中的 3、5 也進行了完全相同的轉移卻又重新進行了計算）。
既然會出現對于相同輸入的、重複條件下的重複計算，那麼我們就可以在這裡偷懶了——我們可以在正式使用一個 NFA 之前，對這個 NFA 進行預先的分析和計算，把在各種狀态集情況下進行的各種轉移情況計算出來，存儲在一張表中。這樣當我們真正分析輸入序列時，就可以根據目前的狀态和要進行的轉移去查表、得到結果了！
這就是子集法構造 DFA 的思路——子集法構造 DFA，實際上就是對 NFA 并行識别記号方法的提前計算并記錄的過程！
将 NFA 上的全部路徑确定化并記錄下來，就能夠造出與該 NFA 等價的 DFA
下面舉個例子來說明 NFA 到 DFA 的轉化
這個例子假設了一個人要從甲地出發到達乙地，如下圖左側部分所示。中間 1、2、3 是途中經過的地點，轉移的 c 指汽車，b 指自行車，我們要找出從甲到乙的交通方式的組合。
這個問題的模型實際上是個 NFA，就像圖上畫的那樣。對于該 NFA，我們可以通過預計算的方式，建立一個經過狀态轉移到達到達狀态集的 DFA（DFA 中的每個狀态都是一個狀态集——以原來的 NFA 中的某些狀态為元素組成的集合）。該 DFA 與原 NFA 等效，能夠識别 cc、ccb、cbb
識别 cc：甲 _c_ {1, 2} _c_{3, 乙}，接受
識别 cbc：甲 _c_ {1, 2} _b_{3} _c_ ? ，不接受
DFA的優點：
- 消除了不确定性（将 NFA 的下一狀态集合，合并為一個狀态）
- 無需動态計算狀态集合（相對于模拟 NFA 算法）
對于有 k 個狀态的 NFA，與之等價的 DFA 最多有 2k 個狀态（因為 DFA 中的每個狀态都是 NFA 所有狀态的一個子集，是以 DFA 的最大狀态數量就是 NFA 的子集數量）
從 NFA 到 DFA（子集法構造 DFA ）
該算法将從 NFA 的初态開始，生成可達狀态機狀态之間的轉移關系。
輸入： NFA N
輸出： 等價于 N 的 DFA D。初态 ε-閉包( {s0} )（這個東西的運算結果，就是 NFA 的初态集），終态是含有 NFA 終态的狀态集合。
該算法中要用到兩個資料結構：Dstates（狀态，用于存儲生成的 DFA 狀态）、Dtran（用于計算 DFA 狀态之間的狀态轉移）
方法：用下述過程構造 DFA：
我們要将字母表中所有的字元都考慮一遍之後，才能說考慮完一個狀态和與之相關的狀态轉移。然後再去考慮其他沒有被标記的狀态（也就是Dstates中的其他元素），即回到最外層的while，開始新的一輪循環——再去考慮在這個狀态下，經過字母表中所有字元能夠達到的狀态。
最後當 Dstates 中沒有剩餘元素時，DFA就完全生成了。最終得到的 Dstates 和 Dtran 就是我們最終生成的 DFA （即，我們得到了一個确定的狀态轉移表）
例：用上述算法構造(a|b)*abb
根據這些運算的結果，我們就可以構造出來如下圖所示的自動機：
嗯，這樣就完成了我們的 DFA 了。
DFA 可真是個好東西，一旦有了 DFA，我們就可以根據它來簡單地識别輸入序列了！不用再進行那種粗野的蠻力計算了。
但，我們目前的 DFA 就已經是最優了嗎？當然不，還能優化的！
再觀察我們上面畫出來的 DFA，不難發現（老師說不難發現，我還真就沒看出來。。。），從 A 開始經過a、b能夠到達的下一狀态，和從 C 開始經過a、b能夠到達的下一狀态是相同的！（A經過a到達B、A經過b到達C；C經過a到達B、C經過b到達C）
這種情況，我們就說 A、C 是等價的：分别以這兩個為初始狀态，在經過不同的輸入序列轉移後達到的效果完全相同。
這樣，我們就可以把A、C合并，改寫成下面的形式——從A、C出發的都改為從0出發，修改後就能得到新的DFA，減少了一個狀态。這就叫最小化 DFA
具體的最小化，下篇部落格再說，這個已經太長了。。。。。。