形式語言與自動機(jī)理論(一)

形式語言與自動機(jī)理論2010年3月1參考教材1、形式語言與自動機(jī)理論

作者：蔣宗禮、姜守旭

出版社：清華大學(xué)出版社

2、AnIntroductiontoFormalLanguagesandAutomata(ThirdEdition)

作者：PeterLinz出版社：機(jī)械工業(yè)出版社3、IntroductiontoAutomataTheory,Languages,andComputation(SecondEdition)

作者：JohnE.Hopcroft,RajeevMotwani,JeffreyD.Ullman出版社：清華大學(xué)出版社2第一章緒論計算機(jī)科學(xué)研究的課題是：可計算性；算法和復(fù)雜性理論；數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫；人工智能；人機(jī)交互和人機(jī)界面。

3第一章緒論計算機(jī)科學(xué)理論計算機(jī)科學(xué)①自動機(jī)論與形式語言理論；②程序理論（包括程序正確性證明、程序驗(yàn)證等）；③形式語義學(xué)；④算法分析和計算復(fù)雜性理論。實(shí)驗(yàn)計算機(jī)科學(xué)4第一章緒論1.4語言1.4.1語言的非形式和形式定義Webster定義：為相當(dāng)大的團(tuán)體的人所懂得,并使的字和組合這些字的方法的統(tǒng)一體。5第一章緒論1.4語言1.4.1語言的非形式和形式定義吳天蔚定義：語言可以被看成一個抽象的數(shù)學(xué)系統(tǒng)。（1994）(信息產(chǎn)業(yè)部計算機(jī)與微電子發(fā)展研究中心)Chomsky定義：按照一定規(guī)律構(gòu)成的句子和符號串的有限或無限的集合。6第一章緒論1.4語言1.4.2形式語言和自動機(jī)理論的產(chǎn)生和作用

（1）產(chǎn)生過程

形式語言的產(chǎn)生過程

自動機(jī)的產(chǎn)生過程（2）作用7第一章緒論1.4語言1.4.3基本概念形式語言的直觀意義形式語言是用來精確描述語言（包括人工語言和自然語言）及其結(jié)構(gòu)的手段。形式語言學(xué)也稱代數(shù)語言學(xué)。8第一章緒論1.4語言1.4.3基本概念對語言研究的主要方面：（2）有窮描述（1）表示（3）語言的結(jié)構(gòu)9第一章緒論語言描述的三種途徑：（1）窮舉法：只適合句子數(shù)目有效的語言。（2）語法描述：生成語言中合格的句子。（3）自動機(jī)：對輸入的句子進(jìn)行檢驗(yàn)，區(qū)別哪些是語言中的句子，哪些不是語言中的句子。1.4語言1.4.3基本概念10第一章緒論1.4語言1.4.3基本概念（1）符號（2）字母表（3）字符串（4）語言字母表的運(yùn)算①乘積運(yùn)算②冪運(yùn)算③閉包運(yùn)算11第二章文法2.1文法的引入例1漢語中的句子：王平和李新是大學(xué)生。它由兩個短語組成：〈主語〉 〈謂語〉王平和李新 是大學(xué)生

該句子可以應(yīng)用下列規(guī)則構(gòu)成：12第二章文法1．〈句子〉→〈主語〉〈謂語〉2．〈主語〉→〈名詞短語〉3．〈名詞短語〉→〈名詞〉4．〈名詞短語〉→〈名詞〉〈連接詞〉〈名詞短語〉5.〈名詞〉→王平6.〈名詞〉→李新7.〈連詞〉→和8.〈謂語〉→〈動賓短語〉9．〈動賓短語〉→〈動詞〉〈賓語〉10.〈動詞〉→是11.〈賓語〉→〈名詞〉12.〈名詞〉→大學(xué)生

13第二章文法該文法也能產(chǎn)生:王平是大學(xué)生；李新和王平是大學(xué)生；王平和大學(xué)生是李新；王平和王平和王平是王平等句子。

14第二章文法2.2文法的形式定義2.2.1定義

文法G是一個4元組G=(V,T,P,S)

其中：（1）V是非終結(jié)符非空有限集合；（2）T是終結(jié)符的非空有限集合；

