形式語言與自動機理論-第四章(蔣宗禮)課件

形式語言與自動機理論

FormalLanguagesandAutomataTheory蔣宗禮形式語言與自動機理論

FormalLanguagesan1課程目的和基本要求課程性質(zhì)技術(shù)基礎(chǔ)

基礎(chǔ)知識要求

數(shù)學(xué)分析（或者高等數(shù)學(xué)），離散數(shù)學(xué)

主要特點

抽象和形式化

理論證明和構(gòu)造性

基本模型的建立與性質(zhì)

課程目的和基本要求課程性質(zhì)2課程目的和基本要求本專業(yè)人員4種基本的專業(yè)能力計算思維能力算法的設(shè)計與分析能力程序設(shè)計和實現(xiàn)能力計算機軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計與應(yīng)用能力計算思維能力邏輯思維能力和抽象思維能力構(gòu)造模型對問題進行形式化描述理解和處理形式模型課程目的和基本要求本專業(yè)人員4種基本的專業(yè)能力3課程目的和基本要求

知識掌握正則語言、下文無關(guān)語言的文法、識別模型及其基本性質(zhì)、圖靈機的基本知識。能力培養(yǎng)學(xué)生的形式化描述和抽象思維能力。使學(xué)生了解和初步掌握“問題、形式化描述、自動化（計算機化）”這一最典型的計算機問題求解思路。課程目的和基本要求知識4主要內(nèi)容

語言的文法描述。RLRG、FA、RE、RL的性質(zhì)。CFLCFG(CNF、GNF)、PDA、CFL的性質(zhì)。

TM基本TM、構(gòu)造技術(shù)、TM的修改。CSLCSG、LBA。主要內(nèi)容語言的文法描述。5教材及主要參考書目蔣宗禮，姜守旭.形式語言與自動機理論.北京：清華大學(xué)出版社，2003年

JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,2001JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979教材及主要參考書目蔣宗禮，姜守旭.形式語言與自動機理論.6第4章正則表達式正則文法擅長語言的產(chǎn)生，有窮狀態(tài)自動機擅長語言的識別。本章討論正則語言的正則表達式描述。它在對正則語言的表達上具有特殊的優(yōu)勢，為正則語言的計算機處理提供了方便條件。簡潔、更接近語言的集合表示和語言的計算機表示等。第4章正則表達式正則文法擅長語言的產(chǎn)生，有窮狀態(tài)自動7第4章正則表達式主要內(nèi)容典型RE的構(gòu)造。與RE等價FA的構(gòu)造方法。與DFA等價的RE的構(gòu)造。重點RE的概念。RE與DFA的等價性。難點：RE與DFA的等價性證明。

第4章正則表達式主要內(nèi)容84.１啟示產(chǎn)生語言{anbmck|n，m，k≥1}∪{aicnbxam|i≥0,n≥1,m≥2,x為d和e組成的串}

的正則文法為AaA|aB|cEBbB|bCCcC|cEcE|bFFdF|eF|aHHaH|a4.１啟示產(chǎn)生語言{anbmck|n，m，k≥1}∪94.１啟示

接受此語言的NFAM

4.１啟示接受此語言的NFAM104.１啟示

計算集合set(q)set(A)={an|n≥0}={a}*

set(B)=set(A){a}{bn|n≥0} ={anabm|m，n≥0} ={a}*{a}*={a}+*set(C)=set(B){c}* ={a}*{a}*{c}*={a}++{c}*set(D)=set(C){c}={a}++{c}*{c} ={a}++{c}+4.１啟示計算集合set(q)114.１啟示

set(E)=set(A){c}{c}*

={a}*{c}{c}*={a}*{c}+set(F)=set(E){d，e}*={a}*{c}+{d，e}*set(H)=set(F){a}{a}*={a}*{c}+{d，e}*{a}{a}*

