NFA 識別記號的并行方法

之前的文章中寫過的 “用一個輸入字符串在一個 NFA 中逐個嘗試各種路徑、最終找到一條從初態(tài)到終態(tài)” 的方法被稱為“NFA識別記號的串行方法”规哲，然而這種方法效率著實(shí)不高——一條路走不通跟啤，要退回去重新走（也就是回溯），從而產(chǎn)生大量的無效計(jì)算唉锌。

為了解決效率問題隅肥，我們可以改變思路，實(shí)現(xiàn)記號的并行識別——這種方式可以防止由于反復(fù)試探產(chǎn)生的回溯袄简。

具體思路是：從起點(diǎn)開始武福，用同一個輸入字符同時去嘗試到下一步的所有可行的路徑。這樣立足于當(dāng)前痘番，把所有可能的下一步全都跳完一次，再把這些結(jié)果收集起來平痰，就可以獲得一個“從當(dāng)前起點(diǎn)開始所有可達(dá)的下一點(diǎn)的集合”汞舱。
此時我們雖然不知道這個集合中哪一個才是能夠滿足后續(xù)需求的（也就是能最終走向終態(tài)的），但至少這個集合中該有哪些元素宗雇，已經(jīng)是確定的了昂芜。
接下來，再從上一步得到的集合中的所有點(diǎn)同時出發(fā)赔蒲，每一個狀態(tài)都按照上面相同的方式去嘗試所有可達(dá)的下一狀態(tài)泌神，然后將所有收集到的可達(dá)狀態(tài)再放入一個新的集合——這樣我們就獲得了從第二個狀態(tài)出發(fā)的可達(dá)狀態(tài)集合……如此往復(fù)良漱，走遍所有的狀態(tài)，最后的終態(tài)節(jié)點(diǎn)就在最后一個可達(dá)狀態(tài)的集合中欢际。

因?yàn)槲覀冊诿恳徊蕉伎紤]了下一步所有可能的轉(zhuǎn)移母市，因此收集到的狀態(tài)集合，就都是“確定”的了损趋。 我們把一個個不確定下一步收集起來變成一個下一步集合患久，這樣就實(shí)現(xiàn)了將不確定的下一狀態(tài)確定化

NFA 上識別記號的確定化方法

NFA 的不確定性，是由于：1. 從一個狀態(tài)通過同樣的字符可以達(dá)到不同的下一狀態(tài)浑槽；2. 允許出現(xiàn) ε 狀態(tài)轉(zhuǎn)移蒋失。

因此，為了消除這種不確定性就需要以下兩個步驟：

1. 消除多于一個的下一狀態(tài)轉(zhuǎn)移： smove(S, a)桐玻，S 是狀態(tài)集合篙挽，a 是字母表里的一個字符（不能是 ε ）；
2. 消除 ε 狀態(tài)轉(zhuǎn)移：使用函數(shù) ε-閉包(T)镊靴，狀態(tài)集 T 的 ε 閉包

• smove(S, a)：從狀態(tài)集 S 中的每個狀態(tài)出發(fā)铣卡，經(jīng)過標(biāo)記為 a 的邊，直接到達(dá)的下一狀態(tài)的全體邑闲；
• ε-閉包(T)：從狀態(tài)集 T 中的每個狀態(tài)出發(fā)算行，經(jīng)過若干次 ε 轉(zhuǎn)移，到達(dá)的狀態(tài)全體苫耸。（經(jīng)過任意有限次 ε 的都算）

狀態(tài)集 T 的 ε-閉包(T)

定義：狀態(tài)集 T 的 ε-閉包(T) 是一個狀態(tài)集州邢，其滿足：