并且V?T=F；（3）P是產(chǎn)生式的非空有限集合；（4）S?V是文法G的開始符。15第二章文法2.2文法的形式定義2.2.2推導(dǎo)和歸約定義：假設(shè)G=(V,T,P,S)是一個文法。如果a?bP,并且,(VT）*，則稱a直接推導(dǎo)出b，記為：ab

如果ab，則稱b在文法G中直接歸約成a，簡稱為歸約。16第二章文法2.2文法的形式定義2.2.3語言定義：設(shè)文法G=(V,T,P,S)。對(VT)*，如果S()*,

則為文法G的一個句型；若對wT*，如果S()*w，則w

稱為由G產(chǎn)生的一個句子。稱L(G)={w|wT*,

S()*w}為文法G產(chǎn)生的語言。17第二章文法2.3文法的構(gòu)造例1：構(gòu)造文法G，使

L(G)={0,1,00,11}定義：假設(shè)G1,G2是文法，如果

L(G1)=L(G2)，則稱G1,G2是等價的。18第二章文法2.3文法的構(gòu)造例2：構(gòu)造文法G，使(1)L(G)={0n|n0}(2)L(G)={0n|n1}(3)L(G)={0n1n|n0}(4)L(G)={0n1n|n1}(5)L(G)={0n1n+1|n0}(6)L(G)={0n1n2n|n1}19第二章文法2.4文法的類型2.4.1Chomsky體系(1)0型文法(短語結(jié)構(gòu)文法)

對產(chǎn)生式不做任何限制PSG(phrasestructuregrammar)PSL(phrasestructurelanguage)

RE(recursivelyenumerable

)20第二章文法2.4文法的類型2.4.1Chomsky體系(2)1型文法（上下文有關(guān)文法）

對P,都有||||CSG(contextsensitivegrammar)CSL(contextsensitivelanguage)21第二章文法2.4文法的類型2.4.1Chomsky體系(3)2型文法（上下文無關(guān)文法）

對P,都有||||，并且VCFG(contextfreegrammar)CFL(contextfreelanguage)22第二章文法2.4文法的類型2.4.1Chomsky體系(4)3型文法（正規(guī)文法、正則文法）

對P,有以下形式：AwB,AworABw,Aw

其中A,BV,wT+

RG(regulargrammar)RL(regularlanguage)23第二章文法2.4文法的類型2.4.2正規(guī)文法和正規(guī)語言定理：L是RL的充分必要條件是存在一個文法，該文法產(chǎn)生語言L,并且產(chǎn)生式的形式是：AaB,AaorABa,Aa其中A,BV,aT.

24第二章文法2.4文法的類型2.5空語句定義：假設(shè)G=(V,T,P,S)是一個文法。如果S不出現(xiàn)在G的任何產(chǎn)生式的右部，則P{S}所形成的文法仍然是與G等價的相應(yīng)類型的文法，所產(chǎn)生的語言是相應(yīng)類型的語言。25第三章有限狀態(tài)自動機(jī)3.1有限狀態(tài)系統(tǒng)3.2有限狀態(tài)自動機(jī)的形式定義（１）形式定義定義：有限狀態(tài)自動機(jī)（finiteautomaton,FA）是一個五元組：Ｍ=(Q,,,q0,F)其中，Q：非空有限狀態(tài)集合；

：有限輸入字母表；

：狀態(tài)轉(zhuǎn)換函數(shù)；：QQ；（DFA）q0：q0Q,是Ｍ的初始狀態(tài)；

F：FQ是Ｍ的終止?fàn)顟B(tài)集。26第三章有限狀態(tài)自動機(jī)3.1有限狀態(tài)系統(tǒng)3.2有限狀態(tài)自動機(jī)的形式定義例如：假設(shè)DFAM=(Q,,,q0,F)。其中Q={q0,q1,q2,q3}，={a,b}，F(xiàn)={q3}27第三章有限狀態(tài)自動機(jī)3.1有限狀態(tài)系統(tǒng)3.2有限狀態(tài)自動機(jī)的形式定義輸入字符串時，轉(zhuǎn)換函數(shù)為：其定義為：對(1)對，有(2)當(dāng)時，28第三章有限狀態(tài)自動機(jī)3.2有限狀態(tài)自動機(jī)的形式定義（２）設(shè)計有限狀態(tài)自動機(jī)例１：構(gòu)造一臺有限狀態(tài)自動機(jī)，它能夠識別所有由奇數(shù)個ａ和奇數(shù)個ｂ組成的字符串。

