【正文】 ⑶ ┳ ⑻ (q1,11,BBGGR) (q2,ε,R) ┳ ⑷ ┳ ⑼ (q1,1,GBBGGR) ┣ ⑹ (q2,ε,BBGGR) (q2,ε,ε) ┳ ⑹ (q1,ε,GGBBGGR) 作業(yè)題 1． 構(gòu)造一個 PDA M， 使得 T(M)= {w| w∈ {a,b}* ∧ w 中的 a,b的個數(shù)相等 }。 PDA與 CFG之間的等價性 這里類似地介紹 PDA與 CFG之間的等價性。 在介紹它們相互轉(zhuǎn)換之前，先介紹 PDA的兩種接收語 言方式可以互相轉(zhuǎn)換。 1． PDA的兩種接收語言方式互相轉(zhuǎn)換 定理 設(shè)一個 PDA M用空棧接收語言 L， 即 N(M)=L， 當(dāng)且僅當(dāng)存在一個 PDA M’,使得 M’用終止?fàn)顟B(tài)接 收 L， 即 T(M’)=L。 證明 ： 1．必要性 ：設(shè) M=(K,Σ,Γ,δ,q0,Z0,Φ)， 用空棧 接收語言 L， N(M)=L。 構(gòu)造 M’=(K∪ {q0’,qf},Σ,Γ∪ {Z0’},δ’,q0’,Z0’,{qf})， 其中 q0’,qf?K， Z0’?Γ。 假設(shè) M接收句子 w， 即 w∈ N(M)， 則 M必有如下 ID變換： M： (q0,w,Z0)├* (q,ε,ε) 其中 q∈ K M’要接收 w， 必須能夠從它的開始 ID（ q0’,w,Z0’） 進(jìn)入 到 M的開始 ID（ q0,w,Z0）， 以后 M’就能夠模擬 M的所有 動作，當(dāng)達(dá)到 M的終止時的 ID（ q,ε,ε） 時，最后進(jìn)入 M’的終止?fàn)顟B(tài) qf， 從而接收 w。 于是 M’的動作序列為： M’： (q0’,w,Z0’)├ (q0,w,Z0Z0’)├* (q,ε,εZ0’)├ (qf,ε,ε) 其中 q∈ K 于是 δ’有下面三種類型的動作： 1） δ’(q0’,ε,Z0’)={(q0,Z0Z0’)} 此動作可使 M’進(jìn)入 M 的開始 ID。 2） 對任何 q∈ K， 任何 a∈ Σ∪ {ε}， 任何 X∈ Γ, δ’(q,a,X)=δ(q,a,X) 這類動作使得 M’模擬 M的所 有動作。 3） 對任何 q∈ K, δ’(q,ε,Z0’)={(qf,ε)} 使得 M’進(jìn)入自己的終止?fàn)顟B(tài)。 根據(jù)上面分析，可以看到：任何 w∈ N(M)， 必有 w∈ T(M’)， (這里不作詳細(xì)證明 )。反之亦然。故有 T(M’)=N(M)。 2． 充分性 ：設(shè) M’=(K,Σ,Γ,δ’,q0’,Z0’,F)， 用終止?fàn)? 態(tài)接收 L， 且 T(M)=L。 構(gòu)造 M=(K∪ {q0,qe},Σ,Γ∪ {Z0},δ,q0,Z0,Φ)， 其中 q0,qe?K， Z0?Γ。 假設(shè) M’接收子 w， 即 w∈ T(M’)， 則 M’必有 ID序列： M’： (q0’,w,Z0’)├ * (q,ε,γ) 其中 q∈ F， γ∈ Γ*。 M要接收 w， 必須能夠從它的開始 ID（ q0,w,Z0） 進(jìn)入 M’ 的開始 ID（ q0’,w,Z0’）， 以后能夠模擬 M’的所有動作， 達(dá)到 M’的終了時的 ID（ q,ε,γ）， 最后進(jìn)入 M的清棧狀 態(tài) qe， 再進(jìn)行清棧，使棧內(nèi)為空。于是 M的動作序列為： M： (q0,w,Z0)├ (q0’,w,Z0’Z0)├ * (q,ε,γZ0)├ * (qe,ε,ε) 其中 q∈ K 于是 δ有下面四種類型的狀態(tài)轉(zhuǎn)移函數(shù)： 1） δ(q0,ε,Z0)={(q0’,Z0’Z0)} 可使 M進(jìn)入 M’的開始 ID。 2） 對任何 q∈ K, 任何 a∈ Σ∪ {ε}, 任何 X∈ Γ, δ(q,a,X)=δ’(q,a,X) 使得 M模擬 M’的所有動作。 3） 對任何 q∈ F, 任何 X∈ Γ∪ {Z0}, δ(q,ε,X)={(qe,ε)} 此動作使得 M進(jìn)入清棧狀態(tài) qe。 4） 對任何 X∈ ?！?{Z0}, δ(qe,ε,X)={(qe,ε)} 使得 M反復(fù)清棧，直至棧內(nèi)為空。 根據(jù)上面分析，可 得 ：任何 w∈ T(M’)， 必有 w∈ N(M)， 反之亦然。 (這里不作詳細(xì)證明 )。故有 N(M)=T(M’)。 從這個定理看到， PDA的兩種接收語言的方式可以互相 轉(zhuǎn)換。因此以后我們討論的 PDA， 對它接收語言的方式 不加限制。 2． 由 CFG 轉(zhuǎn)換成 PDA 下面介紹根據(jù)給定的 CFG G， 求接收 L(G)的 PDA M。 為了理解定理的證明，我們先舉一個例子。 【例 】 給定 CFG G=({S},{0,1},P,S)， 其中 P： S?0S0|1S1|00|11。 顯而易見， L(G)={wwR|w∈ {0,1}*} 求一個 PDA M， 使得 N(M)=L(G)。 解 ： 1． 先將 G變成 GNF形式的 G’， 得 G’=({S,A,B},{0,1},P’,S) P’： S?0SA|1SB|0A|1B , A?0, B?1。 2． 構(gòu)造 PDA M=({q},{0,1},{S,A,B},δ,q,S,Φ)， 其中 δ中動作的確定：如果 A?aγ∈ P’， 則有 δ(q,a,A)中含 有 (q,γ)。 因而，由 S?0SA|0A 得： δ (q,0,S)={(q,SA),(q,A)}。 由 S?1SB|1B 得： δ (q,1,S)={(q,SB),(q,B)}。 由 A?0 得： δ (q,0,A)={(q,ε )}。 由 B?1 得： δ (q,1,B)={(q,ε )}。 下面驗證一下它接收的語言與 G產(chǎn)生的語言是相同的， 并看一看 M是如何模擬 G的派生的。 G中對句子 011110的最左派生過程： S?0SA?01SBA?011BBA?0111BA?01111A?011110 M識別 011110的過程： (q,011110,S)├ (q,11110,SA)├ (q,1110,SBA)├ (q,110,BBA) ├ (q,10,BA)├ (q,0,A)├ (q,ε,ε) PDA M在識別 011110時的每個 ID中的棧內(nèi)符號串，分別 與文法 G的相應(yīng)派生的句型中的變元串相同。從這里看 出 PDA M是模擬 G的最左派生的。 下面給出有關(guān)定理 。 定理 L是 CFL， 則存在 PDA M， 使得 N(M)=L。 證明 ：如果 ε?L， 令 G =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ,S)是具有 GNF形式的 CFG， 且 L(G)=L。 構(gòu)造 PDA M＝ ({q},Ｖ Ｔ ,Ｖ Ｎ ,δ,q,S,Φ) 其中 δ中動作確定：如果 A?aγ∈ P， 則有 δ(q,a,A)中含有 (q,γ)， a∈ Ｖ Ｔ ， γ∈ Ｖ Ｎ *。 PDA M模擬 G的最左派生。由于 G具有 GNF形式，所以 G 的最左派生中的每個句型都是 xα形式，其中 x∈ Ｖ Ｔ +， α∈ Ｖ Ｎ *。 M總是在識別完前部分終極符串 x之后，將句 型 中余下的變元串 α 存在棧內(nèi)。即用歸納法證明如下結(jié)論： G中最左派生 S?*xα， 當(dāng)且僅當(dāng) M中有 (q,x,S)├ *(q,ε,α)。 1． 充分性 。已知 M中有 (q,x,S)├ *(q,ε,α)， 對 M的動作次 數(shù)歸納，證出 G中有最左派生 S?*xα 。 ⑴ 當(dāng) M動作次數(shù)為 0時，有 (q,x,S)├ (q,ε,α)， 顯然此時 x=ε,α=S， 于是 G中有 S?xα。 ⑵ 假設(shè) (q,y,S)├ *(q,ε,β)是由少于 k個動作完成，則文法 G中有派生： S?* yβ(這里 x=y, α=β)。 ⑶ 當(dāng) (q,ya,S)├ *(q,a,β)├ (q,ε,α)是由 k個動作完成時 (這里 x=ya)， 前 k1個動作根據(jù)假設(shè)⑵得：在 G中有派生 S?*yβ。 下面通過分析 M的棧內(nèi)符號串得出如下結(jié)論： 令 β＝ Aγ， A∈ Γ(Γ=Ｖ Ｎ )， α=ηγ， 于是 M的第 k個 動作可以寫成： (q,a,Aγ)├ (q,ε,ηγ)， 由此說明 M有如下狀態(tài)轉(zhuǎn)移函 數(shù)： δ(q,a,A)中有 (q,η),于是 G中有產(chǎn)生式： A?aη， 于 是 G中有派生： S?*yβ ＝ yAγ ?yaηγ=xα , 即 S?* xα 。 可見結(jié)論成立 。 2．必要性 。 設(shè) G中有最左派生 S?*xα，（ 通過對 G中派生 步數(shù)歸納證明 M中有：（ q,x,S） ├ *（ q,ε,α） ）。 ⑴ 如果 G中此派生是由 0步完成的，則此派生為： S?S ， 令 x=ε,α=S， 所以此派生也可以寫成 S?xα。 而 M中顯 然有 (q,ε,S)├ (q,ε,S)， 于是也可以寫成 (q,x,S)├ (q,ε,α)。 結(jié)論成立。 ⑵ 假設(shè) G中派生 S?*xα是由少于 k步完成時，則 M中有 (q,x,S)├ *(q,ε,α)。 ⑶ 若 G中有 k步派生： S?*yAγ?yaηγ=xα 其中 y∈ Ｖ Ｔ *, A∈ Ｖ Ｎ ， γ,η∈ Ｖ Ｎ *， a∈ Ｖ Ｔ ， ya=x， α=ηγ。 由前 k1步派生 S?*yAγ推出的句型，是由 S推導(dǎo)出的前面是 終極符串 y的句型。由假設(shè)⑵得， M中有(q,ya,S)├ *(q,a,Aγ)， 即當(dāng) M識別完 y之后，棧內(nèi)符號串為 Aγ。 再看看 G的第 k步派生：此派生是應(yīng)用產(chǎn)生式 A?aη。 由 δ的定義得 M中有動作： δ(q,a,A)中含有 (q,η)， 于是 M有如下的 ID變換： (q,ya,S)├ *(q,a,Aγ)├ (q,ε,ηγ)=(q,ε,α)， 即 (q,x,S)├ *(q,ε,α)， 必要性成立。 最后得結(jié)論： G中有最左派生 S?*xα， 當(dāng)且僅當(dāng) M中有 (q,x,S)├ *(q,ε,α)。 為了完成本定理的證明，只要令上述結(jié)論中 α＝ ε時， 則得： G中一個最左派生 S ?*x， 當(dāng)且僅當(dāng) M中有 (q,x,S)├ *(q,ε,ε)。 于是得： x∈ L(G)， 當(dāng)且僅當(dāng) x∈ N(M)。 所以 N(M)=L(G)。 3． 由 PDA 轉(zhuǎn)換成 CFG 定理 PDA M使得 N(M)=L， 則 L是 CFL。 證明 ：令 M=(K,Σ,Γ,δ,q0,Z0,Φ)， N(M)=L。 構(gòu)造一個 CFG G =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ,S)， 其中 Ｖ Ｎ ＝ {[q,A,p]|q,p∈ K,A∈ Γ}∪ {S} Ｖ Ｔ ＝ Σ P中產(chǎn)生式有三種類型： 1． 對任何 q∈ K,有 S?[q0,Z0,q]。 2． 對 K中任何 q,q1,q2,…,qm,qm+1=p， 任何 a∈ Σ∪ {ε}， 任何 A,B1,B2,…,Bm∈ Γ， 只要 δ(q,a,A)中含有 (q1,B1B2…Bm)， 則有產(chǎn)生式 [q,A,p]?a[q1,B1,q2][q2,B2,q3]…[qm,Bm,p]。 3． 對 任何 q,p∈ K， 任何 a∈ Σ∪ {ε},任何 A∈ Γ， 如果有 δ(q,a,A)中含有 (p,ε)， 則有產(chǎn)生式 [q,A,p]?a 。 按照上述規(guī)則得到的產(chǎn)生式，有時需要進(jìn)行簡化，去 掉無用的產(chǎn)生式，去掉引起推導(dǎo)死循環(huán)進(jìn)而無法推出終 極符串的產(chǎn)生式。 可以證明 L(G)=L。（ 證明從略 ） 為了清楚地了解上述規(guī)則，以及看看 CFG G文法是如 何模擬 PDA M的，下面舉例說明。 【例 】 給定 PDA M=({q0,q1},{0,1},{X,Z0},δ,q0,Z0,Φ) δ：⑴ δ(q0,0,Z0)={(q0,XZ0)} ⑵ δ(q0,0,X)={(q0,XX)} ⑶ δ(q0,1,X)={(q1,ε)} ⑷ δ(q1,1,X)={(q1,ε)} ⑸ δ(q1,ε,Z0)={(q1,ε)} M: 讀一個 0，一個 X入棧 。 讀一個 1，一個 X退棧。 當(dāng) X都退出后，再退掉 Z0， 棧為空，接收輸入符號串。 所以 M識別的語言 L=T(M)={0i1i|i≥1}。 求一個 CFG G， 使得 L(G)=L。 解 . 令 G =(Ｖ Ｎ ,Ｖ Ｔ ,Ｐ ,S) Ｖ Ｔ ={0,1} Ｖ Ｎ ＝ {S,[q0,Z0,q0],[q0,Z0,q1],[q1,Z0,q0],[q1,Z0,q1], [q0,X,q0],[q0,X,q1], [q1,X,q0], [q1,X,q1]} Ｐ構(gòu)成