1. T中所有的狀態(tài)屬于 ε-閉包(T)； （經(jīng)過若干次 ε 轉(zhuǎn)移嘛褪子，當(dāng)然 0 次也是算的量淌，零次轉(zhuǎn)移所能達(dá)到的當(dāng)然就是所有的自身狀態(tài)）
2. 如果 t 屬于 ε-閉包(T) 且 move(t, ε)=u，則 u 屬于 ε-閉包(T)嫌褪； （比如 t 是之前的 T 的元素經(jīng)過 n 次空轉(zhuǎn)移到的狀態(tài)呀枢，這里的 u 就是經(jīng)過 n+1 次空轉(zhuǎn)移到的）
3. 除此之外沒有其他狀態(tài)屬于 ε-閉包(T)

所有經(jīng)過 ε 跳轉(zhuǎn)后抵達(dá)的狀態(tài)都是結(jié)果集中的一個元素。

ε-閉包算法

閉包U：是一個集合笼痛，其存儲閉包計(jì)算的結(jié)果裙秋；

棧：棧中的元素，就是當(dāng)前還沒有考慮的狀態(tài)節(jié)點(diǎn)（需要我們?nèi)タ紤]從該處沿空邊出發(fā)的節(jié)點(diǎn)）缨伊，沒有考慮空邊的狀態(tài)都要入棧摘刑，需要考慮更多空邊的時候，就從棧里面往出取節(jié)點(diǎn)就行了刻坊。

function ε-閉包(T) is
begin
    for T中的每個狀態(tài)t    // T 是要計(jì)算閉包的集合
    loop 
        將t加入U;// 先加入所有初狀態(tài)枷恕，它們也算閉包運(yùn)算結(jié)果元素
        push(t);// t是新加入的，當(dāng)然沒有考慮過它連接的空邊谭胚，入棧
    end loop;

    while 棧非空 // 考慮經(jīng)所有的狀態(tài)引出的空邊徐块，能到達(dá)哪些狀態(tài)
    loop        // 對每一個狀態(tài)未玻，找空邊所能到的所有下一狀態(tài)
        pop(t); // 棧頂?shù)哪贸鰜恚紤]從該狀態(tài)出發(fā)的空邊轉(zhuǎn)移情況
        for 每個u=move(t, ε)  //若存在u胡控，可以從t經(jīng)過空邊跳到
        loop
            if u不在U中 then //新跳到的這個 u 并沒有被加入 U
                將u加入U;
                push(u);//因?yàn)槭切聛淼陌饨耍室矝]考慮過它的空邊
            end if;
        end loop;
    end loop;

    return U;
end ε-閉包
復(fù)制代碼

例：

圖中的 U 代表我們最終返回的的結(jié)果集合，其元素是在整個算法運(yùn)行的過程中被逐漸添加的铜犬；Stack 是上面?zhèn)未a中提到的“椢柚眨”，用來存儲運(yùn)行時臨時保存的待考慮狀態(tài)（也就是還沒被檢查所有下一狀態(tài)的狀態(tài)）癣猾。

NFA 并行算法

輸入：NFA N, x(EOF)敛劝， s0（NFA的初態(tài)），F(xiàn)（NFA的終態(tài)集）

輸出：若 N 接受 x纷宇，打印“yes”夸盟，否則"no"

方法：用下面的過程對 x 進(jìn)行識別，其中 S 是一個狀態(tài)的集合

與前面的 模擬DFA 相比像捶，有如下區(qū)別：

但模擬 DFA 與模擬 NFA 也有一個共同點(diǎn)，就是【算法與模式無關(guān)】：DFA 和 NFA 都是作為數(shù)據(jù)（參數(shù)）交給算法的拓春，算法的運(yùn)行與具體的自動機(jī)無關(guān)释簿。

NFA 并行算法例：識別 abb 和 abab

所用的 NFA 如下圖所示

