編譯原理及實(shí)現(xiàn)技術(shù)：4-詞法分析-NFA與最小化

第二章：詞法分析

NFA與自動(dòng)機(jī)的最小化內(nèi)容介紹非確定有限自動(dòng)機(jī)（NFA）的定義NFA到DFA的轉(zhuǎn)換自動(dòng)機(jī)的最小化自動(dòng)機(jī)的化簡1.1非確定有限自動(dòng)機(jī)的定義非確定有限自動(dòng)機(jī)NFA為一個(gè)五元組(,S,S0,f,Z)，其中：是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；S是狀態(tài)的集合，它的每個(gè)元素稱為一個(gè)狀態(tài)；S0

S，是非確定有限自動(dòng)機(jī)的初始狀態(tài)集；f是一個(gè)從S×(∪{})到S的子集的映射，即S×(∪{})→2sZS，是一個(gè)終止?fàn)顟B(tài)集，又稱為接受狀態(tài)集1.2DFA和NFA的區(qū)別總結(jié)來看有3點(diǎn)區(qū)別一個(gè)狀態(tài)的不同輸出邊可以標(biāo)有相同符號(hào)允許有多個(gè)開始狀態(tài)允許有空邊1.3NFA的一些問題NFA所能接受的串與DFA的定義是相同的實(shí)現(xiàn)起來很困難aa,b102aba2.1自動(dòng)機(jī)等價(jià)定義：設(shè)A1和A2是同一個(gè)字母表上的自動(dòng)機(jī)，如果有L(A1)=L(A2),則稱A1和A2等價(jià)定理：對于每一個(gè)非確定自動(dòng)機(jī)A,存在一個(gè)確定自動(dòng)機(jī)A’,使得L(A)=L(A’)2.2NFA到DFA的轉(zhuǎn)換狀態(tài)集I的ε閉包：設(shè)I是NFAM狀態(tài)集的子集，定義I的ε閉包ε-CLOSURE(I)為：若q∈I,則q∈ε_(tái)CLOSURE(I).若q∈I,那么從q出發(fā)經(jīng)任意條ε弧而能到達(dá)的任何狀態(tài)q'都屬于ε-CLOSURE(I).2.2NFA到DFA的轉(zhuǎn)換狀態(tài)集I的a轉(zhuǎn)換：若I={S1,…,Sm}是NFA的狀態(tài)集的一個(gè)子集，a∈,則定義:Ia=ε-CLOSURE(J)其中:J=f(S1,a)f(S2,a)…f(Sm,a)2.2NFA到DFA的轉(zhuǎn)換已知A：NFA,構(gòu)造A':DFA令A(yù)'的初始狀態(tài)為I0'=_CLOSURE({S1,S2,…Sk}),其中S1…Sk是A的全部初始狀態(tài)。若I={S1,…,Sm}是A'的一個(gè)狀態(tài)，a，則定義f'(I,a)=Ia將Ia加入S'，重復(fù)該過程，直到S'不產(chǎn)生新狀態(tài)。若I'={S1,…,Sn}是A'的一個(gè)狀態(tài),且存在一個(gè)Si是A的終止?fàn)顟B(tài)，則令I(lǐng)'為A'的終止?fàn)顟B(tài)。2.2NFA到DFA的轉(zhuǎn)換a219b45aa38bba67例子：2.2NFA到DFA的轉(zhuǎn)換

輸入字

狀態(tài)ab+{1,2}{2,4,5,6,7}{3,8}-{2,4,5,6,7}{}{3,8,9}{3,8}{9}{}-{3,8,9}{9}{}-{9}{}{}2.2NFA到DFA的轉(zhuǎn)換轉(zhuǎn)化后的結(jié)果{1,2}對應(yīng)1{2,4,5,6,7}對應(yīng)2{3,8}對應(yīng)3{3,8,9}對應(yīng)4{9}對應(yīng)513245babaa2.2NFA到DFA的轉(zhuǎn)換另外一種消除空邊的轉(zhuǎn)換方式刪去空邊，增加0到2的邊ε環(huán)路的時(shí)候，就把這幾個(gè)狀態(tài)合成一個(gè)a10a2aa10a22.3自動(dòng)機(jī)的最小化定義：等價(jià)狀態(tài)

設(shè)DFAM的兩個(gè)狀態(tài)S1和S2,如果對任意輸入的符號(hào)串x，從S1和S2出發(fā)，總是同時(shí)到達(dá)接受狀態(tài)或拒絕狀態(tài)中，則稱S1和S2是等價(jià)的。1234567abccbd2.3自動(dòng)機(jī)的最小化定義：無關(guān)狀態(tài)設(shè)S是DFAM的一個(gè)狀態(tài)，若：從開始狀態(tài)無到S的通路，或S到任意終止?fàn)顟B(tài)無通路則稱S為M的無關(guān)狀態(tài)

102ab102ab2.3自動(dòng)機(jī)的最小化定義：最小(最簡)自動(dòng)機(jī)如果DFAM沒有無關(guān)狀態(tài)，也沒有等價(jià)狀態(tài)，則稱M為最小自動(dòng)機(jī)結(jié)論：任一DFA都可以化為最簡自動(dòng)機(jī)，即任一DFAM都存在DFAM'，使得L(M)=L(M')，且M'是最簡自動(dòng)機(jī)

2.4自動(dòng)機(jī)的化簡狀態(tài)分離法終止?fàn)顟B(tài)為一組，非終止?fàn)顟B(tài)為一組對每一組進(jìn)行分離，若每組中的元素映射到不同的組，則表示他們不等價(jià)，就可以劃分出來。重復(fù)2，知道沒有新組產(chǎn)生，此時(shí)每組中的狀態(tài)都為等價(jià)狀態(tài)。2.4自動(dòng)機(jī)的化簡例1aa17b32bab5abaa46bb8bab2.4自動(dòng)機(jī)的化簡1,3ba4,6,7,8a2,5bb2.4自動(dòng)機(jī)的化簡例2a15