整體的步驟是三步：?
一，先把正規(guī)式轉(zhuǎn)換為NFA（非確定有窮自動機）,?
二，在把NFA通過“子集構(gòu)造法”轉(zhuǎn)化為DFA，?
三，在把DFA通過“分割法”進行最小化。


一步很簡單，就是反復(fù)運用下圖的規(guī)則，圖1?




這樣就能轉(zhuǎn)換到NFA了。?

給出一個例題，來自Google book。本文主要根據(jù)這個例題來講，圖2?

?
二.子集構(gòu)造法。?
同樣的例題，把轉(zhuǎn)換好的NFA確定化，圖3?




這個表是從NFA到DFA的時候必須要用到的。第一列第一行I的意思是從NFA的起始節(jié)點經(jīng)過任意個ε所能到達的結(jié)點集合。Ia表示從該集合開始經(jīng)過一個a所能到達的集合，經(jīng)過一個a的意思是可以略過前后的ε。同樣Ib也就是經(jīng)過一個b，可以略過前后任意個ε。?
至于第二行以及后面的I是怎么確定的。我參考了一些題目才明白，原來就是看上面的Ia和Ib哪個還沒出現(xiàn)在I列，就拿下來進行運算，該列對應(yīng)的Ia和Ib就是前面我說的那樣推導(dǎo)。


如果還不太明白，看圖就是了。你會發(fā)現(xiàn)I中的幾個項目都在Ia和Ib中出現(xiàn)了。而且是完全出現(xiàn)


這步做完以后，為了畫出最后的DFA，那么肯定得標出一些號來，比如1.2.3.。或者A。 B。c，我一般標的方法是先把I列全部標上1.2.3.遞增。然后看1表示的集合和Ia和Ib中的哪個集合一樣，就把那個集合也表示為1.繼續(xù)向下做。最后會得到這樣一個表格。圖4?




至此，就可以表示出DFA了。就對照上面那個表，從0節(jié)點開始經(jīng)過a到1.經(jīng)過b到2，就這樣畫就行了。。


最后的DFA如下圖，圖5?




雙圈的表示終態(tài)，這個是怎么來的呢。去看看圖4，會發(fā)現(xiàn)有些項之前有雙圈標志，這個是因為在NFA圖2中，9為終態(tài)， ，改成1.2.3.。。方便畫節(jié)點后就需要把這些點作為終態(tài)了。。

三.最小化，分割法。

FA的最小化就是尋求最小狀態(tài)DFA

最小狀態(tài)DFA的含義:?
1.沒有多余狀態(tài)(死狀態(tài))

?

除多余狀態(tài)?
什么是多余狀態(tài)？?
從這個狀態(tài)沒有通路到達終態(tài)；S1?
從開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)。S2?
如何消除多余狀態(tài)？?
刪除

2. 沒有兩個狀態(tài)是互相等價（不可區(qū)別）?
兩個狀態(tài)s和t等價的條件：?
兼容性（一致性）條件——同是終態(tài)或同是非終態(tài)?
傳播性（蔓延性）條件——對于所有輸入符號，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)換到等價的狀態(tài)里。。

DFA的最小化—例子，第一步都是固定的。分成終態(tài)和非終態(tài)

１．將Ｍ的狀態(tài)分為兩個子集一個由終態(tài)k1=｛Ｃ，Ｄ，Ｅ，Ｆ｝組成，一個由非終態(tài)k2=｛Ｓ，Ａ，Ｂ｝組成，

２．考察｛Ｓ，Ａ，Ｂ｝是否可分．

因為Ａ經(jīng)過a到達C屬于k1.而S經(jīng)過a到達A屬于k2.B經(jīng)過a到達A屬于k2，所以K2繼續(xù)劃分為{S，B},{A},

３．考察｛Ｓ，Ｂ｝是否可再分：

B經(jīng)過b到達D屬于k1.S經(jīng)過b到達B屬于k2，所以S，B可以劃分。劃分為{S},{B}

４．考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分：?
因為Ｃ，Ｄ，Ｅ，Ｆ經(jīng)過a和b到達的狀態(tài)都屬于｛Ｃ，Ｄ，Ｅ，Ｆ｝=k1所以相同，所以不可再分：

５．｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝來代替則，因為CDEF相同，你也可以用C來代替。無所謂的最小化的ＤＦＡ如圖，：?

轉(zhuǎn)自：http://blog.csdn.net/qq_23100787/article/details/50402643

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的【编译原理】:NFA转变为DFA的子集构造法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。