• 識別 abb：

  1. 計(jì)算初態(tài)集： ε-閉包( {0} ) = {0, 1, 2, 4, 7} 記作集合A

     該步驟創(chuàng)建初始狀態(tài)集

  2. 讀取到輸入字符 a，計(jì)算從 A 出發(fā)經(jīng)過 a 到達(dá)的狀態(tài)集：ε-閉包( smove(A, a) ) = {8, 3, 6, 7, 1, 2, 4} 記作集合B硼莽，B 的詳細(xì)計(jì)算過程如下庶溶，寫的比較細(xì)，懂的可以直接略過懂鸵。偏螺。

     因想要的是從狀態(tài)集合 A 出發(fā)進(jìn)行經(jīng)過 a 的狀態(tài)轉(zhuǎn)移再求個空閉包，因此我們需要對于集合 A 中的每個狀態(tài)匆光，都進(jìn)行一次 a 狀態(tài)轉(zhuǎn)移套像，再將轉(zhuǎn)移后的結(jié)果放入一個新的集合，最后對這個集合整體求一次空閉包终息。這一步驟夺巩，我們一步步來，首先我們建立一個臨時集合 T周崭，用于存放 A 集合中經(jīng)過 a 了轉(zhuǎn)移柳譬，卻還沒有進(jìn)行閉包運(yùn)算的狀態(tài)。

     1. 對集合 A 中的狀態(tài) 0休傍，沒有從 0 開始的 a 轉(zhuǎn)移，無事發(fā)生蹲姐，不需要填入集合 T磨取；
     2. 對集合 A 中的狀態(tài) 1人柿，沒有從 1 開始的 a 轉(zhuǎn)移，同樣不需要填入集合 T忙厌；
     3. 對集合 A 中的狀態(tài) 2凫岖，其經(jīng)過一次 a 轉(zhuǎn)移，到達(dá)狀態(tài) 3逢净，將 3 加入 T哥放，現(xiàn)在 T = {3}；
     4. 對集合 A 中的狀態(tài) 4爹土，沒有從該狀態(tài)開始的 a 轉(zhuǎn)移甥雕，不填入 T 集合；
     5. 對集合 A 中的狀態(tài) 7胀茵，其經(jīng)過一次 a 轉(zhuǎn)移社露，到達(dá)狀態(tài) 8，將 8 加入 T琼娘，現(xiàn)在 T = {3, 8}峭弟；

     至此， ε-閉包( smove(A, a) ) 中的 smove(A, a) 計(jì)算完成脱拼，其結(jié)果是 smove(A, a) = T = {3, 8}瞒瘸；

     接下來，對 T 進(jìn)行閉包運(yùn)算：

     1. 3 經(jīng)過一次空轉(zhuǎn)移熄浓，得到 6情臭；
     2. 3 向右側(cè)進(jìn)行一次空轉(zhuǎn)移，得到 7玉组；
     3. 3 向左側(cè)進(jìn)行一次空轉(zhuǎn)移谎柄，得到 1，再從這個 1 出發(fā)惯雳，進(jìn)行空轉(zhuǎn)移朝巫，得到 2、4石景；
     4. 沒有從 8 開始的空轉(zhuǎn)移劈猿。

     至此，ε-閉包( T )潮孽，也即 ε-閉包( smove(A, a) ) 計(jì)算完成揪荣，結(jié)果是{3, 8, 6, 7, 1, 2, 4}

  3. 讀取到輸入字符 b，計(jì)算從 B 出發(fā)經(jīng)過 b 到達(dá)的狀態(tài)集：ε-閉包( smove(B, b) )={9, 5, 6, 7, 1 , 2, 4}往史，記為集合 C（計(jì)算方法與上一步完全相同）仗颈；

  4. 讀取到輸入字符 b，計(jì)算從 C 出發(fā)經(jīng)過 b 到達(dá)的狀態(tài)集：ε-閉包( smove(C, c) )={10, 5, 6, 7, 1, 2, 4}，記為集合 D （計(jì)算方法與前兩步完全相同）挨决；

  5. 結(jié)束请祖。計(jì)算 D∩{10} = {10}，終態(tài)集與結(jié)果集交際非空脖祈，接受肆捕。識別的路徑為 AaBbCbD

  因此，我們可以確定盖高， 初態(tài)和終態(tài)之間存在一條為 abb 的路徑慎陵。

  但實(shí)際上，對abb的識別也可以認(rèn)為是：

  0 ε* A aε* B bε* C bε* D喻奥，即席纽，通過一個輸入字符進(jìn)行直接轉(zhuǎn)移后，再經(jīng)過若干次的空轉(zhuǎn)移映凳，轉(zhuǎn)移到了下一下一狀態(tài)集胆筒。路徑上的標(biāo)記是 ε*aε*bε*bε*，去掉空轉(zhuǎn)移就是 abb 了诈豌，即 ε*aε*bε*bε* = abb仆救。

