計應大三上-編譯原理3章_第1頁
計應大三上-編譯原理3章_第2頁
計應大三上-編譯原理3章_第3頁
計應大三上-編譯原理3章_第4頁
計應大三上-編譯原理3章_第5頁
免費預覽已結束,剩余29頁可下載查看

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

第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,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論