chap02-形式語言與自動機(jī)理論基礎(chǔ)(有限自動機(jī))課件

有限自動機(jī)確定的有限自動機(jī)（DFA）非確定的有限自動機(jī)（NFA）NFA轉(zhuǎn)換為等價的DFA確定的有限自動機(jī)（DFA）的化簡（最小化）1整體概述THEFIRSTPARTOFTHEOVERALLOVERVIEW,PLEASESUMMARIZETHECONTENT第一部分2有限自動機(jī)(DeterministicFiniteAutomata)一.

DFA的定義二.DFA的三種表示三.DFA接受的語言確定的有限自動機(jī)(DFA)3一DFAM定義一個確定的有限自動機(jī)DFAM是一個五元組Ｍ＝（Σ，S，S0，Z，f）

Σ是一個字母表，它的每個元素稱為一個輸入符號。

S是一個有限狀態(tài)集合。

S0∈S，S0稱為初始狀態(tài)。

Z是S的子集，稱為終結(jié)狀態(tài)集合。

f是一個從S×Σ到S的單值映射

f(ｑ，ａ)＝ｑ’（ｑ,ｑ’∈S，ａ∈Σ）表示當(dāng)前狀態(tài)為q,輸入符號為a時，自動機(jī)將轉(zhuǎn)換到下一個狀態(tài)ｑ’，ｑ’稱為ｑ的后繼。4例設(shè)ＤＦＡＭ＝（｛ａ，ｂ｝，｛０，１，２，３｝，０，｛３｝，f）其中f（０，ａ）＝１，f（１，ａ）＝３f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３二

ＤＦＡ的三種表示：（1）用轉(zhuǎn)換函數(shù)（2）轉(zhuǎn)移矩陣（3）狀態(tài)轉(zhuǎn)換圖5所謂確定的狀態(tài)機(jī)，其確定性表現(xiàn)在狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)?。?）用轉(zhuǎn)換函數(shù)f（０，ａ）＝１，f（１，ａ）＝３f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３6（2）轉(zhuǎn)移矩陣70132aaaabbbb3（3）狀態(tài)轉(zhuǎn)換圖結(jié)點表示狀態(tài)，箭弧標(biāo)記為字母表中的字母輸入字符狀態(tài)ab012132213333終結(jié)狀態(tài)如何表示？8三DFAM接受的語言(字符串集)如果對所有ｗ∈Σ*，以下述方式遞歸地擴(kuò)充f的定義

