第3章有窮自動機編譯原理陳炬樺

有窮自動機的形式定義

定義3.1

一個確定型有窮自動機DFA是一個五元組

DFA=（Q,Σ,t,q0,F）

Q：非空有窮狀態集；

Σ：有窮輸入字母表；

t：是一個單值映射t(q,a)q’

q0：開始狀態，q0∈QF：非空終止狀態集

DFA狀態轉換(左表)圖

abq0q1q3q1q0q2q2q3q1q3q2q0有窮自動機的擴充的映射

定義3.2DFA=（Q,Σ,t,q0,F）擴充的映射

t：定義為①t(q,ε)=q②t(q,aα)=t(t(q,a),α)

定義3.3DFA=（Q,Σ,t,q0,F），如果t(q0,α)=q∈F，稱α為DFA接收。定義3.4

兩個有窮自動機A1和A2，如果L(A1)=L(A2)，則稱自動機A1與A2等價。

非確定型有窮自動機NDFA定義3.5

一個非確定型有窮自動機NDFA是一個五元組

NDFA=(Q,Σ,t,Q0,F)t：是一個多值映射

Q0：開始狀態集,Q0Q例3.6NDFA

NDFA到DFA的轉換

空移環路的尋找和消除

NDFA到DFA的轉換

消除空移

如果B是終止狀態，置A為終止狀態；

如果A是開始狀態，置B為開始狀態；確定化——子集法

設NDFAA=（Q,Σ,t,Q0,F）設一個非確定型有窮自動機，它的語言為L（A）,可以構造一個與它等價的確定型有窮自動機DFAA’=（Q,Σ,t,q0,F）,L（A）=L（A’）

確定化——造表法

xy[q0][q1,q2][q0][q1,q2][q0,q3][q1,q2,q3][q0,q3][q1,q2,q3][q0,q3][q1,q2,q3][q0,q1,q3][q1,q2,q3][q0,q1,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3][q0,q1,q2,q3]NFA->DFAxy[q0]q0’[q1,q2]q1’[q0]q0’[q1,q2]q1’[q0,q3]q2’[q1,q2,q3]q3’[q0,q3]q2’[q1,q2,q3]q3’[q0,q3]q2’[q1,q2,q3]q3’[q0,q1,q3]q4’[q1,q2,q3]q3’[q0,q1,q3]q4’[q0,q1,q2,q3]q5’[q0,q1,q2,q3]q5’[q0,q1,q2,q3]q5’[q0,q1,q2,q3]q5’[q0,q1,q2,q3]q5’

用了q’別名去替換εNDFA的確定化

εNDFA=（Q,Σ∪{ε},t,Q0,F）定義3.8狀態子集I的ε-閉包，

ε-closure(I)={q|t(I,ε)=q}定義3.9Ia=ε-closure(J)，其中J=t(I,a)NFA-ε

->

NFAεNDFA的確定化舉例

IxIy0[S]1[1,2,3]1[1,2,3]2[4]3[2,3,5]2[4]

4[6,7,8]3[2,3,5]5[4,6,7,8]3[2,3,5]4[6,7,8]6[7,8]5[4,6,7,8]6[7,8]4

[6,7,8]6[7,8]6[7,8]DFA的化簡

<1>終止狀態與非終止狀態可區分的，分成子集<2>對所有子集對所有輸入符號判斷，如果可區分則分解子集<3>如果<2>有分解子集，轉<2>，否則結束。從化簡的DFA到程序設計

DFA的化簡舉例xy0,2②×0|21,3,4,5①×1|3,4,5B1D3,4,5A0C2正規文法與有窮自動機

從正規文法到FA

G={VN，VT，P，S}FA=（Q,Σ,t,q0,F）

q0={S}Σ=VT在FA增加一個終止狀態Z，F={Z},Q=VN∪FA→aB=>t(A,a)=B；A→a=>t(A,a)=Z正規文法與有窮自動機舉例

從正規文法到FA例3.14G19[S]：

S→aS|aA|bBA→bA|cCB→aB|dDC→cC|cD→dD|d正規文法與有窮自動機

從FA到正規文法

FA=（Q,Σ,t,q0,F)G=(VN，VT，P，S)

VN=QVT=ΣS=q0t(A,a)=B=>A→aB,如果A∈F,A→ε正規文法與有窮自動機舉例

從FA到正規文法

例3.15

G20[S]：

S→xA|yBA→yA|yC|xBB→xC|yC|yA|εC→ε

正規表達式的定義

定義3.12字母表Σ上的正規表達式和正規集遞歸定義如下

符號正規表達式正規集regular

seta∈Σa{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)*正規表達式到NDFA的轉換

正規表達式到NDFA的轉換舉例NDFA到正規表達式的轉換

NDFA到正規表達式的轉換[(x!yy)(y|xy)*(y|x(x|y)]|[(y|xy*x)(yy*x)*(yy*y|x|y)]正規文法到正規表達式

規則：U→αV，V→β轉換為U→αβU→αU|β轉換為U→α*βU→α|β

轉換為

U→α|β

正規文法到正規表達式舉例S→aS|aA|bBA→bA|cCB→aB|dDC→cC|cD→dD|dS→aS|(ab*cc*c|ba*dd*d)→a*ab*cc*c|a*ba*dd*dA→bA|cc*c→b*cc*cB→aB|dd*d→a*dd*dC→c*cD→d*d舉例

①構造該正則式所對應的NFA(畫出轉換圖)設字母表∑：{a,b}，給出∑上的一個正則式aa*bb*(ab*)*b。①構造該正則式所對應的NFA(畫出轉換圖)②將所求的NFA確定化(畫出DFA的轉換圖)③將所求的DFA最小化(畫出極小化后的轉換圖)；

②將所求的NFA確定化(畫出DFA的轉換圖)abq0[S]q1[1,2,3]

q1[1,2,3]q2[2,3]q3[4,5,6,7,10]q2[2,3]q2[2,3]q3[4,5,6,7,10]q3[4,5,6,7,10]q4[8,9,7,10]q5[5,6,710,Z]q4[8,9,7,10]q4[8,9,7,10]q6[9,7,10,Z]q5[5,6,710,Z]q4[8,9,7,10]q5[5,6,710,Z]q6[9,7,10,Z]q4[8,9,7,10]q6[9,7,10,Z]abA0123401234AAAAAXAABBB56A0B1212BBCCC3434CCDDD5656CCDD舉例

①構造該正則式所對應的NFA(畫出轉換圖)設字母表∑：{0，1}，給出∑上的一個正則式

1（01）*(10|1)*0*。①構造該正則式所對應的NFA(畫出轉換圖)；②將所求的NFA確定化(畫出DFA的轉換圖)；③將所求的DFA最小化(畫出極小化后的轉換圖)；

②確定化01A[S]B[1,2,4,5,7,8,Z]B[1,2,4,5,7,8,Z]C[3,8,Z]D[5,6,7,8,Z]C[3,8,Z]E[8,Z]F[2,4,5,7,8,Z]D[5,6,7,8,Z]G[5,7,8,Z]D[5,6,7,8,Z]E[8,Z]E[8,Z]

F[2,4,5,7,8,Z]C[3,8,Z]D[5,6,7,8,Z]G[5,7,8,Z]E[8,Z]D[5,6,7,8,Z]③

最小化

01a[A]

b[B,