編譯原理：第3章 有窮自動(dòng)機(jī)

1、第3章 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)的形式定義 定義3.1 一個(gè)確定型有窮自動(dòng)機(jī)DFA是一個(gè)五元組 DFA=（Q , , t, q0, F） Q：非空有窮狀態(tài)集； ：有窮輸入字母表； t：是一個(gè)單值映射 t(q,a) q q0：開(kāi)始狀態(tài)， q0Q F：非空終止?fàn)顟B(tài)集 DFA狀態(tài)轉(zhuǎn)換(左表)圖 abq0q1q3q1q0q2q2q3q1q3q2q0有窮自動(dòng)機(jī)的擴(kuò)充的映射 定義 3.2 DFA=（Q , , t, q0, F） 擴(kuò)充的映射 t： 定義為 t(q,)=q t(q,a)= t(t(q,a),) 定義 3.3 DFA=（Q , , t, q0, F）， 如果 t(q0,)=qF，稱為DFA接收。

2、定義 3.4 兩個(gè)有窮自動(dòng)機(jī)A1和A2， 如果L(A1)=L(A2)，則稱自動(dòng)機(jī)A1與A2等價(jià)。 非確定型有窮自動(dòng)機(jī)NDFA定義 3.5 一個(gè)非確定型有窮自動(dòng)機(jī)NDFA是一個(gè)五元組 NDFA=(Q , , t, Q0, F) t：是一個(gè)多值映射 Q0：開(kāi)始狀態(tài)集, Q0 Q例3.6 NDFA NDFA到DFA的轉(zhuǎn)換 空移環(huán)路的尋找和消除 NDFA到DFA的轉(zhuǎn)換 消除空移 如果B是終止?fàn)顟B(tài)，置A為終止?fàn)顟B(tài)； 如果A是開(kāi)始狀態(tài)，置B為開(kāi)始狀態(tài)；確定化子集法 設(shè)NDFA A=（Q , , t, Q0, F）設(shè)一個(gè)非確定型有窮自動(dòng)機(jī)，它的語(yǔ)言為L(zhǎng)（A）,可以構(gòu)造一個(gè)與它等價(jià)的確定型有窮自動(dòng)機(jī) DFA

3、A=（Q , , t, q0, F）, L（A）= L（A） 確定化造表法 xyq0q1,q2q0q1,q2q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q1,q3q1,q2,q3q0,q1,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3xyq0q0q1,q2q1q0q0q1,q2q1q0,q3q2q1,q2,q3q3q0,q3q2q1,q2,q3q3q0,q3q2q1,q2,q3q3q0,q1,q3q4q1,q2,q3q3q0,q1,q3q4q0,q1,q2,q3q5q0,q1,q2,q

4、3q5q0,q1,q2,q3q5q0,q1,q2,q3q5q0,q1,q2,q3q5NDFA的確定化 NDFA=（Q , t, Q0, F）定義 3.8 狀態(tài)子集 I的-閉包， -closure (I)=q | t (I, )=q 定義 3.9 Ia=-closure (J)，其中J=t (I,a)NDFA的確定化舉例IxIy0S11,2,311,2,32432,3,52446,7,832,3,554,6,7,832,3,546,7,867,854,6,7,867,84 6,7,867,867,8DFA的化簡(jiǎn) 終止?fàn)顟B(tài)與非終止?fàn)顟B(tài)可區(qū)分的，分成子集 對(duì)所有子集對(duì)所有輸入符號(hào)判斷，如果可區(qū)分則分

5、解子集 如果有分解子集，轉(zhuǎn)，否則結(jié)束。從化簡(jiǎn)的DFA到程序設(shè)計(jì) DFA的化簡(jiǎn)舉例xy0, 2 0 | 21,3,4,51 | 3,4,5B1D3,4,5A0C2正規(guī)文法與有窮自動(dòng)機(jī) 從正規(guī)文法到FA G=VN，VT，P，SFA=（Q , , t, q0, F） q0=S= VT在FA增加一個(gè)終止?fàn)顟B(tài)Z，F(xiàn)=Z, Q =VNFAaB=t(A,a)=B； Aa=t(A,a)=Z正規(guī)文法與有窮自動(dòng)機(jī)舉例從正規(guī)文法到FA例3.14 G19S： SaS | aA | bB AbA | cC BaB | dD CcC | c DdD | d正規(guī)文法與有窮自動(dòng)機(jī)從FA到正規(guī)文法 FA=（Q , , t, q

