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

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

FormalLanguagesandAutomataTheory蔣宗禮形式語言與自動機(jī)理論

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

基礎(chǔ)知識要求

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

主要特點

抽象和形式化

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

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

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

知識掌握正則語言、下文無關(guān)語言的文法、識別模型及其基本性質(zhì)、圖靈機(jī)的基本知識。能力培養(yǎng)學(xué)生的形式化描述和抽象思維能力。使學(xué)生了解和初步掌握“問題、形式化描述、自動化（計算機(jī)化）”這一最典型的計算機(jī)問題求解思路。課程目的和基本要求知識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教材及主要參考書目蔣宗禮，姜守旭.形式語言與自動機(jī)理論.北京：清華大學(xué)出版社，2003年

JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,2001JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979教材及主要參考書目蔣宗禮，姜守旭.形式語言與自動機(jī)理論.6第7章下推自動機(jī)PDA描述CFL，所以它應(yīng)該與CFG等價。PDA應(yīng)該包含F(xiàn)A的各個元素，或者包含那些可以取代FA的各個元素的功能的元素。

PDA按照最左派生的派生順序，處理處于當(dāng)前句型最左邊的變量，因此，需要采用棧作為其存儲機(jī)構(gòu)。按照FA的“習(xí)慣”，PDA用終態(tài)接受語言。模擬GNF的派生PDA用空棧接受語言。

第7章下推自動機(jī)PDA描述CFL，所以它應(yīng)該與CFG等價7第7章下推自動機(jī)主要內(nèi)容PDA的基本概念。PDA的構(gòu)造舉例。用終態(tài)接受語言和用空棧接受語言的等價性。PDA是CFL的接受器。重點PDA的基本定義及其構(gòu)造，PDA是CFL的等價描述。

難點根據(jù)PDA構(gòu)造CFG。第7章下推自動機(jī)主要內(nèi)容87.1基本定義PDA的物理模型7.1基本定義PDA的物理模型97.1基本定義PDA應(yīng)該含有三個基本結(jié)構(gòu)存放輸入符號串的輸入帶。存放文法符號的棧。有窮狀態(tài)控制器。PDA的動作在有窮狀態(tài)控制器的控制下根據(jù)它的當(dāng)前狀態(tài)、棧頂符號、以及輸入符號作出相應(yīng)的動作，在有的時候，不需要考慮輸入符號。

7.1基本定義PDA應(yīng)該含有三個基本結(jié)構(gòu)107.1基本定義下推自動機(jī)(pushdownautomaton，PDA)M=(Q，∑，Γ，δ，q0，Z0，F(xiàn))Q——狀態(tài)的非空有窮集合。q∈Q，q稱為M的一個狀態(tài)(state)；∑——輸入字母表(inputalphabet)。要求M的輸入字符串都是∑上的字符串；?！獥７柋?stackalphabet)。A∈Γ，叫做一個棧符號；7.1基本定義下推自動機(jī)(pushdownautoma117.1基本定義Z0——Z0∈Γ叫做開始符號(startsymbol)，是M啟動時候棧內(nèi)惟一的一個符號。所以，習(xí)慣地稱其為棧底符號；q0——q0∈Q，是M的開始狀態(tài)(initialstate)，也可叫做初始狀態(tài)或者啟動狀態(tài)；F——FQ，是M的終止?fàn)顟B(tài)(finalstate)集合，簡稱為終態(tài)集。q∈F，q稱為M的終止?fàn)顟B(tài)，也可稱為接受狀態(tài)(acceptstate)，簡稱為終態(tài)。