f（ｑ，ε）＝ｑf(ｑ，ｗａ）＝f(f(ｑ，w），ａ）9對于上例中的DFAM和w=baa，

f(0，baa）=f(2,aa）=f(1,a）=30132aaaabbbb30b2a1a33該DFAM能夠識別字符串baa10從狀態(tài)轉(zhuǎn)換圖看，從初態(tài)出發(fā)，沿任一條路徑到達(dá)終結(jié)狀態(tài)，這條路徑上的弧上的標(biāo)記符號連接起來構(gòu)成的符號串為DFAM所識別。DFAM所能識別的符號串的全體記為L(M)，稱為DFAM所識別的語言。Ｌ（Ｍ）＝｛ｗ｜ｗ∈Σ*，若存在ｑ∈Z，使f（ｑ０，ｗ）＝ｑ｝11非確定的有限自動機(jī)（NFA）NondeterministicFiniteAutomata一.NFAm的定義

二.FA的等價定理三.具有-轉(zhuǎn)移的NFA構(gòu)造DFA的算法12非確定有限自動機(jī)M是一個五元組

M＝（Σ，S，S０，Z，f） 其中Σ，S，Z的意義和DFA的定義一樣，其中S０表示初始狀態(tài)集，f是一個從S×(Σ∪{})到S的子集的映射，即f：S×(Σ∪{})２S，其中２S是S的冪集，即S中所有子集組成的集合。一NFA的形式定義:確定的和非確定的有限自動機(jī)之間的重要區(qū)別是1、狀態(tài)轉(zhuǎn)換函數(shù)是一個多值映射；反映在狀態(tài)轉(zhuǎn)換圖上即對同一弧標(biāo)記到達(dá)的狀態(tài)結(jié)點不惟一。2、NFA初態(tài)集，而DFA是一個唯一的狀態(tài).NFA存在弧標(biāo)記130132ababbab314類似ＤFA，NFAm可用狀態(tài)轉(zhuǎn)換圖表示，如果f(ｑ，ａ）={ｑ1，ｑ2...，ｑk}，則從q出發(fā)分別向ｑ1，ｑ2...，ｑk各畫出一條標(biāo)記為a的箭弧(非確定的含義)。同理可定義NFAm所識別（接受）的語言。Σ*中所有可能被NFAm所識別的符號串的集合記為L(M)。NFAM’所識別的語言為:

L(M’)={α|f(q0,α)=qq∈Z}

15定理對任何一個NFAM，都存在一個

DFAM’，使L(M’)=L(M)構(gòu)造方法：用M’的一個狀態(tài)對應(yīng)M的多個狀態(tài)，用這種方法，能從一個NFAM構(gòu)造一個等價的DFAM’，稱作子集構(gòu)造法。二.FA的等價定理16定義

集合I的ε-閉包：令I(lǐng)是一個狀態(tài)集的子集，定義ε-closure（I）為：1）若s∈I，則s∈ε-closure（I）；2）若s∈I，則從s出發(fā)經(jīng)過任意條ε弧能夠到達(dá)的任何狀態(tài)都屬于ε-closure（I）。

狀態(tài)集ε-closure（I）稱為I的ε-閉包通過例子來說明狀態(tài)子集的ε-閉包的構(gòu)造方法三、具有-轉(zhuǎn)移的NFA構(gòu)造等價DFA的方法17例：如圖所示的狀態(tài)轉(zhuǎn)換圖：令I(lǐng)={1}，求ε-closure（I）=？156432aεεaε根據(jù)定義：ε-closure（I）={1，3，5}18構(gòu)造等價DFA算法若t1是NFA的初態(tài)，DFA的初態(tài)A=—closure({t1})。對NFA中每一個箭弧標(biāo)記m，計算—closure(f(q,m))，其中q為已生成的DFA狀態(tài)。遍歷字母表的每個字符為輸入例如字母表為{a,b}

B=—closure(f(A,a))

C=—closure(f(A,b))

如果B和C不為空集，重復(fù)這一過程，直到不在出現(xiàn)新的狀態(tài)集合）D=—closure(f(B,a))

E=—closure(f(B,b))F=—closure(f(C,a))

G=—closure(f(C,b))……注意:D,E,F,G中相等的集合合并,空集則舍去.19

—closure

(f(A，a))的含義NFA中從集合A中的狀態(tài)出發(fā)，先經(jīng)若干箭弧，接著經(jīng)標(biāo)記為a的箭弧到達(dá)的狀態(tài)集合的—closure。014236578910aabbb0124A={0,1,2,4,7}a3a861247B={3,8,6,1,2,4,7}aC={5,1,2,4,6,7}從NFA出發(fā)構(gòu)造DFAb7b567124abab20statesabB={3,8,6,1,2,4,7}A={0,1,2,4,7}BC={5,6,1,2,4,7}CBD={5,9,6,1,2,4,7}DBCBE={5,10,6,1,2,4,7}EBC等價DFA的轉(zhuǎn)移矩陣21等價的DFA的狀態(tài)轉(zhuǎn)換圖ABDstartabbCbbbaaaaE

注意：包含原初始狀態(tài)0的狀態(tài)子集A為DFAM的初態(tài)包含原終止?fàn)顟B(tài)10的狀態(tài)子集E為DFAM的終態(tài)。22例：有NFAM’

A=ε-closure({1})={1,4}a1234startabaccεB=ε-closure(f(A,a))=ε-closure(f({1,4},a))=ε-closure(f(1,a)∪f(4,a))=ε-closure({2,3}∪φ）=ε-closure({2,3})={2,3}C=ε-closure(f(A,b))=ε-closure(f(1,b)∪f(4,b))=ε-closure(φ）=φD=ε-closure(f(A,c))=ε-closure(f(1,c)∪f(4,c))=φE=ε-closure(f(B,a))F=ε-closure(f(B,b))G=ε-closure(f(B,c))……B=ε-closure(f(A,a))C=ε-closure(f(A,b))D=ε-closure(f(A,c))……23DFAM的狀態(tài)圖：ABDCEstart{1,4}{2,3}{4}{2}acabbc

注意：包含原初始狀態(tài)1的狀態(tài)子集為DFAM的初態(tài)包含原終止?fàn)顟B(tài)4的狀態(tài)子集為DFAM的終態(tài)。{3,4}a24具有-轉(zhuǎn)移的NFA構(gòu)造等價DFA的方法不具有-轉(zhuǎn)移的NFA如何構(gòu)造等價DFA？25例NFAM=(0,1,q0,q1,q0,{q1,

f),其中

f(q0,0)=q0,q1,f(q0,1)=q1f(q1,0)=f(q1,1)=q0,q1q0q0q100111start26q0q0q100111startf({q0}

,0)=q0,q1, f({q0},1)=q1f({q1},0)=, f({q1},0)=q0,q1f(q0,q1,0)=(q0,0)∪(q1

,0)=q0,q1f(q0,q1,1)=(q0,1)∪(q1

,1)=q0,q127M與M’的狀態(tài)轉(zhuǎn)換圖如下所示：q0q0q100111start{q0}q0q0{q1}{q0,q1}0110,1start28確定有限自動機(jī)的化簡所謂一個DFAM=(,S,S0,Z,f)的化簡是指尋找一個狀態(tài)數(shù)比較少的DFAM’,使

L(M)=L(M’)。而且可以證明，存在一個最少狀態(tài)的DFAM’,使L(M)=L(M’)。自動機(jī)是描述信息處理過程的—種數(shù)學(xué)模型對一種語言，它可以用許多文法來描述，同樣可以有無限多個FA來描述一種語言；這些FA是等價的，但其構(gòu)成的復(fù)雜程度差別很大29一個DFAm是最小化的

它沒有多余狀態(tài)并且沒有互相等價的狀態(tài)。一個DFAm可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的DFAm’30一、有限自動機(jī)的多余狀態(tài)（無關(guān)狀態(tài)）（1）從該自動機(jī)的開始狀態(tài)出發(fā),任何輸入串也不能到達(dá)的那個狀態(tài)（2）從該狀態(tài)出發(fā)沒有通向終態(tài)結(jié)的道路1011startq04231111startq042300

這些多余狀態(tài)不在從初態(tài)到終態(tài)的路徑上，對識別句子無任何作用。為什么？

31二、等價狀態(tài)的定義設(shè)p,qS

，若對任何w*

,f(p,w)與f(q,w)同時到達(dá)終止?fàn)顟B(tài)或拒絕狀態(tài)之中，則稱p和q是等價的。否則，稱p和q不等價（可區(qū)別）。

判定兩個狀態(tài)p和q不等價，只要找到一個w*，使f（p,w)Z且f（q,w)Z，或者相反。32說明（a）終結(jié)狀態(tài)與非終結(jié)狀態(tài)不等價。（b）對于a，f（p,a)=r,f（q,a)=s,r與s均等價，則p與q等價;若存在某個a，f（p,a)=r,f（q,a)=s其中r與s不等價,則p與q不等價。

設(shè)p表示非終結(jié)狀態(tài)，q表示終結(jié)狀態(tài)，

*，使f（p,)=pZ且f（q,)=qZr與s不等價,存在w*f（r,w)Z且f（s,w)Zf（p,aw)Z且f（q,aw)Z33分割法：把一個DFA(不含多余狀態(tài))的狀態(tài)分割成一些不相關(guān)的子集，使得任何不同的兩個子集狀態(tài)都是可區(qū)別的，而同一個子集中的任何狀態(tài)都是等價的.在各個子集中任取一個狀態(tài)做代表，刪去子集的其余狀態(tài)。一個DFAm可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的DFAm’34例:最小化5724361srartaaaaaaabbbbbbb分割法（劃分法）具體實現(xiàn)：有沒有多余狀態(tài)？35123456637315467374142ab子集號整理12345663731546737414212ab子集號終結(jié)狀態(tài)與非終結(jié)狀態(tài)不等價36123456637315467374142ab1243子集號1243123456637315467374142ab5子集號123456637315467374142ab123子集號37用子集號代替狀態(tài)號得:12345ab5214355231155243aaaaabbbbb38化簡以下DFAq8q7q6q5q1q2q311110111000000q401q8q7q6q5q1q2q31111011100000039區(qū)分終態(tài)與非終態(tài)整理1256726738637375131201子集號8731562627386373775131201子集號873401526273866373775131301子集號87321526273866373775131301子集號87324541用子集號代替狀態(tài)號得:1234501342125521553124011101001042NFADFA最小化化簡過程43課堂練習(xí)1.匯編程序是對（

）A.機(jī)器語言的執(zhí)行

B.匯編語言的翻譯C.高級語言的翻譯

D.高級語言程序的解釋執(zhí)行2.編譯程序是對（

）A.機(jī)器語言的執(zhí)行

B.匯編語言的翻譯C.高級語言的翻譯

D.高級語言程序的解釋執(zhí)行443.對編譯過程中的各階段進(jìn)行組合的目的是（

）A.便于編程實現(xiàn)

B.提高執(zhí)行效率

C.增加遍數(shù)

D.便于移植4.對于文法G，僅含終結(jié)符號的句型稱為（

）A.最左短語

B.句子

C.最左素短浯

D.語法樹455.一個上下文無關(guān)文法所含四個組成部分是（

）A.一個開始狀態(tài)，一組終結(jié)狀態(tài)、一個符號集、一組產(chǎn)生式B.一組終結(jié)符號，一組非終結(jié)符號、一個開始符號、一組產(chǎn)生