有限自動機(jī)理論05章下推自動機(jī)

1、第五章 下推自動機(jī) PDA,FA識別正則語言(右線性語言)PDA識別上下文無關(guān)語言,,FA只能處理正則語言 正則文法生成無窮語言是由于 A->wA不需要記錄w的個數(shù),,無關(guān)文法生成無窮語言 A->αAβ 需要記錄α和β之間的對應(yīng)關(guān)系 無法用FA的有窮個狀態(tài)來表示。,,為FA擴(kuò)充一個無限容量的棧 用棧的內(nèi)容和FA的狀態(tài)結(jié)合起來就可以表示無限存儲。這種模型就是下

2、推自動機(jī)PDA,,PDA作為形式系統(tǒng)最早于1961年出現(xiàn)在 Oettinger 的論文中。 與上下文無關(guān)文法的等價性由Chomsky于1962年發(fā)現(xiàn)。,與FA比較,PDA具有一個棧存儲器有兩個操作： 入棧---將內(nèi)容壓入棧中 出棧---將棧頂元素移出,下推自動機(jī)物理模型,a1,a2,a3,…,aj,…,an,an+1,,,…,FSC,,,,,…,存儲帶,棧存儲器,棧存儲器,存放不同于字母的符號 只能對棧頂元素進(jìn)

3、行操作。,下推自動機(jī)動作 根據(jù),FSC當(dāng)前的狀態(tài) 輸入帶上的當(dāng)前字符 棧頂符號 進(jìn)行狀態(tài)改變和入?；虺鰲２僮?將讀頭向右移動一個單元,,,5.1.1 確定的下推自動機(jī),例5-1 語言 L={w|w∈(a,b)*，且a、b個數(shù)相等} 暫時不考慮狀態(tài) (或PDA僅有一個狀態(tài)),初始,棧為空從左到右逐個掃描串w∈(a，b)*,入棧,若棧為空,當(dāng)前符號是a,則A入棧若棧為空,當(dāng)前符號是b,則B入

4、棧若棧頂為A,當(dāng)前符號是a,則A入棧若棧頂為B,當(dāng)前符號是b,則B入棧,出棧,若棧頂為A,當(dāng)前符號是b，則A出棧若棧頂為B,當(dāng)前符號是a，則B出棧,,若串w有相同個數(shù)的a和b 當(dāng)且僅當(dāng) w掃描結(jié)束后，棧為空。,注意,PDA在兩種情況下停機(jī)： 串掃描結(jié)束 沒有對應(yīng)的規(guī)則,串掃描結(jié)束,棧如果為空 就接收掃描過的串。,,對于非正式的算法， 用形式化的方式進(jìn)行描述：,,特殊的符號Z0表示棧底 初

5、始化時先壓入棧,規(guī)則(指令),若x是w的當(dāng)前符號 D是棧頂符號則用符號串V代替D即將D彈出棧，而將串V壓入棧,具體,若x是w的當(dāng)前符號，棧頂符號為D 將D彈出棧 將A壓入棧，成為新的棧頂,一般地,若x是w的當(dāng)前符號，棧頂符號為D 表示： 將D彈出棧 將串A1A2… Ak壓入棧(A1為新棧頂),例5-1 算法的形式化描述,,,規(guī)則 表示將w掃描結(jié)束后，將棧置成空也表示

6、該P(yáng)DA可以接收空串ε,思考：,如何接收語言 L={w|w∈(a,b)+,且a和b個數(shù)相等}?,例：語言L={anbn|n≥0},定義： ,,則還可以接收語言 {(ab)n|n≥0}，或 {ambm(ab)n|m≥0,n≥0} 等語言。,思考：如何接收語言,L={anbn|n>0} L={anbn|n≥0} L={(ab)n|n>0} L={(ab)n|n≥0},例5