7.1基本定義Z0——Z0∈Γ叫做開始符號(start127.1基本定義δ——狀態(tài)轉(zhuǎn)移函數(shù)(transitionfunction)，有時候又叫做狀態(tài)轉(zhuǎn)換函數(shù)或者移動函數(shù)。

δ：Q×(∑∪{ε})×Γ

7.1基本定義δ——狀態(tài)轉(zhuǎn)移函數(shù)(transition137.1基本定義 δ(q，a，Z)={(p1，γ1)，(p2，γ2)，…，(pm，γm)}表示M在狀態(tài)q，棧頂符號為Z時，讀入字符a，對于i=1，2，…，m，可以選擇地將狀態(tài)變成pi，并將棧頂符號Z彈出，將γi中的符號從右到左依次壓入棧，然后將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。

7.1基本定義 δ(q，a，Z)={(p1，γ1)，(147.1基本定義 δ(q，ε，Z)={(p1，γ1)，(p2，γ2)，…，(pm，γm)}表示M進(jìn)行一次ε-移動(空移動)，即M在狀態(tài)q，棧頂符號為Z時，無論輸入符號是什么，對于i=1，2，…，m，可以選擇地將狀態(tài)變成pi，并將棧頂符號Z彈出，將γi中的符號從右到左依次壓入棧，讀頭不移動。

7.1基本定義 δ(q，ε，Z)={(p1，γ1)，(157.1基本定義符號使用約定英文字母表較為前面的小寫字母，如a，b，c，…，表示輸入符號；英文字母表較為后面的小寫字母，如x，y，z，…，表示由輸入字符串；英文字母表的大寫字母，表示棧符號；希臘字母α，β，γ，…，表示棧符號串。

7.1基本定義符號使用約定167.1基本定義即時描述(instantaneousdescription，ID)(q，w，γ)∈(Q，∑*，Γ*)稱為M的一個即時描述。它表示M處于狀態(tài)q，w是當(dāng)前還未處理的輸入字符串，而且M正注視著w的首字符，棧中的符號串為γ，γ的最左符號為棧頂符號，最右符號為棧底的符號，較左的符號在棧的較上面，較右的符號在棧的較下面。7.1基本定義即時描述(instantaneousde177.1基本定義如果(p，γ)∈δ(q，a，Z)，a∈∑，則(q，aw，Zβ)├M(p，w，γβ)表示M做一次非空移動，從ID(q，aw，Zβ)變成ID(p，w，γβ)。

如果(p，γ)∈δ(q，ε，Z)，則(q，w，Zβ)├M(p，w，γβ)表示M做一次空移動，從ID(q，aw，Zβ)變成ID(p，w，γβ)。7.1基本定義如果(p，γ)∈δ(q，a，Z)，a∈∑，187.1基本定義├Mn是├M的n次冪(q1，w1，β1)├Mn(qn，wn，βn)├M*是├M的克林閉包(q，w，α)├M*(p，x，β)├M+是├M的正閉包(q，w，α)├M+(p，x，β)7.1基本定義├Mn是├M的n次冪197.1基本定義M接受的語言

M用終態(tài)接受的語言L(M)={w|(q0，w，Z0)├*(p，ε，β)且p∈F}

M用空棧接受的語言N(M)={w|(q0，w，Z0)├*(p，ε，ε)}

7.1基本定義M接受的語言207.1基本定義例7-1考慮接受語言L={w2wT|w∈{0,1}*}的PDA的設(shè)計。解法1：先設(shè)計產(chǎn)生L的CFGG1： G1：S2|0S0|1S1再將此文法轉(zhuǎn)化成GNF： G2：S2|0SA|1SB A0 B1

7.1基本定義例7-1考慮接受語言L={w2wT|217.1基本定義句子0102010的最左派生和我們希望相應(yīng)的PDAM的動作。

派生M應(yīng)該完成的動作S0SA從q0啟動，讀入0，將S彈出棧，將SA壓入棧，狀態(tài)不變01SBA在狀態(tài)q0，讀入1，將S彈出棧，將SB壓入棧，狀態(tài)不變

010SABA在狀態(tài)q0，讀入0，將S彈出棧，將SA壓入棧，狀態(tài)不變0102ABA在狀態(tài)q0，讀入2，將S彈出棧，將ε壓入棧，狀態(tài)不變01020BA在狀態(tài)q0，讀入0，將A彈出棧，將ε壓入棧，狀態(tài)不變010201A在狀態(tài)q0，讀入1，將B彈出棧，將ε壓入棧，狀態(tài)不變0102010在狀態(tài)q0，讀入0，將A彈出棧，將ε壓入棧，狀態(tài)不變7.1基本定義句子0102010的最左派生和我們希望相應(yīng)227.1基本定義M1=({q0}，{0，1，2}，{S，A，B}，δ1，q0，S，Φ)。其中：δ1(q0，0，S)={(q0，SA)}δ1(q0，1，S)={(q0，SB)}δ1(q0，2，S)={(q0，ε)}δ1(q0，0，A)={(q0，ε)}δ1(q0，1，B)={(q0，ε)}此時有：N(M1)=L。7.1基本定義M1=({q0}，{0，1，2}，{S，A237.1基本定義M2=({q0,q1},{0,1,2},{S,A,B,Z0},δ2,q0,Z0,{q1})δ2(q0，0，Z0)={(q0，SAZ0)}δ2(q0，1，Z0)={(q0，SBZ0)}δ2(q0，2，Z0)={(q1，ε)}δ2(q0，0，S)={(q0，SA)}δ2(q0，1，S)={(q0，SB)}δ2(q0，2，S)={(q0，ε)}δ2(q0，0，A)={(q0，ε)}δ2(q0，1，B)={(q0，ε)}δ2(q0，ε，Z0)={(q1，ε)}此時有：N(M2)=L(M2)=L。

7.1基本定義M2=({q0,q1},{0,1,2},{247.1基本定義解法2：注意到L={w2wT|w∈{0,1}*}，所以PDAM3的工作可以分成兩大階段。在讀到字符2之前，為“記載”階段：每讀到一個符號就在棧中做一次相應(yīng)的記載。在讀到2以后，再讀到字符時，就應(yīng)該進(jìn)入“匹配”階段：由于棧的“先進(jìn)后出”特性正好與wT相對應(yīng)，所以，用棧頂符號逐一地與輸入字符匹配。

7.1基本定義解法2：257.1基本定義M3=({q0，q1，q2，qf，qt}，{0，1，2}，{A，B，Z0}，δ3，q0，Z0，{qf})

q0為開始狀態(tài)q1為記錄狀態(tài)q2為匹配狀態(tài)qf為終止?fàn)顟B(tài)qt陷阱狀態(tài)

7.1基本定義M3=({q0，q1，q2，qf，qt}，267.1基本定義δ3(q0，0，Z0)={(q1，AZ0)}δ3(q0，1，Z0)={(q1，BZ0)}δ3(q0，2，Z0)={(qf，ε)}δ3(q1，0，A)={(q1，AA)}δ3(q1，1，A)={(q1，BA)}δ3(q1，0，B)={(q1，AB)}δ3(q1，1，B)={(q1，BB)}

7.1基本定義δ3(q0，0，Z0)={(q1，AZ0)277.1基本定義δ3(q1，2，A)={(q2，A)}δ3(q1，2，B)={(q2，B)}δ3(q2，0，A)={(q2，ε)}δ3(q2，0，B)={(qt，ε)}δ3(q2，1，B)={(q2，ε)}δ3(q2，1，A)={(qt，ε)}δ3(q2，ε，Z0)={(qf，ε)}此時有：N(M3)=L(M3)=L。7.1基本定義δ3(q1，2，A)={(q2，A)}287.1基本定義不追求讓PDA同時用終止?fàn)顟B(tài)和空棧接受同樣的語言，還可以刪除狀態(tài)qf。這樣我們可以得到PDAM4。M4=({q0，q1，q2}，{0，1，2}，{A，B，Z0}，δ4，q0，Z0，Φ)

δ4(q0，0，Z0)={(q1，AZ0)}δ4(q0，1，Z0)={(q1，BZ0)}δ4(q0，2，Z0)={(q2，ε)}7.1基本定義不追求讓PDA同時用終止?fàn)顟B(tài)和空棧接受同樣297.1基本定義δ4(q1，0，A)={(q1，AA)}δ4(q1，1，A)={(q1，BA)}δ4(q1，0，B)={(q1，AB)}δ4(q1，1，B)={(q1，BB)}δ4(q1，2，A)={(q2，A)}δ4(q1，2，B)={(q2，B)}δ4(q2，0，A)={(q2，ε)}δ4(q2，1，B)={(q2，ε)}7.1基本定義δ4(q1，0，A)={(q1，AA)}307.1基本定義確定的(deterministic)PDA(q，a，Z)∈Q×∑×Γ， |δ(q，a，Z)|+|δ(q，ε，Z)|≤1

PDA在每一個狀態(tài)q和一個棧頂符號下的動作都是惟一的。

關(guān)鍵對于(q，Z)∈Q×Γ，M此時如果有非空移動，就不能有空移動。每一種情況下的移動都是惟一的。7.1基本定義確定的(deterministic)PDA317.1基本定義例7-2構(gòu)造接受L={wwT|w∈{0,1}*}的PDA。差異δ(q0，0，A)={(q0，AA)，(q1，ε)} 0是w中的0或者是wT的首字符0；δ(q0，1，B)={(q0，BB)，(q1，ε)} 1是w中的1或者是wT的首字符1。

7.1基本定義例7-2構(gòu)造接受L={wwT|w∈{0327.2PDA與CFG等價

對于任意PDAM1，存在PDAM2，使得L(M2)=N(M1)；對于任意PDAM1，存在PDAM2，使得N(M2)=L(M1)。CFL可以用空棧接受語言的PDA接受。PDA接受語言可以用CFG描述。

7.2PDA與CFG等價對于任意PDAM1，存在PD337.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價

定理7-1對于任意PDAM1，存在PDAM2，使得N(M2)=L(M1)。

證明要點：

（1）構(gòu)造。設(shè)PDAM1=(Q，∑，Γ，δ1，q01，Z01，F(xiàn))取PDAM2=(Q∪{q02，qe}，∑，?！葅Z02}，δ，q02，Z02，F(xiàn))其中Q∩{q02，qe}=?！蓒Z02}=Φ。

7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價定理7-347.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價

δ2(q02，ε，Z02)={(q01，Z01Z02)}(q,a,Z)∈Q×∑×Γ,δ2(q,a,Z)=δ1(q,a,Z)；(q,Z)∈(Q-F)×Γ,δ2(q,ε,Z)=δ1(q,ε,Z)；(q,Z)∈F×Γ δ2(q,ε,Z)=δ1(q,ε,Z)∪{(qe,ε)}；q∈F,δ2(q,ε,Z02)={(qe,ε)}；Z∈?！葅Z02},δ2(qe,ε,Z)={(qe,ε)}7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價δ2(q0357.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價

（2）證明N(M2)=L(M1)。

x∈L(M1)(q01，x，Z01)├M1*(q，ε，γ)且q∈F(q01，x，Z01Z02)├M1*(q，ε，γZ02)且q∈F(q01，x，Z01Z02)├M2*(q，ε，γZ02)且q∈F7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價（2）證367.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價

(q01，x，Z01Z02)├M2*(q，ε，γZ02)├M2*(qe，ε，ε)且q∈F(q01，x，Z01 Z02)├M2*(qe，ε，ε)(q02，x，Z02)├M2(q01，x，Z01Z02)├M2*(qe，ε，ε)(q02，x，Z02)├M2*(qe，ε，ε)x∈N(M2)7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價(q01377.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價

定理7-2對于任意PDAM1，存在PDAM2，使得L(M2)=N(M1)。

證明要點：

(1)構(gòu)造。設(shè)PDAM1=(Q，∑，Γ，δ1，q01，Z01，

Φ)

7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價定理7-387.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價

取PDAM2=(Q∪{q02，qf}，∑，?！葅Z02}，δ，q02，Z02，{qf})其中Q∩{q02，qf}=?！蓒Z02}=Φ。δ2的定義如下，δ2(q02，ε，Z02)={(q01，Z01Z02)}對于(q，a，Z)∈Q×(∑∪{ε})×Γ,δ2(q，a，Z)=δ1(q，a，Z)。 δ2(q，ε，Z02)={(qf，ε)}

7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價取PDA397.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價

(2)證明L(M2)=N(M1)。x∈L(M2)(q02，x，Z02)├M2*(qf，ε，ε)(q02，x，Z02)├M2(q01，x，Z01Z02)(q02，x，Z02)├M2(q01，x,Z01Z02)├M2*(qf,ε,ε)。(q01，x，Z01Z02)├M2*(q，ε，Z02)且(q，ε，Z02)├M2*(qf，ε，ε)(q01，x，Z01Z02)├M1*(q，ε，Z02)。(q01，x，Z01)├M1*(q，ε，ε)。x∈N(M1)。7.2.1PDA用空棧接受和用終止?fàn)顟B(tài)接受等價(2)證407.2.2PDA與CFG等價

定理7-3對于任意CFLL，存在PDAM，使得N(M)=L。

證明要點：先考慮識別L-{ε}的PDA，然后再考慮對ε的處理問題。

7.2.2PDA與CFG等價定理7-3對于任意CFL417.2.2PDA與CFG等價

(1)構(gòu)造PDA。

設(shè)GNFG=(V，T，P，S)，使得L(G)=L-{ε}。取PDAM=({q}，T，V，δ，q，S，Φ)對于任意的A∈V，a∈T， δ(q，a，A)={(q，γ)|Aaγ∈P}也就是說，(q，γ)∈δ(q，a，A)的充分必要條件是Aaγ∈P。

7.2.2PDA與CFG等價(1)構(gòu)造PDA。427.2.2PDA與CFG等價

(2)證明構(gòu)造的正確性：N(M)=L-{ε}。施歸納于w的長度n，證明(q，w，S)├Mn(q，ε，α)的充分必要條件為Snwα。并且在假設(shè)結(jié)論對n=k成立，而證明結(jié)論對n=k+1成立時，取w=xa，|x|=k，a∈T。在證明必要性時有如下過程，充分性的證明過程是倒退回來。

7.2.2PDA與CFG等價(2)證明構(gòu)造的正確性：N437.2.2PDA與CFG等價

(q,w,S)=(q，xa，S)├Mk(q，a，γ)├M(q，ε，α)此時必定存在A∈V，γ=Aβ1，(q,β2)∈δ(q,a,A)。 (q,a,γ)=(q,a,Aβ1)├M(q,ε,β2β1)=(q，ε，α)。由(q，β2)∈δ(q，a，A)就可以得到Aaβ2∈P，再由歸納假設(shè)，得到 SkxAβ1。合起來就有 SkxAβ1xaβ2β1。

7.2.2PDA與CFG等價(q,w,S)=(q，xa，447.2.2PDA與CFG等價

(3)考慮ε∈L的情況。

先按照(1)的構(gòu)造方法構(gòu)造出PDA M=({q}，T，V，δ，q，S，Φ)使得N(M)=L-{ε}。然后取 M1=({q，q0}，T，V∪{Z}，δ1，q0，Z，Φ)其中，q0≠q，ZV，令δ1(q0，ε，Z)={(q0，ε)，(q，Z0)}，對于(a，A)∈T×Vδ1(q，a，A)=δ(q，a，A)

7.2.2PDA與CFG等價(3)考慮ε∈L的情況。457.2.2PDA與CFG等價

定理7-4對于任意的PDAM，存在CFGG使得L(G)=N(M)。

證明要點：

(1)構(gòu)造對應(yīng)(q1，A1A2…An)∈δ(q，a，A)難以用產(chǎn)生式[q，A]a[q1，A1A2…An]模擬。同樣也難以用[q，A]a[q1，A1][q2，A2]…[qn，An]模擬。7.2.2PDA與CFG等價定理7-4對于任意的PD467.2.2PDA與CFG等價

PDA的移動(q1，A1A2…An)∈δ(q，a，A)需要用如下形式的產(chǎn)生式模擬。[q，A，qn+1]a[q1，A1，q2][q2，A2，q3]…[qn，An，qn+1]q2，…，qn是分別對應(yīng)PDA恰“處理完”A1進(jìn)而處理A2，…，恰“處理完”An-1進(jìn)而處理An的狀態(tài)。當(dāng)然就有了恰“處理完”An而進(jìn)入的狀態(tài)qn+1