設(shè)計考慮有以下狀態(tài)：（1）到此為止讀入偶數(shù)個a和偶數(shù)個b;

（2）到此為止讀入奇數(shù)個a和偶數(shù)個b;

（3）到此為止讀入偶數(shù)個a和奇數(shù)個b;（4）到此為止讀入奇數(shù)個a和奇數(shù)個b;29例２：設(shè)計一臺有限狀態(tài)自動機(jī)，識別含有00作為子串的所有{0,1}上的字符串組成的語言。設(shè)計考慮以下狀態(tài)：（1）開始狀態(tài)，什么都沒有輸入或者輸入1；（2）接收到的符號是0；（3）接收到的符號是00；第三章有限狀態(tài)自動機(jī)3.2有限狀態(tài)自動機(jī)的形式定義（２）設(shè)計有限狀態(tài)自動機(jī)30第三章有限狀態(tài)自動機(jī)3.2有限狀態(tài)自動機(jī)的形式定義（２）設(shè)計有限狀態(tài)自動機(jī)例3：設(shè)計一個DFAM，它能識別所有能被3整除的十進(jìn)制數(shù)。設(shè)計可以考慮有以下情況：（1）已輸入的數(shù)字與上一余數(shù)之和被3除余0；

（2）已輸入的數(shù)字與上一余數(shù)之和被3除余1；

（3）已輸入的數(shù)字與上一余數(shù)之和被3除余2；31第三章有限狀態(tài)自動機(jī)3.2有限狀態(tài)自動機(jī)的形式定義（3）即時描述（瞬時描述、格局）

定義：設(shè)M=(Q,,,q0,F)是一個FA,

x,y*,(q0,x)=q。則

xqy稱為M

的一個即時描述

(instantaneousdescription,ID)。32第三章有限狀態(tài)自動機(jī)3.2有限狀態(tài)自動機(jī)的形式定義（4）到達(dá)某狀態(tài)的字符串集合

定義：設(shè)FA

M=(Q,,,q0,F)，對qQ能從開始狀態(tài)到達(dá)所輸入的字符串集合為：

set(q)={x|x*,并且(q0,x)=q}33第三章有限狀態(tài)自動機(jī)3.2有限狀態(tài)自動機(jī)的形式定義（5）有限狀態(tài)自動機(jī)等價

假設(shè)M1,M2是FA，如果L(M1)=L(M2)，則M1與M2等價。34第三章有限狀態(tài)自動機(jī)3.3非確定的有限自動機(jī)(NFA)（1）形式定義

定義：非確定有限自動機(jī)（non-deterministicfiniteautomaton,NFA）是一個五元組：Ｍ=(Q,,,q0,F)其中，Q、、q0、F的定義與在FA中的定義相同；

：狀態(tài)轉(zhuǎn)換函數(shù)，：Qp(Q)

即對(q,a)Q

(q,a)={p1,p2,…,pm}Q35第三章有限狀態(tài)自動機(jī)3.3非確定的有限自動機(jī)(NFA)狀態(tài)轉(zhuǎn)換函數(shù)：Qp(Q)，對qQ①對*②對a,w*有③對PQ36第三章有限狀態(tài)自動機(jī)3.3非確定的有限自動機(jī)(NFA)（1）形式定義非確定的有限自動機(jī)(NFAM)所接受的語言:37第三章有限狀態(tài)自動機(jī)3.3非確定的有限自動機(jī)(NFA)例：設(shè)計一臺NFA，使它能夠接受0，1形成的字符串且該字符串的最后兩位是01。設(shè)計分析可以考慮以下情況：（1）在初始狀態(tài)下，無論輸入1還是輸入0都是一種不可接受的狀態(tài)；（2）在初始狀態(tài)下，輸入0時，是一種可能接受的狀態(tài)；（3）在可能接受的狀態(tài)下，輸入1時，是可接受的狀態(tài)。38第三章有限狀態(tài)自動機(jī)3.3非確定的有限自動機(jī)(NFA)（2）DFA和NFA的等價性