7、-2,L={wcwT|w∈(a，b)*},識別語言,思想：,將w的各個字符壓入棧后 棧中的內(nèi)容從棧頂?shù)綏５椎捻樞?剛好是wT的順序,,為了區(qū)別壓棧和出棧動作 增加兩個狀態(tài)----read 和match PDA處于read狀態(tài)時， 處理整個串的前半部分，將對應(yīng)的符號壓入棧,,掃描到字母c時 PDA的狀態(tài)轉(zhuǎn)為match開始處理整個串的后半部分，將棧中的內(nèi)容出棧。,規(guī)則,若PDA處于狀態(tài)q w的當(dāng)前

8、字母是x 當(dāng)前棧頂符號為D則自動機(jī)的狀態(tài)改變?yōu)閝′并用符號串V代替D,,（在本例中）用Z代表任意的棧頂符號 規(guī)則〈read，a，Z，read，AZ>可以表示以下3條規(guī)則：〈read，a，Z0，read，AZ0>〈read，a，A，read，AA>〈read，a，B，read，AB>,用下列的規(guī)則來描述PDA,〈read，a，Z，read，AZ>〈read，b，Z，read，BZ&g

9、t;〈read，c，Z，match，Z>〈match，a，A， match，ε>〈match，b，B， match，ε>〈match，ε，Z0，match，ε>,,若串w是該語言的合法的串 當(dāng)且僅當(dāng) w掃描結(jié)束后，棧為空。,Z0,符號棧,串a(chǎn)bbcbba的處理過程,A,B,,read,,,,,,,,,,,,,,match,=>,,,B,,,,,掃描到字母c,棧內(nèi)的內(nèi)容（從棧頂?shù)綏５祝┦菕呙柽^

10、的串的逆 與未掃描過的串的順序相同此時，不作出棧和入棧操作，僅僅把PDA的狀態(tài)從read改變到match。,接收語言L={anbn|n>0},〈q0，a，Z0，q0，AZ0>〈q0，a，A，q0，AA>〈q0，b，A，q1，ε>〈q1，b，A，q1，ε>〈q1，ε，Z0，q1，ε>,5.1.2 不確定的下推自動機(jī),例5-3 語言L={wwT|w∈(a,b)*},,沒有中心點(diǎn)字符

11、 在掃描過程中，就沒有確定的位置進(jìn)行狀態(tài)的變換 具有不確定性。,,使用規(guī)則〈read，ε，Z，match，Z> 來代替〈read， c ，Z，match，Z>即在read狀態(tài)時，可隨時改變?yōu)閙atch狀態(tài)（棧的內(nèi)容和掃描符號不變）,,〈read，a，Z，read，AZ>〈read，b，Z，read，BZ>〈read，ε，Z，match，Z>〈match，a，A， match，ε>

12、〈match，b，B， match，ε>〈match，ε，Z0，match，ε>,,該P(yáng)DA是不確定的 處于狀態(tài)read狀態(tài)時 隨時都可以進(jìn)行選擇: 繼續(xù)掃描，或狀態(tài)變換為match,,一個串w能夠由PDA所識別： 僅當(dāng)串是wwT的形式且PDA狀態(tài)在中心點(diǎn)進(jìn)行了變換,,對于不確定的PDA和串w 若存在至少一個可能的掃描過程 使得當(dāng)串w掃描結(jié)束時，棧為空 則稱串w能夠被PDA所識別。,

