




下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 齒輪技術員崗位面試問題及答案
- 智能教學設備運維師崗位面試問題及答案
- 知識圖譜工程師崗位面試問題及答案
- 湖南省邵東三中2025屆高一下化學期末監測試題含解析
- 2025屆新疆昌吉市第九中學高一化學第二學期期末學業水平測試試題含解析
- 第六單元名著導讀《水滸傳》基本知識點梳理+2025-2026學年統編版語文九年級上冊
- 中子星吸積現象-洞察及研究
- 桐廬退役警犬管理辦法
- 北京社區規約管理辦法
- 材料安裝合同管理辦法
- 2025全員安全生產責任制范本
- 林業行政執法培訓
- 電大考試試題及答案商法
- 廣西壯族自治區柳州市上進聯考2024-2025學年高一下學期6月期末聯合考試數學試題(含答案)
- 高中英語必背3500單詞表完整版
- 大連農商銀行2024年招聘172人管理單位遴選500模擬題附帶答案詳解
- 安徽省工傷職工停工留薪期分類目錄
- 2019-2020學年湖南長沙長郡中學高一入學分班考試數學卷(常用)
- 職業安全衛生知識競賽題
- SLAP損傷的治療課件
- 廣東省外語藝術職業學院后勤服務項目檢查評分標準
評論
0/150
提交評論