定理：設(shè)L(MN)是由NFAMN所接受的語言。則存在一個DFAMD，使得L(MD)=L(MN)。39第三章有限狀態(tài)自動機(jī)（1）形式定義3.4有轉(zhuǎn)換的有限狀態(tài)自動機(jī)(-NFA)

定義：有轉(zhuǎn)換的NFAM是一個五元組：Ｍ=(Q,,,q0,F)其中，Q、、q0、F的定義與NFA中的定義相同；

：狀態(tài)轉(zhuǎn)換函數(shù),：Q({})p(Q)

即對(q,a)Q({})

(q,a)={p1,p2,…,pm}Q40第三章有限狀態(tài)自動機(jī)3.4有轉(zhuǎn)換的有限狀態(tài)自動機(jī)(-NFA)（2）相關(guān)概念

閉包

假設(shè)有轉(zhuǎn)換的NFAＭ=(Q,,,q0,F)，對qQ,q的閉包是指由狀態(tài)q出發(fā)，經(jīng)過有限段弧到達(dá)的狀態(tài)以及q本身組成的狀態(tài)集合。記為-CLOSURE(q)。若PQ,那么-CLOSURE(P)=41第三章有限狀態(tài)自動機(jī)3.4有轉(zhuǎn)換的有限狀態(tài)自動機(jī)(-NFA)（2）相關(guān)概念

的定義對qQ,w*,a

①②其中：42第三章有限狀態(tài)自動機(jī)3.4有轉(zhuǎn)換的有限狀態(tài)自動機(jī)(-NFA)（2）相關(guān)概念

的定義

③對RQ

有轉(zhuǎn)換NFAM所接受的語言43第三章有限狀態(tài)自動機(jī)3.4有轉(zhuǎn)換的有限狀態(tài)自動機(jī)(-NFA)（3）-NFA與NFA的等價性

定理：如果-NFAM所接受的語言為L(M),那么存在一個NFAM1，使得L(M1)=L(M)44第三章有限狀態(tài)自動機(jī)3.5FA是正規(guī)語言的識別器由文法推導(dǎo)句子Sa1A1Sa1A1A1a2A2a1a2A2……..…………

An-2an-1An-1a1a2…an-1An-2

An-1ana1a2…an-1an自動機(jī)識別句子(q0,a1)=q1q0a1…an├a1q1a2…an(q1,a2)=q2├a1a2q2a3…an……..…………

(qn-1,an)=qn├a1a2a3…anqnqnF45第三章有限狀態(tài)自動機(jī)3.5FA是正規(guī)語言的識別器定理：FA接受的語言是正規(guī)語言思路：假設(shè)一臺DFAM,它所接受的語言是L(M),該語言能夠被正規(guī)文法推出。定理：正規(guī)語言能夠被FA所接受思路：假設(shè)L是由正規(guī)文法產(chǎn)生的語言,構(gòu)造一臺自動機(jī)FA能夠接受它。46第三章有限狀態(tài)自動機(jī)3.5FA是正規(guī)語言的識別器例1：假設(shè)RGG=({S,B},{0,1},P,S)

其中P={S0B,B0B|1S|0}

構(gòu)造一臺NFAM,使得L(M)=L(G)。例2：由例1的NFAM

構(gòu)造一臺DFAM1,使得

L(M1)=L(M)。例3：由例2的DFAM1

構(gòu)造一個RGG,使得

L(G)=L(M1)。47第三章有限狀態(tài)自動機(jī)3.6FA的一些變形(1)雙向有限自動機(jī)確定的雙向有限自動機(jī)（2DFA）2DFA是一個五元組Ｍ=(Q,,,q0,F)其中，Q,,q0,F的定義與DFA的定義一致

：QQ{L,R,S}48第三章有限狀態(tài)自動機(jī)3.6FA的一些變形(1)雙向有限自動機(jī)格局變化2DFA所接受的語言L(M)={w|w*,q0w├wp,pF}49第三章有限狀態(tài)自動機(jī)3.6FA的一些變形(2)帶輸出的有限自動機(jī)Moor機(jī)一個Moor機(jī)為六元組M=(Q,,,,,q0)其中，Q,,,q0的含義與DFA的一致。

：為有限輸出字母表