13、接收語言L={(ab)n|n≥0},〈q1，a，Z0，q2，AZ0>〈q2，b，A，q1，ε>〈q1，ε，Z0，q1，ε〉,接收語言L={(ab)n|n>0},〈q0，a，Z0，q0，AZ0>〈q0，b，A，q1，ε>〈q1，a，Z0，q2，AZ0>〈q2，b，A，q1，ε>〈q1，ε，Z0，q1，ε>,定義5-1,下推自動機(jī)PDA是一個七元式：M=(Q，∑，Г，δ，q0，Z

14、0，F(xiàn)) Q是一個有限狀態(tài)的集合 ∑是輸入串的字母集合 Г是棧內(nèi)符號集合,,q0∈Q是開始狀態(tài)Z0∈Г是棧底符號F?Q是接收狀態(tài)集合,,δ：Q×(∑∪{ε})×Г→Q×Г* 對于確定的PDA，有 δ（q，x，D）=( q′，V) 對于不確定的PDA，有 ( q′，V) ∈δ（q，x，D）,一般,使用 表示δ函數(shù),定義5-2 PDA格局(或瞬間描述

15、ID),格局代表某個時刻PDA的情況 PDA的格局是一個三元式 (q，w，σ) 其中，q為狀態(tài),,w=x1x2…xn 還沒有被掃描到的串(將掃描x1)σ=Z1Z2…Zm 棧的內(nèi)容(Z1在棧頂，Zm在棧底),PDA,初始格局為 (q0，w，Z0)接收格局為 (q，ε，ε)其中: q∈Q （與接收狀態(tài)無關(guān)）,,格局的轉(zhuǎn)換是 由于狀態(tài)

16、轉(zhuǎn)換函數(shù)的作用引起的,確定的PDA,引起的格局轉(zhuǎn)換為： (q，xw，Aσ)=> (q1，w，A1A2… Akσ),不確定的PDA （情況1）,① 則 (q,xw,Aσ)=> (q1，w,A1A2… Akσ)②則(q,xw,Aσ)=> (q2，xw， B1B 2…Bjσ),不確定的PDA

17、 （情況2）,①則 (q,xw,Aσ)=> (q1，w，A1A2… Akσ)②則 (q,xw,Aσ)=> (q2，w， B1B 2…Bjσ),,用=>*代表格局的任意次變換,,不確定PDA對于某一格局可能會有不同的下一格局。,5.1.3 PDA接收語言的兩種方式,定義5-3 PAD以空棧方式接收的語言為L(M），且 L(M)={w|(q0，w

18、，Z0) =>*(q,ε,ε) q∈Q},,接收格局與接收狀態(tài)無關(guān) 只要當(dāng)串w掃描結(jié)束，而棧為空則串w被PDA以空棧方式所接收。,定義5-4,PAD以終態(tài)方式接收的語言為F(M)，且 F(M)={w|(q0,w，Z0) =>*(q′,ε,σ)

19、 q′∈F,σ∈Г*},,接收格局與棧是否為空無關(guān)只要當(dāng)串w掃描結(jié)束，而PDA處于某個接收狀態(tài)則串w被PDA以終態(tài)方式所接收。,定理5-1,語言L被PDA以終態(tài)方式所接收 當(dāng)且僅當(dāng) 它被PDA以空棧方式所接收。即終態(tài)接收與空棧接收方式等價。,證明：,略,5.1.4廣義PDA和單態(tài)PDA,定義5-5 廣義的PDA是七元式 PDA=(Q,∑，Г，δ，q0，Z0，F(xiàn))（除了δ外，其余同一

20、般的PDA）其中,,Q是一個有限狀態(tài)的集合∑是輸入串的字母集合Г是棧內(nèi)符號集合q0∈Q是開始狀態(tài)Z0∈Г是初始的棧底符號F?Q是接收狀態(tài)(終止?fàn)顟B(tài))集合,,δ：Q×(∑∪{ε})×Г+→Q×Г* (q，x，B1 B2… Bk)=(q′，C1 C2… Cn) 一般形式為 ,,一般的PDA，棧頂只是一個符號廣義PDA的棧頂可以為多個符號。,定理5-4,若語言L能由廣義PDA所接收 則

21、L能夠由一般的PDA所接收。,證明思路,廣義的PDA的一條規(guī)則一般PDA的多條規(guī)則的組合,就是,證明：,對于廣義的PDA的任意一條規(guī)則 增加狀態(tài)r1，r2，…，rk-1，,,改造為： … ,,得到一般的PDA′ 且L=L(PDA′)。,定義5-6單態(tài)PDA,僅有一個狀態(tài)的PDA 規(guī)則簡化為 ,(等價性)問題,一個NFA是否可以轉(zhuǎn)換為 一個單態(tài)PDA？,思路,NFA