• 識別 abab

  1. 初態(tài)集： ε-閉包( {0} ) = {0, 1, 2, 4, 7} 記作 A
  2. 從 A 出發(fā)經(jīng) a 到達(dá)：ε-閉包( smove(A, a) ) = {8, 3, 6, 7, 1, 2, 4} ，記作 B
  3. 從 B 出發(fā)經(jīng) b 到達(dá)：ε-閉包( smove(B, b) ) = {5, 9, 6, 7, 1, 2, 4} 矫渔，記作 C
  4. 從 C 出發(fā)經(jīng) a 到達(dá)：ε-閉包( smove(C, a) ) = {8, 3, 6, 7, 1, 2, 4} 彤蔽，等于 B
  5. 從 B 出發(fā)經(jīng) b 到達(dá)：ε-閉包( smove(B, b) ) = {5, 9, 6, 7, 1, 2, 4} ，等于 C

  識別路徑為：A a B b C a B b C庙洼，由于 C ∩ {10} = ?顿痪，所以不接受。

觀察上面的兩個識別過程可以發(fā)現(xiàn)油够，當(dāng)我們使用同一個 NFA 去識別兩個字串時蚁袭，產(chǎn)生了大量的重復(fù)計(jì)算（兩個例子的前三步是完全相同的，第二個例子中的 3石咬、5 也進(jìn)行了完全相同的轉(zhuǎn)移卻又重新進(jìn)行了計(jì)算）揩悄。

既然會出現(xiàn)對于相同輸入的、重復(fù)條件下的重復(fù)計(jì)算鬼悠，那么我們就可以在這里偷懶了——我們可以在正式使用一個 NFA 之前删性，對這個 NFA 進(jìn)行預(yù)先的分析和計(jì)算，把在各種狀態(tài)集情況下進(jìn)行的各種轉(zhuǎn)移情況計(jì)算出來焕窝，存儲在一張表中蹬挺。這樣當(dāng)我們真正分析輸入序列時，就可以根據(jù)當(dāng)前的狀態(tài)和要進(jìn)行的轉(zhuǎn)移去查表它掂、得到結(jié)果了巴帮！

這就是子集法構(gòu)造 DFA 的思路——子集法構(gòu)造 DFA，實(shí)際上就是對 NFA 并行識別記號方法的提前計(jì)算并記錄的過程！

將 NFA 上的全部路徑確定化并記錄下來榕茧，就能夠造出與該 NFA 等價的 DFA

下面舉個例子來說明 NFA 到 DFA 的轉(zhuǎn)化

這個例子假設(shè)了一個人要從甲地出發(fā)到達(dá)乙地发乔，如下圖左側(cè)部分所示。中間 1雪猪、2、3 是途中經(jīng)過的地點(diǎn)起愈，轉(zhuǎn)移的 c 指汽車只恨，b 指自行車，我們要找出從甲到乙的交通方式的組合抬虽。

這個問題的模型實(shí)際上是個 NFA官觅，就像圖上畫的那樣。對于該 NFA阐污，我們可以通過預(yù)計(jì)算的方式休涤，建立一個經(jīng)過狀態(tài)轉(zhuǎn)移到達(dá)到達(dá)狀態(tài)集的 DFA（DFA 中的每個狀態(tài)都是一個狀態(tài)集——以原來的 NFA 中的某些狀態(tài)為元素組成的集合）。該 DFA 與原 NFA 等效笛辟，能夠識別 cc功氨、ccb、cbb

DFA的優(yōu)點(diǎn)：

1. 消除了不確定性（將 NFA 的下一狀態(tài)集合手幢，合并為一個狀態(tài)）
2. 無需動態(tài)計(jì)算狀態(tài)集合（相對于模擬 NFA 算法）

