【正文】 解 . 令 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)成。 所以 M識別的語言 L=T(M)={0i1i|i≥1}。 讀一個 1，一個 X退棧。（ 證明從略 ） 為了清楚地了解上述規(guī)則，以及看看 CFG G文法是如 何模擬 PDA M的，下面舉例說明。 按照上述規(guī)則得到的產(chǎn)生式，有時需要進行簡化，去 掉無用的產(chǎn)生式，去掉引起推導(dǎo)死循環(huán)進而無法推出終 極符串的產(chǎn)生式。 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]。 證明 ：令 M=(K,Σ,Γ,δ,q0,Z0,Φ)， N(M)=L。 所以 N(M)=L(G)。 為了完成本定理的證明，只要令上述結(jié)論中 α＝ ε時， 則得： G中一個最左派生 S ?*x， 當且僅當 M中有 (q,x,S)├ *(q,ε,ε)。 由 δ的定義得 M中有動作： δ(q,a,A)中含有 (q,η)， 于是 M有如下的 ID變換： (q,ya,S)├ *(q,a,Aγ)├ (q,ε,ηγ)=(q,ε,α)， 即 (q,x,S)├ *(q,ε,α)， 必要性成立。由假設(shè)⑵得， M中有(q,ya,S)├ *(q,a,Aγ)， 即當 M識別完 y之后，棧內(nèi)符號串為 Aγ。 ⑶ 若 G中有 k步派生： S?*yAγ?yaηγ=xα 其中 y∈ Ｖ Ｔ *, A∈ Ｖ Ｎ ， γ,η∈ Ｖ Ｎ *， a∈ Ｖ Ｔ ， ya=x， α=ηγ。 結(jié)論成立。 ⑴ 如果 G中此派生是由 0步完成的，則此派生為： S?S ， 令 x=ε,α=S， 所以此派生也可以寫成 S?xα。 2．必要性 。 下面通過分析 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α 。 ⑵ 假設(shè) (q,y,S)├ *(q,ε,β)是由少于 k個動作完成，則文法 G中有派生： S?* yβ(這里 x=y, α=β)。已知 M中有 (q,x,S)├ *(q,ε,α)， 對 M的動作次 數(shù)歸納，證出 G中有最左派生 S?*xα 。即用歸納法證明如下結(jié)論： G中最左派生 S?*xα， 當且僅當 M中有 (q,x,S)├ *(q,ε,α)。由于 G具有 GNF形式，所以 G 的最左派生中的每個句型都是 xα形式，其中 x∈ Ｖ Ｔ +， α∈ Ｖ Ｎ *。 構(gòu)造 PDA M＝ ({q},Ｖ Ｔ ,Ｖ Ｎ ,δ,q,S,Φ) 其中 δ中動作確定：如果 A?aγ∈ P， 則有 δ(q,a,A)中含有 (q,γ)， a∈ Ｖ Ｔ ， γ∈ Ｖ Ｎ *。 定理 L是 CFL， 則存在 PDA M， 使得 N(M)=L。從這里看 出 PDA M是模擬 G的最左派生的。 下面驗證一下它接收的語言與 G產(chǎn)生的語言是相同的， 并看一看 M是如何模擬 G的派生的。 由 A?0 得： δ (q,0,A)={(q,ε )}。 因而，由 S?0SA|0A 得： δ (q,0,S)={(q,SA),(q,A)}。 解 ： 1． 先將 G變成 GNF形式的 G’， 得 G’=({S,A,B},{0,1},P’,S) P’： S?0SA|1SB|0A|1B , A?0, B?1。 【例 】 給定 CFG G=({S},{0,1},P,S)， 其中 P： S?0S0|1S1|00|11。 2． 由 CFG 轉(zhuǎn)換成 PDA 下面介紹根據(jù)給定的 CFG G， 求接收 L(G)的 PDA M。 從這個定理看到， PDA的兩種接收語言的方式可以互相 轉(zhuǎn)換。 (這里不作詳細證明 )。 4） 對任何 X∈ ?！?{Z0}, δ(qe,ε,X)={(qe,ε)} 使得 M反復(fù)清棧，直至棧內(nèi)為空。 2） 對任何 q∈ K, 任何 a∈ Σ∪ {ε}, 任何 X∈ Γ, δ(q,a,X)=δ’(q,a,X) 使得 M模擬 M’的所有動作。 M要接收 w， 必須能夠從它的開始 ID（ q0,w,Z0） 進入 M’ 的開始 ID（ q0’,w,Z0’）， 以后能夠模擬 M’的所有動作， 達到 M’的終了時的 ID（ q,ε,γ）， 最后進入 M的清棧狀 態(tài) qe， 再進行清棧，使棧內(nèi)為空。 構(gòu)造 M=(K∪ {q0,qe},Σ,?！?{Z0},δ,q0,Z0,Φ)， 其中 q0,qe?K， Z0?Γ。故有 T(M’)=N(M)。 根據(jù)上面分析，可以看到：任何 w∈ N(M)， 必有 w∈ T(M’)， (這里不作詳細證明 )。 2） 對任何 q∈ K， 任何 a∈ Σ∪ {ε}， 任何 X∈ Γ, δ’(q,a,X)=δ(q,a,X) 這類動作使得 M’模擬 M的所 有動作。 假設(shè) M接收句子 w， 即 w∈ N(M)， 則 M必有如下 ID變換： M： (q0,w,Z0)├* (q,ε,ε) 其中 q∈ K M’要接收 w， 必須能夠從它的開始 ID（ q0’,w,Z0’） 進入 到 M的開始 ID（ q0,w,Z0）， 以后 M’就能夠模擬 M的所有 動作，當達到 M的終止時的 ID（ q,ε,ε） 時，最后進入 M’的終止狀態(tài) qf， 從而接收 w。 證明 ： 1．必要性 ：設(shè) M=(K,Σ,Γ,δ,q0,Z0,Φ)， 用空棧 接收語言 L， N(M)=L。 在介紹它們相互轉(zhuǎn)換之前，先介紹 PDA的兩種接收語 言方式可以互相轉(zhuǎn)換。 (q1,110011,R) ┣ ⑽ (q2,110011,ε) ┳ ⑵ (q1,10011,GR) ┣ ⑹ (q2, 0011,R) ┣ ⑼ (q2, 0011,ε) ┳ ⑵ (q1,0011,GGR) ┳ ⑸ (q1,011,BGGR)┣ ⑶ (q2,11,GGR)┣ ⑻ (q2,1,GR) ┳ ⑶ ┳ ⑻ (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ù)相等 }。因此當連續(xù)讀的兩個符號 相同時，就有兩種可能：一種情況是這兩個符號都是 w中 的符號，此時狀態(tài)不變；另一種情況是前一個符號是 w末 尾的符號，而后一個符號是 wR的第一個符號，此時就要 改變狀態(tài)。 ⑶ 問題是：如何判斷 w與 wR的分界線。 2． ⑴ 當 讀左半邊的符號串 w時， M是在 q1狀態(tài)，這時 如果讀 0，則向棧內(nèi)壓入符號 B； 如果讀 1，則向棧內(nèi)壓入符號 G。 解 ： 設(shè)計的思想是 ： PDA M 有兩個狀態(tài) K={q1,q2}， 有三 個棧內(nèi)符號，即 Γ＝ {R,B,G}。 7.【 例 】 設(shè)計一個 PDA M ， 使之接收語言 L如下： L={wwR|w∈ {0,1}*}， 例如 01011010∈ L。 這相當于是個確定的 PDA。 后面我們將證明這兩種接收方式可以互相轉(zhuǎn)換 。 上例中 M識別 0011c1100時， ID的變化過程： (q1,0011c1100,R)├ (q1,011c1100,BR)├ (q1,11c1100,BBR)├ (q1,1c1100,GBBR)├ (q1,c1100,GGBBR)├ (q2,1100,GGBBR)├ (q2,100,GBBR)├ (q2,00,BBR)├ (q2,0,BR)├ (q2,ε,R)├ (q2,ε,ε) 接收 0011c1100。 如上例中 （ q1,0011c1100,R） ├ （ q1, 011c1100,BR） ├ （ q1,11c1100,BBR） ├ （ q1,1c1100,GBBR） ├ （ q1,c1100,GGBBR） ├ （ q2,1100,GGBBR） 可以寫成 (q1,0011c1100,R)├ *(q1,1100,GGBBR)。 例如 上 例中有 ID0├ ID1， 即 （ q1,0011c1100,R） ├ （ q1, 011c1100,BR）。 例如上例中，當帶上符號串為 0011c1100時， 開始的 ID0：（ q1,0011c1100,R）， 當讀完第一個 0后，變成 ID1：（ q1,011c1100,BR）。 5． PDA的瞬間描述 ID (Instantaneous Description ) PDA M的當前格局，稱之為 M的瞬間描述 ID。 當帶上符號串都讀完后，棧內(nèi)為空，就說明帶上符號 串正是 L中的句子。具體動作如下表所示： 棧頂 當前 輸 入 符 號 符號 狀態(tài) 0 1 c B q1 B入棧 ， 狀態(tài)為 q1 G入棧 ， 狀態(tài)為 q1 狀態(tài)改成 q2 q2 G q1 B入棧 ， 狀態(tài)為 q1 G入棧 ， 狀態(tài)為 q1 狀態(tài)改成 q2 q2 R q1 B入棧 ， 狀態(tài)為 q1 G入棧 ， 狀態(tài)為 q1 狀態(tài)改成 q2 q2 退棧頂 ， 狀態(tài)為 q2 － － － 退棧頂 ， 狀態(tài)為 q2 － 如果帶上無符號可讀，則退棧頂 R， 否則，無動作。 0 1 0 1 c 1 0 1 0 入 棧 q1 出 棧 q2 這樣，當帶上符號都讀完時，棧內(nèi)應(yīng)該是符號 R。 3).當讀符號 c時，狀態(tài)變成 q2。 2).當讀 c左邊的符號時， M是在 q1狀態(tài)，此時 如果讀 0，則向棧內(nèi)壓入符號 B； 如果讀 1，則向棧內(nèi)壓入符號 G。 解 ： 設(shè)計的思想是 ： PDA M 有兩個狀態(tài)，即 K={q1,q2}， 有三個棧內(nèi)符號，即 Γ＝ {R,B,G}。 4） 用希臘字母 α、 β、 γ…表示棧內(nèi)符號串， 即 α,β, γ,…∈ Γ*。 2） 用小寫英文字母 x、 y、 z…表示輸入帶上帶符號串，即 x,y,z,…∈ ∑*。 注意 ：假設(shè)棧內(nèi)符號串 γ從底到頂依次是 ABCD， 則 γ 要寫成 DCBA, 即棧頂符號寫在左邊，棧底符號寫在右邊。 （ 2） ε 動作， 一般用于讀帶上符號串的開頭或者是末尾。 有兩種狀態(tài)轉(zhuǎn)移函數(shù)： （ 1）掃描輸入帶上符號 a， δ(q,a,Z)={(p1,γ1),(p2,γ2),…,(pm,γm)}， 其中 q∈ K， a∈ Σ， Z∈ Γ， p1,p2,…,pm∈ K, γ1,γ2,…,γm∈ Γ*。 F—— F?K， 終止狀態(tài)集合。 q0—— q0∈ K， 開始狀態(tài)。 Σ—— 輸入帶上的符號集合。 兩個只讀頭 ： 分別用來讀取 帶上符號和棧內(nèi)符號 。 有限控制器 ： 存放 PDA的狀態(tài)轉(zhuǎn)移函數(shù)。 下推自動機 (Push Down Automaton, PDA) 下面介紹識別 CFL的自動機 ——下推自動機。 例如 ， 看看它們派生 00100100的過程 。令 G’=({S,A,B},{0,1},P’,