22、=（Q，∑ , δ，q0，F(xiàn)） 將NFA的狀態(tài)當(dāng)作PDA的棧內(nèi)符號構(gòu)造單態(tài)的PDA　=（{*}，∑，Q，δ′，*，q0，{*}),,NFA：δ(q，x)= {q1，q2，… qn｝單態(tài)的PDA： … ,,NFA： 若 q ∈δ*(q0，w)單態(tài)的PDA： 有 （*，w，q0）=>*（*，ε，q）,,NFA： 若δ(q，x)∩F≠ф 單態(tài)的PDA： ,

23、因此,NFA： δ*(q0，w)∩F≠ф單態(tài)的PDA： （*，w，q0）=>*（*，ε，ε）即 L(NFA)=L(PDA),右線性文法,G=（∑，V，S，P） 也可以對應(yīng)一個單態(tài)的PDA，,,產(chǎn)生式　　　 A→bB 　　 　　 A→b,PDA的規(guī)則 ,,將文法的開始符號S當(dāng)作是單態(tài)PDA的棧底符號，則,,對于文法G S=>*w1A=>w1bB=>*w1bw2=w

24、對于單態(tài)PDA (*，w1bw2，S)=>*(*，bw2，A) =>(*，w2，B)=>*(*， ε， ε),例5-4 語言L={anbn|n≥1},文法S→aSBS→aB B→b, ,單態(tài)PDA,,對于串a(chǎn)nbn，單態(tài)的PDA可能會有以下的格局轉(zhuǎn)換：①(*，anbn，S）=>n(*，an-jbn，SBj） ②(*，anbn，S）=>n（*，an-kbn，Bk

25、） ③(*，anbn，S）=>n（*，bn，Bn）其中：①是導(dǎo)出②和③的中間過程；,,②會導(dǎo)致停機(jī)，因為沒有合適的規(guī)則③可以完成最后的轉(zhuǎn)換： （*，bn，Bn）=>*（*，ε，ε）,,使用n-1次規(guī)則 1次規(guī)則 n次規(guī)則 ,5.1.5 下推自動機(jī)的存儲技術(shù),參考Turing的存儲技術(shù)。略,5.1.6 PDA掃描多個符號,參考Turing的

26、掃描多個符號技術(shù)。略,5.2 上下文無關(guān)文法和范式,范式是指標(biāo)準(zhǔn)的形式在代數(shù)中， 2/4，3/6，…的范式是1/2。本節(jié)討論在上下文無關(guān)文法的幾個重要的范式。,定理5-5,G是一個上下文無關(guān)文法，則存在一個上下文無關(guān)文法G′，使得：①L(G)=L(G′)②若ε≠L(G)，則G′沒有空串產(chǎn)生式,,③若ε∈L(G)，則G′有S′→ε， 且S′不出現(xiàn)在G′的任何產(chǎn)生式的右邊④G′中沒有A→B形式的產(chǎn)生式。,證明,前3點(diǎn)是空串

27、定理的內(nèi)容(見2.6)第4點(diǎn)證明參見參考文獻(xiàn)1。,5.2.1 Chomsky范式(CNF),定義5-7 上下文無關(guān)文法G=(∑，V，S，P) 若G的每個產(chǎn)生式是下列形式之一：,,A→BC A，B，C∈V A→a A∈V，a∈∑ S→ε 且S不出現(xiàn)在產(chǎn)生式的右邊則G是Chomsky范式(CNF) 。,定理5-6,G是一個上下文無關(guān)文法，則存在一個等價的上下文無關(guān)文法G′ 使得L(G)

28、=L(G′)，且G′是CNF。,證明,對于任意的上下文無關(guān)文法G 首先使它滿足定理5-5的要求 對于文法中的任意的產(chǎn)生式 A→B1B2…Bm,,假設(shè)每個Bi都是非終結(jié)符 (若不是，則使用非終結(jié)符Bi′來代替Bi，并增加產(chǎn)生式Bi′→Bi),A→B1B2…Bm,若m=2，滿足了CNF要求；m≥3，將它改造為m-1個產(chǎn)生式：,A→B1B2…Bm,A→B1C1 C1→B2C2 … Cm-3→

29、Bm-2Cm-2 Cm-2→Bm-1Bm,,其中 C1，C2，…，Cm-2是新加的非終結(jié)符得到的文法G′是CNF 且L(G)=L(G′)。證畢。,5.2.2 Greibach范式(GNF),定義5-8上下文無關(guān)文法G=(∑，V，S，P)是GNF，若G的每個產(chǎn)生式形式為 A→bW b∈∑，W∈V*,定理5-7,G是一個上下文無關(guān)文法，則存在一個等價的上下文無關(guān)文法G′，使得L

30、(G)=L(G′) 且G′中沒有直接左遞歸的產(chǎn)生式， 即不存在A→Av形式的產(chǎn)生式 其中：A∈V，v∈(∑UV)+。,,沒有直接左遞歸的文法也稱為無直接左遞歸范式（NLR）。,證明,見2.7。,,某些文法可能沒有直接左遞歸， 但可能會有間接左遞歸。,定理5-8,G是一個上下文無關(guān)文法，則存在一個等價的上下文無關(guān)文法G′， 使得L(G)=L(G′)且G′中沒有間接左遞歸的產(chǎn)生式。,,沒有間接左遞歸的文法也

31、稱為無間接左遞歸范式。,證明,見2.7。,定理5-9,G是任意一個上下文無關(guān)文法，則存在一個等價的上下文無關(guān)文法G′， 使得L(G)=L(G′) 且G′是Greibach范式(GNF)。,,對于任意的上下文無關(guān)文法G，產(chǎn)生式形式為 Ai→Ajw Ai→aw,或,,假設(shè)w包含的字符全為非終結(jié)符對于Ai→aw，本身就是GNF的形式,對于Ai→Ajw,利用消除左遞歸的算法，

32、在消除左遞歸的以后，從An-1開始，將An代入到An-1，將An-1代入到A n-2，直至A1， 再將增加的非終結(jié)符的產(chǎn)生式的開頭符號代替掉，得到GNF。,5.3 PDA與上下文無關(guān)語言,PDA識別的語言是上下文無關(guān)語言。,定理5-10,對于上下文無關(guān)語言L和文法G 若L=L(G)，則語言L能被(廣義)不確定的PDA所接收,證明：,假設(shè)文法是GNF范式 構(gòu)造一個單態(tài)的PDA來接收語言L；,,文法G中有3種形式的產(chǎn)生式，

33、它們分別對應(yīng)PDA的規(guī)則： S→ε A→b A→bW其中：A∈V，W∈V+，,,需要證明,語言L=L(PDA)。為證明之，先證明（*，w1w2，S）=>*（*，w2，σ） iff S=>*w1σ,,即掃描串后w1，M棧內(nèi)符號串為σ；若上述成立，假設(shè)w2=σ=ε，則（*，w1，S）=>*（*，ε，ε） iff S=>*w1,,現(xiàn)在用歸納法證明

34、（對串w1的長度進(jìn)行歸納）（*,w1w2，S）=>*（*,w2，σ） iff S=>*w1σ,證明,基礎(chǔ)：當(dāng)w1=ε，有兩種情況：a）（*，w2，S）=>*（*，w2，S） iff S=>*S 是成立的；b）若S→ε在G中，則有 （*,w2，S）=>*（*，w2，ε） iff S=>*ε 是成立的；,,假設(shè)：當(dāng)w1≠ε時，長度

35、為n時；（*,w1w2，S）=>*（*,w2，σ） iff S=>*w1σ令σ=Aг，w2=aw3，（將w1a當(dāng)作新的w1，長度為n+1），則,,(*,w1aw3，S）=>*（*, aw3， Aг） iff S=>*w1Aг而（*， aw3， Aг）=>（*， w3， г′г） iff A→aг′,因此,(*，w1aw3，S

36、)=>*(*， w3， г′г) iff S=>*w1aг′г所以：假設(shè)成立，證畢。,例5-10,文法G為 S→(L|ε L→(LL|)對于串：(()()),,構(gòu)造的單態(tài)的PDA（棧底為S）為：,S→(LS→ε L→(LLL→),,對于單態(tài)的PDA 可以構(gòu)造對應(yīng)的上下文無關(guān)文法G 使得L(M)=L(G),例5-11有單態(tài)的PDA：,

37、,,構(gòu)造上下文無關(guān)文法G（用Z代替Z0作為開始符號）為： Z→aAZ|bBZ|ε A→aAA|b B→bBB|a,例5-12構(gòu)造PDA,接收語言 L={w2wT | w∈{0,1}*},解法1：,read--match,解法2：GNF =>PDA,產(chǎn)生L的上下文無關(guān)文法： S→2 | 0S0 | 1S1,將文法轉(zhuǎn)化成GNF,S→2 | 0SA | 1SB A→0 B→1,構(gòu)造單態(tài)PDA,

38、 //S→0SA //S→1SB //S→2 //A→0 //B→1,定理5-11,對于單態(tài)的PDA 存在一個上下文無關(guān)文法G 使得L（G）= L(PDA) 且G為GNF范式形式。,證明,PDA 文法 B→aσ B→a,,根據(jù)單態(tài)的PDA 可以得

39、到對應(yīng)的GNF。而多態(tài)的PDA，不可以直接得到GNF。,問題,多態(tài)PDA如何得到對應(yīng)的上下文無關(guān)文法？,定理5-12,對于多態(tài)PDA，存在上下文無關(guān)文法G，使得L(G)=L(M)。,證明,構(gòu)造上下文無關(guān)文法G 思路為用文法的一個推導(dǎo)模擬PDA的一個動作 。具體過程參考P135。,對于多態(tài)PDA,得到對應(yīng)的上下文無關(guān)文法的產(chǎn)生式具有如下的形式： A→aA1A2…An A→A1A2…An A→a

40、 A→ε,定理5-13,若M是多態(tài)的PDA，則存在一個單態(tài)PDA′，使得 L(PDA)= L(PDA′),證明,略。,總之,對于一個PDA 存在一個上下文無關(guān)文法G，使得L(M)=L(G)。,注意,確定PDA和不確定PDA不等價。,例 構(gòu)造PDA接收,語言L={w|w∈{a,b}* w中a的個數(shù)為b的2倍 且a必須成對出現(xiàn)},思路：,將一個a當(dāng)作一個

41、成對的aa:構(gòu)造上下文無關(guān)文法G為：Z→aCAZ|bBZ|εA→aCAA|bB→bBB|aCC→a,有單態(tài)PDA：, ,例5-16構(gòu)造(廣義)PDA接收,語言 L={w|w∈{a,b}* 且w中a的個數(shù)為b的2倍},考慮出棧情況,基本結(jié)構(gòu)為：aab、aba和baa。,aab、aba和baa,,方法2：,構(gòu)造文法S→SaSaSbS|SaSbSaS

42、|SbSaSaS|ε 轉(zhuǎn)換為GNF 轉(zhuǎn)換為PDA,思考 構(gòu)造PDA接收,語言L={w|w∈{a,b}+,且w中a的個數(shù)為b的2倍}考查題—第2題,例5-17 構(gòu)造PDA接收,語言 L={anbm|0≦n ≦ m，m ≦ 2n},,S→aSB|aSBB|ε B→b,單態(tài)PDA為,,或 單態(tài)PDA,,例5-18 構(gòu)造PDA接收,語言L={anbm|0 ≦ m ≦ n，n ≦ 2m},,S→a