={a}*{c}+{d，e}*{a}+set(I)=set(H){a}={a}*{c}+{d，e}*{a}+{a}L(M)=set(D)∪set(H) ={a}++{c}+∪{a}*{c}+{d，e}*{a}+{a}4.１啟示set(E)=set(A){c}{c}*124.１啟示

根據(jù)集合運算的定義，{d，e}=kptmiyb∪{e}。從而， {d，e}*=(fvedrnm∪{e})*。這樣可以將L(M)寫成如下形式： L(M)={a}++{c}+∪{a}*{c}+(aoungvk∪{e})*{a}+{a}

記作： a+b+c++a*c+(d+e)*a+a=aa*bb*cc*+a*cc*(d+e)*aaa*

4.１啟示根據(jù)集合運算的定義，134.2RE的形式定義正則表達式(regularexpression，RE)⑴Φ是∑上的RE，它表示語言Φ；⑵ε是∑上的RE，它表示語言{ε}；⑶對于a∈∑，a是∑上的RE，它表示語言{a}；4.2RE的形式定義正則表達式(regularexpr144.2RE的形式定義

⑷如果r和s分別是∑上表示語言R和S的RE，則：r與s的“和”(r+s)是∑上的RE，(r+s)表達的語言為R∪S；r與s的“乘積”(rs)是∑上的RE，(rs)表達的語言為RS；r的克林閉包(r*)是∑上的RE，(r*)表達的語言為R*。⑸只有滿足⑴、⑵、⑶、⑷的才是∑上的RE。4.2RE的形式定義⑷如果r和s分別是∑上表示語言R和154.2RE的形式定義

例4-1設(shè)∑={0，1}⑴0，表示語言{0}；⑵1，表示語言{1}；⑶(0+1)，表示語言{0，1}；⑷(01)，表示語言{01}；⑸((0+1)*)，表示語言{0，1}*；⑹((00)((00)*))，表示語言{00}{00}*；4.2RE的形式定義例4-1設(shè)∑={0，1}164.2RE的形式定義

⑺((((0+1)*)(0+1))((0+1)*))，表示語言{0，1}+；

⑻((((0+1)*)000)((0+1)*))，表示{0，1}上的至少含有3個連續(xù)0的串組成的語言；⑼((((0+1)*)0)1)，表示所有以01結(jié)尾的0、1字符串組成的語言；⑽(1(((0+1)*)0))，表示所有以1開頭，并且以0結(jié)尾的0、1字符串組成的語言。

4.2RE的形式定義⑺((((0+1)*)(0+1))174.2RE的形式定義

約定

⑴r的正閉包r+表示r與(r*)的乘積以及(r*)與r的乘積：r+=(r(r*))=((r*)r)⑵閉包運算的優(yōu)先級最高，乘運算的優(yōu)先級次之，加運算“+”的優(yōu)先級最低。所以，在意義明確時，可以省略其中某些括號。

((((0+1)*)000)((0+1)*))=(0+1)*000(0+1)*

4.2RE的形式定義約定184.2RE的形式定義

((((0+1)*)(0+1))((0+1)*))=(0+1)*(0+1)(0+1)*

⑶在意義明確時，REr表示的語言記為L(r)，也可以直接地記為r。⑷加、乘、閉包運算均執(zhí)行左結(jié)合規(guī)則。4.2RE的形式定義((((0+1)*)(0+1))((194.2RE的形式定義相等(equivalence)r、s是字母表∑上的一個RE，如果L(r)=L(s)，則稱r與s相等，記作r=s。相等也稱為等價。幾個基本結(jié)論⑴

結(jié)合律：(rs)t=r(st) (r+s)+t=r+(s+t)⑵

分配律：r(s+t)=rs+rt (s+t)r=sr+tr4.2RE的形式定義相等(equivalence)204.2RE的形式定義⑶

交換律： r+s=s+r。⑷

冪等律： r+r=r。⑸

加法運算零元素：r+Φ=r。⑹

乘法運算單位元：rε=εr=r。⑺

乘法運算零元素：rΦ=Φr=Φ。⑻L(Φ)=Φ。⑼L(ε)={ε}。⑽L(a)={a}。4.2RE的形式定義⑶交換律： r+s=s+r。214.2RE的形式定義⑾L(rs)=L(r)L(s)。⑿L(r+s)=L(r)∪L(s)。⒀L(r*)=(L(r))*。⒁L(Φ*)={ε}。⒂L((r+ε)*)=L(r*)。⒃L((r*)*)=L(r*)。⒄L((r*s*)*)=L((r+s)*)。⒅

如果L(r)L(s)，則r+s=s。4.2RE的形式定義⑾L(rs)=L(r)L(s)。224.2RE的形式定義⒆L(rn)=(L(r))n。⒇rnrm=rn+m。一般地，r+ε≠r，(rs)n

≠rnsn，rs≠sr。冪

r是字母表∑上的RE，r的n次冪定義為

⑴r0=ε。⑵rn=rn-1r。4.2RE的形式定義⒆L(rn)=(L(r))n。234.2RE的形式定義例4-2

設(shè)∑={0，1}00表示語言{00}；(0+1)*00(0+1)*表示所有的至少含兩個連續(xù)0的0、1串組成的語言；(0+1)*1(0+1)9表示所有的倒數(shù)第10個字符為1的串組成的語言；4.2RE的形式定義例4-2設(shè)∑={0，1}244.2RE的形式定義L((0+1)*011)={x|x是以011結(jié)尾的0、1串}；L(0+1+2+)={0n1m2k|m，n，k≥1}；L(0*1*2*)={0n1m2k|m，n，k≥0}；L(1(0+1)*1+0(0+1)*0))={x|x的開頭字符與尾字符相同}。4.2RE的形式定義L((0+1)*011)={x|x是以254.3RE與FA等價正則表達式r稱為與FAM等價，如果L(r)=L(M)。從開始狀態(tài)出發(fā)，根據(jù)狀態(tài)之間按照轉(zhuǎn)移所確定的后繼關(guān)系，依次計算出所給FA的各個狀態(tài)q對應(yīng)的set(q)，并且最終得到相應(yīng)的FA接受的語言的RE表示。尋找一種比較“機械”的方法，使得計算機系統(tǒng)能夠自動完成FA與RE之間的轉(zhuǎn)換。4.3RE與FA等價正則表達式r稱為與FAM等價，如果264.3.1RE到FA的等價變換0對應(yīng)的FA01對應(yīng)的FA4.3.1RE到FA的等價變換0對應(yīng)的FA01對應(yīng)的FA274.3.1RE到FA的等價變換0+1對應(yīng)的FA4.3.1RE到FA的等價變換0+1對應(yīng)的FA284.3.1RE到FA的等價變換0*對應(yīng)的FA4.3.1RE到FA的等價變換0*對應(yīng)的FA294.3.1RE到FA的等價變換定理4-1

RE表示的語言是RL。證明：施歸納于正則表達式中所含的運算符的個數(shù)n，證明對于字母表∑上的任意正則表達式r，存在FAM，使得L(M)=L(r)。M恰有一個終止?fàn)顟B(tài)。M在終止?fàn)顟B(tài)下不作任何移動。

4.3.1RE到FA的等價變換定理4-1RE表示的語304.3.1RE到FA的等價變換n=0

r=εr=Φ

r=a

4.3.1RE到FA的等價變換n=0r=εr=Φr314.3.1RE到FA的等價變換設(shè)結(jié)論對于n=k時成立，此時有如下FA：M1=(Q1，∑，δ1，q01，{f1})M2=(Q2，∑，δ2，q02，{f2})L(M1)=L(r1)，L(M2)=L(r2)。Q1∩Q2=Φ。

n=k4.3.1RE到FA的等價變換設(shè)結(jié)論對于n=k時成立，此324.3.1RE到FA的等價變換n=k+1

r=r1+r2取q0，fQ1∪Q2，令 M=(Q1∪Q2∪{q0，f}，∑，δ，q0，{f})①δ(q0，ε)={q01，q02}；②對q∈Q1，a∈∑∪{ε}，δ(q，a)=δ1(q，a);對q∈Q2，a∈∑∪{ε}，δ(q，a)=δ2(q，a)；③δ(f1，ε)={f}；④δ(f2，ε)={f}。4.3.1RE到FA的等價變換n=k+1r=r1+r2334.3.1RE到FA的等價變換n=k+1

r=r1+r2

4.3.1RE到FA的等價變換n=k+1r=r1+r2344.3.1RE到FA的等價變換M=(Q1∪Q2，∑，δ，q01，{f2})

①

對q∈Q1-{f1}，a∈∑∪{ε}δ(q，a)=δ1(q，a)；②

對q∈Q2-{f2}，a∈∑∪{ε}δ(q，a)=δ2(q，a)；③δ(f1，ε)={q02}4.3.1RE到FA的等價變換M=(Q1∪Q2，∑，δ，354.3.1RE到FA的等價變換r=r1r2

4.3.1RE到FA的等價變換r=r1r2364.3.1RE到FA的等價變換M=(Q1∪{q0，f}，∑，δ，q0，{f})其中q0，fQ1，定義δ為①

對q∈Q1-{f1}，a∈∑， δ(q，a)=δ1(q，a)。②

δ(f1，ε)={q01，f}。③δ(q0，ε)={q01，f}。4.3.1RE到FA的等價變換M=(Q1∪{q0，f}，374.3.1RE到FA的等價變換r=r1*

4.3.1RE到FA的等價變換r=r1*384.3.1RE到FA的等價變換按照定理4-1證明給出的方法構(gòu)造一個給定RE的等價FA時，該FA有可能含有許多的空移動?？梢园凑兆约簩o定RE的“理解”以及對FA的“理解”“直接地”構(gòu)造出一個比較“簡單”的FA。定理證明中所給的方法是機械的。由于“直接地”構(gòu)造出的FA的正確性依賴于構(gòu)造者的“理解”，所以它的正確性缺乏有力的保證。

4.3.1RE到FA的等價變換按照定理4-1證明給出的方394.3.1RE到FA的等價變換例4-3

構(gòu)造與(0+1)*0+(00)*等價的FA。

4.3.1RE到FA的等價變換例4-3構(gòu)造與(0404.3.1RE到FA的等價變換按照對(0+1)*0+(00)*的“理解”“直接地”構(gòu)造出的FA。4.3.1RE到FA的等價變換按照對(0+1)*0+(00414.3.2RL可以用RE表示計算DFA的每個狀態(tài)對應(yīng)的集合——字母表的克林閉包的等價分類，是具有啟發(fā)意義的。

這個計算過程難以“機械”地進行。

計算q1到q2的一類串的集合：Rkij。圖上作業(yè)法。4.3.2RL可以用RE表示計算DFA的每個狀態(tài)對應(yīng)的集424.3.2RL可以用RE表示定理4-2RL可以用RE表示。設(shè)DFAM=({q1，q2，…，qn}，∑，δ，q1，F(xiàn))Rkij={x|δ(qi，x)=qj而且對于x的任意前綴y(y≠x，y≠ε)，如果δ(qi，y)=ql，則l≤k}。4.3.2RL可以用RE表示定理4-2RL可以用RE表434.3.2RL可以用RE表示R0ij=

{a|δ(qi，a)=qj} 如果i≠j

{a|δ(qi，a)=qj}∪{ε} 如果i=jRkij=Rk-1ik(Rk-1kk)*Rk-1kjRk-1ij

4.3.2RL可以用RE表示R0ij={a|δ(qi，a444.3.2RL可以用RE表示圖上作業(yè)法

啟示4.3.2RL可以用RE表示圖上作業(yè)法454.3.2RL可以用RE表示圖上作業(yè)法操作步驟⑴預(yù)處理：①用標(biāo)記為X和Y的狀態(tài)將M“括起來”：在狀態(tài)轉(zhuǎn)移圖中增加標(biāo)記為X和Y的狀態(tài)，從標(biāo)記為X的狀態(tài)到標(biāo)記為q0的狀態(tài)引一條標(biāo)記為ε的?。粡臉?biāo)記為q(q∈F)的狀態(tài)到標(biāo)記為Y的狀態(tài)分別引一條標(biāo)記為ε的弧。②

去掉所有的不可達狀態(tài)。4.3.2RL可以用RE表示圖上作業(yè)法操作步驟464.3.2RL可以用RE表示⑵

對通過步驟(1)處理所得到的狀態(tài)轉(zhuǎn)移圖重復(fù)如下操作，直到該圖中不再包含除了標(biāo)記為X和Y外的其他狀態(tài)，并且這兩個狀態(tài)之間最多只有一條弧。

并弧

將從q到p的標(biāo)記為r1，r2，…，rg并行弧用從q到p的、標(biāo)記為r1+r2+…+rg的弧取代這g個并行弧。

4.3.2RL可以用RE表示⑵對通過步驟(1)處理所得到474.3.2RL可以用RE表示去狀態(tài)1如果從q到p有一條標(biāo)記為r1的弧，從p到t有一條標(biāo)記為r2的弧，不存在從狀態(tài)p到狀態(tài)p的弧，將狀態(tài)p和與之關(guān)聯(lián)的這兩條弧去掉，用一條從q到t的標(biāo)記為r1r2的弧代替。去狀態(tài)2如果從q到p有一條標(biāo)記為r1的弧，從p到t有一條標(biāo)記為r2的弧，從狀態(tài)p到狀態(tài)p標(biāo)記為r3的弧，將狀態(tài)p和與之關(guān)聯(lián)的這三條弧去掉，用一條從q到t的標(biāo)記為r1r3*r2的弧代替。4.3.2RL可以用RE表示去狀態(tài)1484.3.2RL可以用RE表示去狀態(tài)3如果圖中只有三個狀態(tài)，而且不存在從標(biāo)記為X的狀態(tài)到達標(biāo)記為Y的狀態(tài)的路，則將除標(biāo)記為X的狀態(tài)和標(biāo)記為Y的狀態(tài)之外的第3個狀態(tài)及其相關(guān)的弧全部刪除。

4.3.2RL可以用RE表示去狀態(tài)3494.3.2RL可以用RE表示⑶

從標(biāo)記為X的狀態(tài)到標(biāo)記為Y的狀態(tài)的弧的標(biāo)記為所求的正則表達式。如果此弧不存在，則所求的正則表達式為Φ。

4.3.2RL可以用RE表示⑶從標(biāo)記為X的狀態(tài)到標(biāo)記為Y504.3.2RL可以用RE表示例4-4

求圖4-14所示的DFA等價的RE。4.3.2RL可以用RE表示例4-4求圖4-14所示514.3.2RL可以用RE表示預(yù)處理。4.3.2RL可以用RE表示預(yù)處理。524.3.2RL可以用RE表示去掉狀態(tài)q3。4.3.2RL可以用RE表示去掉狀態(tài)q3。534.3.2RL可以用RE表示去掉狀態(tài)q4。4.3.2RL可以用RE表示去掉狀態(tài)q4。544.3.2RL可以用RE表示合并從標(biāo)記為q2的狀態(tài)到標(biāo)記為Y的狀態(tài)的兩條并行弧。

4.3.2RL可以用RE表示合并從標(biāo)記為q2的狀態(tài)到標(biāo)記為554.3.2RL可以用RE表示去掉狀態(tài)q0。4.3.2RL可以用RE表示去掉狀態(tài)q0。564.3.2RL可以用RE表示并弧。

4.3.2RL可以用RE表示并弧。574.3.2RL可以用RE表示去掉狀態(tài)q1。4.3.2RL可以用RE表示去掉狀態(tài)q1。584.3.2RL可以用RE表示去掉狀態(tài)q2。1*0(11*0)*0((00*111*0+00*10+11*0)(11*0)*0)(00*