構(gòu)造正規(guī)式最小DFA方法

1、今天早上去圖書館，去看編譯原理，想把這部分搞清楚，看著龍書+國產(chǎn)的某一本不知什么的習(xí)題與解析，猜過程。猜原理。終于是看懂了。整體的步驟是三步：一，先把正規(guī)式轉(zhuǎn)換為 NFA （非確定有窮自動(dòng)機(jī)），二，在把NFA通過“子集構(gòu)造法”轉(zhuǎn)化為 DFA ,三，在把DFA通過“分割法”進(jìn)行最小化。AA4a5X301(bl<z)團(tuán)£3正w表達(dá)式到有隈口動(dòng)粗的轉(zhuǎn)擬規(guī)!<«這樣就能轉(zhuǎn)換到NFA 了。給岀一個(gè)例題，來自Google book 。本文主要根據(jù)這個(gè)例題來講，圖2構(gòu)造與正達(dá)式(a* L b") Cba”等&的DFAdKtFri.首先構(gòu)造正則表達(dá)式的NFA,

2、其構(gòu)過程如圖2.11所示中二.子集構(gòu)造法。同樣的例題，把轉(zhuǎn)換好的I1亠02.1 氣4乩機(jī)九斜熄川人91(4.6.7,9111,3,4,5.,7.8.9|6(1,6.7,9討5了.時(shí)!8?柑N(yùn)FA確定化，圖3這個(gè)表是從NFA到DFA的時(shí)候必須要用到的。第一列第一行I的意思是從NFA的起始節(jié)點(diǎn)經(jīng)過 任意個(gè)e所能到達(dá)的結(jié)點(diǎn)集合。la表示從該集合開始經(jīng)過一個(gè) a所能到達(dá)的集合，經(jīng)過一個(gè)a的意 思是可以略過前后的e。同樣lb也就是經(jīng)過一個(gè)b，可以略過前后任意個(gè)至于第二行以及后面的I是怎么確定的。我參考了一些題目才明白，原來就是看上面的la和lb哪個(gè)還沒岀現(xiàn)在I列，就拿下來進(jìn)行運(yùn)算，該列對(duì)應(yīng)的la和lb就

3、是前面我說的那樣推導(dǎo)。這步做完以后，為了畫岀最后的DFA，那么肯定得標(biāo)岀一些號(hào)來，比如1.2.3.。或者A ° B° c，我一般標(biāo)的方法是先把I列全部標(biāo)上1.2.3.遞增。然后看1表示的集合和la和lb中的哪個(gè)集合一樣， 就把那個(gè)集合也表示為1.繼續(xù)向下做。最后會(huì)得到這樣一個(gè)表格。圖4遠(yuǎn)abf OU1264Q2S203360413A65至此，就可以表示岀 DFA 了。就對(duì)照上面那個(gè)表，從 0節(jié)點(diǎn)開始經(jīng)過a到1.經(jīng)過b到2，就這樣 畫就仃了° °最后的DFA如下圖，圖5這個(gè)是怎么來的呢。去看看圖會(huì)發(fā)現(xiàn)有些項(xiàng)之前有雙圈標(biāo)志，這個(gè)是因?yàn)殡p圈的表示終態(tài)，在NFA

4、圖2中，9為終態(tài)，所以所有包含9的集合都被認(rèn)為是終態(tài)集，改成1.2.3.。°方便畫節(jié)點(diǎn)后就需 要把這些點(diǎn)作為終態(tài)了。 °三.最小化，分割法。FA的最小化就是尋求最小狀態(tài) DFA最小狀態(tài)DFA的含義：1.沒有多余狀態(tài)（死狀態(tài)）2.沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）兩個(gè)狀態(tài)s和t等價(jià)的條件：兼容性（一致性）條件一一同是終態(tài)或同是非終態(tài)傳播性（蔓延性）條件從 s岀發(fā)讀入某個(gè)a和從t岀發(fā)經(jīng)過某個(gè)a并且經(jīng)過某個(gè)b到達(dá)的狀態(tài)等價(jià)。就是相同。DFA的最小化一例子，第一步都是固定的。分成終態(tài)和非終態(tài)k1= C,D,E,F 組成，一個(gè)由非終態(tài) k2= S,A,1 .將M的狀態(tài)分為兩個(gè)子集一個(gè)由終態(tài)B組成，2 .考察S,A,B 是否可分.aSBA因?yàn)锳經(jīng)過a為S, B,A,到達(dá)C屬于k1.而S經(jīng)過a到達(dá)A屬于k2.B經(jīng)過a到達(dá)A屬于k2，所以K2繼續(xù)劃分3 .考察S,B是否可再分:B經(jīng)過b到達(dá)D屬于k1.S經(jīng)過b到達(dá)B屬于k2，所以S, B可以劃分。劃分為S,BD,E,F 是否可再分:4 考察C,因?yàn)镃,D,E,F經(jīng)過a和b到達(dá)的狀態(tài)都屬于C,D,E,F=k1所以相同，所以不可再分:5. C,D,E,F 以D來代替則，因?yàn)?CDEF相同，你也可以用