6、0, F) G=(VN，VT，P，S) VN=QVT= S=q0t(A,a)=B =AaB,如果AF, A正規(guī)文法與有窮自動(dòng)機(jī)舉例從FA到正規(guī)文法 例3.15 G20S： SxA | yB AyA | yC | xB BxC | yC | yA | C 正規(guī)表達(dá)式的定義 定義 3.12 字母表上的正規(guī)表達(dá)式和正規(guī)集遞歸定義如下 符號(hào)正規(guī)表達(dá)式正規(guī)集aa a e1與e2L(e1)與L(e2)e1 | e2L(e1 | e2)= L(e1 )L( e2)e1. e2L(e1 . e2)= L(e1 ) L( e2)( e1 )*L( e1 )*)= L( e1 )*正規(guī)表達(dá)式到NDFA的轉(zhuǎn)換 正規(guī)

7、表達(dá)式到NDFA的轉(zhuǎn)換舉例NDFA到正規(guī)表達(dá)式的轉(zhuǎn)換 NDFA到正規(guī)表達(dá)式的轉(zhuǎn)換(x!yy)(y|xy)*(y|x(x|y)|(y|xy*x)(yy*x)*(yy*y|x|y)正規(guī)文法到正規(guī)表達(dá)式 規(guī)則： UV，V 轉(zhuǎn)換為 UUU| 轉(zhuǎn)換為 U*U| 轉(zhuǎn)換為 U| 正規(guī)文法到正規(guī)表達(dá)式舉例SaS | aA | bB AbA | cCBaB | dD CcC|c DdD | dSaS | (a b* c c* c | b a*d d*d) a* a b* c c* c | a*b a*d d*d AbA | c c* c b* c c* cBaB | d d*d a*d d*dCc* cDd*d

8、 舉例構(gòu)造該正則式所對(duì)應(yīng)的NFA(畫(huà)出轉(zhuǎn)換圖)設(shè)字母表：a, b，給出上的一個(gè)正則式aa*bb*(ab*)*b 。構(gòu)造該正則式所對(duì)應(yīng)的NFA(畫(huà)出轉(zhuǎn)換圖)將所求的NFA確定化(畫(huà)出DFA的轉(zhuǎn)換圖)將所求的DFA最小化(畫(huà)出極小化后的轉(zhuǎn)換圖)； 將所求的NFA確定化(畫(huà)出DFA的轉(zhuǎn)換圖)abq0Sq11,2,3q11,2,3q22,3q34,5,6,7,10q22,3q22,3q34,5,6,7,10q34,5,6,7,10q48,9,7,10q55,6,7 10,Zq48,9,7,10q48,9,7,10q69,7,10,Zq55,6,7 10,Zq48,9,7,10q55,6,7 10,Zq

9、69,7,10,Zq48,9,7,10q69,7,10,ZabA0 1 2 3 40 1 2 3 4AAAAAXAABBB5 6A0B1 21 2BBCCC3 43 4CCDDD5 65 6CCDD舉例構(gòu)造該正則式所對(duì)應(yīng)的NFA(畫(huà)出轉(zhuǎn)換圖)設(shè)字母表：0，1，給出上的一個(gè)正則式 1（01）* (10|1) * 0 *。構(gòu)造該正則式所對(duì)應(yīng)的NFA(畫(huà)出轉(zhuǎn)換圖)；將所求的NFA確定化(畫(huà)出DFA的轉(zhuǎn)換圖)；將所求的DFA最小化(畫(huà)出極小化后的轉(zhuǎn)換圖)； 確定化01ASB1,2,4,5,7,8,ZB1,2,4,5,7,8,ZC3,8,ZD5,6,7,8,ZC3,8,ZE8,ZF2,4,5,7,8,ZD5,6,7,8,ZG5,7,8,ZD5,6,7,8,ZE8,ZE8,ZF2,4,5,7,8,ZC3,8,ZD5,6,7,8,ZG5,7,8,ZE8,ZD5,6,7,8,Z 最小化 01aAbB,