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

第二章：詞法分析

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

S，是非確定有限自動機的初始狀態(tài)集；f是一個從S×(∪{})到S的子集的映射，即S×(∪{})→2sZS，是一個終止狀態(tài)集，又稱為接受狀態(tài)集1.2DFA和NFA的區(qū)別總結(jié)來看有3點區(qū)別一個狀態(tài)的不同輸出邊可以標有相同符號允許有多個開始狀態(tài)允許有空邊1.3NFA的一些問題NFA所能接受的串與DFA的定義是相同的實現(xiàn)起來很困難aa,b102aba2.1自動機等價定義：設A1和A2是同一個字母表上的自動機，如果有L(A1)=L(A2),則稱A1和A2等價定理：對于每一個非確定自動機A,存在一個確定自動機A’,使得L(A)=L(A’)2.2NFA到DFA的轉(zhuǎn)換狀態(tài)集I的ε閉包：設I是NFAM狀態(tài)集的子集，定義I的ε閉包ε-CLOSURE(I)為：若q∈I,則q∈ε_CLOSURE(I).若q∈I,那么從q出發(fā)經(jīng)任意條ε弧而能到達的任何狀態(tài)q'都屬于ε-CLOSURE(I).2.2NFA到DFA的轉(zhuǎn)換狀態(tài)集I的a轉(zhuǎn)換：若I={S1,…,Sm}是NFA的狀態(tài)集的一個子集，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'的初始狀態(tài)為I0'=_CLOSURE({S1,S2,…Sk}),其中S1…Sk是A的全部初始狀態(tài)。若I={S1,…,Sm}是A'的一個狀態(tài)，a，則定義f'(I,a)=Ia將Ia加入S'，重復該過程，直到S'不產(chǎn)生新狀態(tài)。若I'={S1,…,Sn}是A'的一個狀態(tài),且存在一個Si是A的終止狀態(tài)，則令I'為A'的終止狀態(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}對應1{2,4,5,6,7}對應2{3,8}對應3{3,8,9}對應4{9}對應513245babaa2.2NFA到DFA的轉(zhuǎn)換另外一種消除空邊的轉(zhuǎn)換方式刪去空邊，增加0到2的邊ε環(huán)路的時候，就把這幾個狀態(tài)合成一個a10a2aa10a22.3自動機的最小化定義：等價狀態(tài)

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

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

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