:為輸出函數(shù)Q50第三章有限狀態(tài)自動機(jī)3.6FA的一些變形Moor機(jī)例：用Moor機(jī)設(shè)計一臺模4往返計數(shù)器。

51第三章有限狀態(tài)自動機(jī)3.6FA的一些變形(2)帶輸出的有限自動機(jī)Mealy機(jī)一個Mealy機(jī)為六元組M=(Q,,,,,q0)其中，Q,,,,q0的含義與Moor機(jī)的一致。:為輸出函數(shù)Q

52第三章有限狀態(tài)自動機(jī)3.6FA的一些變形Mealy機(jī)例如：用Mealy機(jī)設(shè)計一臺奇偶校驗(yàn)器。

53第三章有限狀態(tài)自動機(jī)3.6FA的一些變形Moor機(jī)和Mealy機(jī)的等價性54第三章有限狀態(tài)自動機(jī)3.6FA的一些變形(2)帶輸出的有限自動機(jī)Moor機(jī)和Mealy機(jī)的等價性定義：設(shè)M=(Q,,,,,q0)為一個Moor機(jī)，M’=(Q’,,’,,’,q0)為一個Mealy機(jī)，且b=(q0),若對于w*,都有

TM(w)=bTM’(w)則稱Moor機(jī)與Mealy機(jī)等價，記為M~M’。55第三章有限狀態(tài)自動機(jī)3.6FA的一些變形(2)帶輸出的有限自動機(jī)定理：對每個Moor機(jī)M1=(Q,,,,,q0)都存在一個Mealy機(jī)M2,使得M2

~

M1.定理：對每個Mealy機(jī)M1=(Q,,,,,q0)都存在一個Moor機(jī)M2,使得M2

~

M1.56第三章有限狀態(tài)自動機(jī)例1：構(gòu)造與Moor機(jī)描述的模4往返計數(shù)器等價的Mealy機(jī)。57第三章有限狀態(tài)自動機(jī)例2：給定一臺Mealy機(jī)（如圖所示），構(gòu)造一臺與它等價的Moor機(jī)。

58第三章有限狀態(tài)自動機(jī)總結(jié)：概念：文法分類（0、1、2、3型文法）

自動機(jī)分類（DFANFA-NFA

2DFAMoorMealy）自動機(jī)之間、與文法之間的等價轉(zhuǎn)換Moor機(jī)Mealy機(jī)-NFANFADFARG2DFA59第四章正規(guī)表達(dá)式4.1正規(guī)表達(dá)式的形式定義定義：設(shè)是一個字母表，字母表上正規(guī)式（RegularExpression,RE）和正規(guī)集定義如下：（1）是上的正規(guī)式，對應(yīng)的正規(guī)集為；（2）是上的正規(guī)式，對應(yīng)的正規(guī)集為{}；（3）對a，a是上的正規(guī)式，對應(yīng)的正規(guī)集為{a}；60第四章正規(guī)表達(dá)式4.1正規(guī)表達(dá)式的形式定義（4）如果r和s分別是上的正規(guī)式，對應(yīng)的正規(guī)集為R和S。那么(r+s)為正規(guī)式，對應(yīng)的正規(guī)集為RS；(rs)為正規(guī)式，對應(yīng)的正規(guī)集為RS；(r*)為正規(guī)式，對應(yīng)的正規(guī)集為R*（5）只有滿足上述形式定義的表達(dá)式才是上的正規(guī)式，它所表達(dá)的語言是正規(guī)集。61第四章正規(guī)表達(dá)式4.1正規(guī)表達(dá)式的形式定義例如：假設(shè)={a,b}(1)((a+b)*)(2)(ab*)(3)(b(a+b)*)(4)((a+b)*((aa)+(bb))(a+b)*)(5)（((((a*)b)a*)b)a*）62第四章正規(guī)表達(dá)式正規(guī)表達(dá)式的運(yùn)算性質(zhì)假設(shè)r,s,t都是上正規(guī)式，則有以下性質(zhì)：（1）結(jié)合律；（2）分配律；（3）交換律；（4）冪等律；（5）加運(yùn)算單位元；（6）乘運(yùn)算單位元；（7）乘運(yùn)算零元；（8）(r*)*=r*；（9）r*=r++；（10）*=（11）*=4.1正規(guī)表達(dá)式的形式定義63第四章正規(guī)