對于有 k 個狀態(tài)的 NFA捷凄，與之等價的 DFA 最多有 2^k 個狀態(tài)（因?yàn)?DFA 中的每個狀態(tài)都是 NFA 所有狀態(tài)的一個子集，所以 DFA 的最大狀態(tài)數(shù)量就是 NFA 的子集數(shù)量）

從 NFA 到 DFA（子集法構(gòu)造 DFA ）

該算法將從 NFA 的初態(tài)開始围来，生成可達(dá)狀態(tài)機(jī)狀態(tài)之間的轉(zhuǎn)移關(guān)系跺涤。

輸入： NFA N 輸出： 等價于 N 的 DFA D。初態(tài) ε-閉包( {s0} )（這個東西的運(yùn)算結(jié)果监透，就是 NFA 的初態(tài)集）桶错，終態(tài)是含有 NFA 終態(tài)的狀態(tài)集合。 該算法中要用到兩個數(shù)據(jù)結(jié)構(gòu)：Dstates（狀態(tài)胀蛮，用于存儲生成的 DFA 狀態(tài)）院刁、Dtran（用于計(jì)算 DFA 狀態(tài)之間的狀態(tài)轉(zhuǎn)移） 方法：用下述過程構(gòu)造 DFA：

我們要將字母表中所有的字符都考慮一遍之后，才能說考慮完一個狀態(tài)和與之相關(guān)的狀態(tài)轉(zhuǎn)移醇滥。然后再去考慮其他沒有被標(biāo)記的狀態(tài)（也就是Dstates中的其他元素）黎比，即回到最外層的while，開始新的一輪循環(huán)——再去考慮在這個狀態(tài)下鸳玩，經(jīng)過字母表中所有字符能夠達(dá)到的狀態(tài)阅虫。

最后當(dāng) Dstates 中沒有剩余元素時，DFA就完全生成了不跟。最終得到的 Dstates 和 Dtran 就是我們最終生成的 DFA （即颓帝，我們得到了一個確定的狀態(tài)轉(zhuǎn)移表）

例：用上述算法構(gòu)造(a|b)*abb

根據(jù)這些運(yùn)算的結(jié)果，我們就可以構(gòu)造出來如下圖所示的自動機(jī)：

嗯，這樣就完成了我們的 DFA 了购城。

DFA 可真是個好東西吕座，一旦有了 DFA，我們就可以根據(jù)它來簡單地識別輸入序列了瘪板！不用再進(jìn)行那種粗野的蠻力計(jì)算了吴趴。

但，我們當(dāng)前的 DFA 就已經(jīng)是最優(yōu)了嗎侮攀？當(dāng)然不锣枝，還能優(yōu)化的！

再觀察我們上面畫出來的 DFA兰英，不難發(fā)現(xiàn)（老師說不難發(fā)現(xiàn)撇叁，我還真就沒看出來。畦贸。陨闹。），從 A 開始經(jīng)過a薄坏、b能夠到達(dá)的下一狀態(tài)趋厉，和從 C 開始經(jīng)過a、b能夠到達(dá)的下一狀態(tài)是相同的＝鹤埂（A經(jīng)過a到達(dá)B觅廓、A經(jīng)過b到達(dá)C；C經(jīng)過a到達(dá)B涵但、C經(jīng)過b到達(dá)C）

這種情況杈绸，我們就說 A、C 是等價的：分別以這兩個為初始狀態(tài)矮瘟，在經(jīng)過不同的輸入序列轉(zhuǎn)移后達(dá)到的效果完全相同瞳脓。

這樣，我們就可以把A澈侠、C合并劫侧，改寫成下面的形式——從A、C出發(fā)的都改為從0出發(fā)哨啃，修改后就能得到新的DFA烧栋，減少了一個狀態(tài)。這就叫最小化 DFA

具體的最小化拳球，下篇博客再說审姓，這個已經(jīng)太長了。祝峻。魔吐。扎筒。。酬姆。