7形式語(yǔ)言與自動(dòng)機(jī)-2015-下推自動(dòng)機(jī)

1、形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī)Formal Languages and Automata Theory胡春明胡春明 鄧婷鄧婷 趙永望趙永望第第七七章章 下推自動(dòng)機(jī)下推自動(dòng)機(jī)2第七章第七章 下推自動(dòng)機(jī)下推自動(dòng)機(jī) 下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）下推自動(dòng)機(jī)的構(gòu)造下推自動(dòng)機(jī)的構(gòu)造PDA 兩種接受語(yǔ)言方式的等價(jià)兩種接受語(yǔ)言方式的等價(jià)確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)（DPDA）PDA 與與 CFG 等價(jià)等價(jià)第七章第七章 下推自動(dòng)機(jī)下推自動(dòng)機(jī)正則文法與有窮狀態(tài)自動(dòng)機(jī)正則文法與有窮狀態(tài)自動(dòng)機(jī) 例：構(gòu)造與給定右正則文法等價(jià)的例：構(gòu)造與給定右正則文法等價(jià)的 FA。M=(Q, , , q0, F, ),Q

2、=E, A, B, C, Z =0,1 (E, 0)=A, (E, 1)=B, (A, 1)=Z, (A,1)=C, (B, 0)=Z, (B, 0)=C, (C, 0)=B, (C, 1)=A F=Z文法及機(jī)器：文法及機(jī)器：有有窮狀態(tài)自動(dòng)機(jī)窮狀態(tài)自動(dòng)機(jī)(FA) - 正則語(yǔ)言正則語(yǔ)言(RL)下推自動(dòng)機(jī)下推自動(dòng)機(jī)(PDA) - 上下文無關(guān)語(yǔ)言上下文無關(guān)語(yǔ)言(CFL)上下文無關(guān)文法與下推自動(dòng)機(jī)上下文無關(guān)文法與下推自動(dòng)機(jī)（ PDA ）PDA提出的思路：提出的思路： 對(duì)于對(duì)于CFG, 當(dāng)它是當(dāng)它是GNF的時(shí)候的時(shí)候, 派生總是從左往右進(jìn)行派生總是從左往右進(jìn)行, 而且右邊變量而且右邊變量后綴的長(zhǎng)度是不定

3、的后綴的長(zhǎng)度是不定的,想用有窮狀態(tài)來表示這些后綴不一定總是可能的。想用有窮狀態(tài)來表示這些后綴不一定總是可能的。 按照最左派生來分析句子的情況下按照最左派生來分析句子的情況下,可以考慮用可以考慮用棧棧來保存來保存A a, A aA1A2 Am 定義定義 6 - 12： 如果如果 CFG G =（V, T, P, S）中所有產(chǎn)生式都有如下形式：）中所有產(chǎn)生式都有如下形式：A a ，其中，其中， A V ，a T， V ，則則 G 被稱為格雷巴赫范式（被稱為格雷巴赫范式（ GNF ）AmA2A1PDA 裝置模型裝置模型PDA的動(dòng)作的動(dòng)作 在有窮狀態(tài)控制器的控制下根據(jù)它的在有窮狀態(tài)控制器的控制下根據(jù)它

4、的當(dāng)前狀態(tài)、棧頂當(dāng)前狀態(tài)、棧頂符號(hào)、以及輸入符號(hào)符號(hào)、以及輸入符號(hào)作出相應(yīng)的作出相應(yīng)的動(dòng)作動(dòng)作有時(shí)有時(shí),不不需要考慮輸入需要考慮輸入符號(hào)符號(hào)為何為何稱下稱下推自推自動(dòng)機(jī)？動(dòng)機(jī)？存放輸入符號(hào)串存放輸入符號(hào)串的的輸入帶輸入帶存放文法符號(hào)的存放文法符號(hào)的棧棧有窮狀態(tài)有窮狀態(tài)控制器控制器格雷巴赫范式：格雷巴赫范式：S 2 | 0SA | 1SB A 0 B 1接受串：接受串：110020011S 1SB 11SBB 110SABB 1100SAABB 11002AABB 110020ABB 100200BB 11002001B 110020011PDA 裝置執(zhí)行過程舉例裝置執(zhí)行過程舉例SBSBBSBB

5、ASBBAABBABBBBBAAS最左派生 定義定義 7-1：下推自動(dòng)機(jī)：下推自動(dòng)機(jī)(pushdown automaton, PDF) 是一個(gè)七元組是一個(gè)七元組 M = ( Q, , , , q0, Z0, F ), 其中其中 Q: 狀態(tài)的非空有窮集合；狀態(tài)的非空有窮集合； : 輸入字母表；輸入字母表； : 棧字母表；棧字母表； q0: 初始狀態(tài)初始狀態(tài), （ q0 Q） ； Z0: 開始符號(hào)開始符號(hào) 或?；驐５椎追?hào)符號(hào),（ Z0 ）； F: 終止?fàn)顟B(tài)終止?fàn)顟B(tài)集合集合, F Q; : 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù),Q ( ) 2Q * 。對(duì)于對(duì)于 ( q, a , Z ) Q ( ) 1、 (

6、q, a, Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) 2、 ( q, , Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) 下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）1、 ( q, a, Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) 在在狀態(tài)狀態(tài) q下下, 棧棧頂符號(hào)為頂符號(hào)為 Z, 讀入讀入字符字符 a 時(shí)時(shí), M 可選擇將狀態(tài)可選擇將狀態(tài)變?yōu)樽優(yōu)?pi （i =1, 2, , m,） 棧棧頂符號(hào)頂符號(hào) Z 彈彈出出,將將 i 中的符號(hào)中的符號(hào)從右到左從右到左依此壓入依此壓入棧棧, 將將讀頭向右移

7、動(dòng)一個(gè)讀頭向右移動(dòng)一個(gè)字符字符, 指向指向輸入串的下一個(gè)字符輸入串的下一個(gè)字符。 下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）-狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)約定：約定： 1） i 的最左邊符號(hào)被置于棧的最高位置；最右符號(hào)在最低位置上的最左邊符號(hào)被置于棧的最高位置；最右符號(hào)在最低位置上。 2）在一個(gè)動(dòng)作中不允許同時(shí)選擇狀態(tài)在一個(gè)動(dòng)作中不允許同時(shí)選擇狀態(tài) pi 和符號(hào)串和符號(hào)串 j , i j。piq aaZ i i= bcdbcd 2、 ( q, , Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) M 進(jìn)行一次空移動(dòng)進(jìn)行一次空移動(dòng)：狀態(tài)：狀態(tài)為為 q, 棧頂符號(hào)為棧頂符號(hào)為Z

8、時(shí)時(shí)未未對(duì)任何輸入字符進(jìn)行對(duì)任何輸入字符進(jìn)行掃描掃描,也也可選擇將狀態(tài)變?yōu)榭蛇x擇將狀態(tài)變?yōu)?pi ( i=1, 2, , m)將將棧頂符號(hào)棧頂符號(hào) Z 彈彈出出,將將 i 中的符號(hào)從右到左依此壓入中的符號(hào)從右到左依此壓入棧棧,輸入輸入頭不向頭不向前移動(dòng)。前移動(dòng)。 約定：約定： 1） i 最左邊符號(hào)被置于棧的最高位置；最右符號(hào)在最低位置上。最左邊符號(hào)被置于棧的最高位置；最右符號(hào)在最低位置上。 2）在一個(gè)動(dòng)作中不允許同時(shí)選擇狀態(tài)）在一個(gè)動(dòng)作中不允許同時(shí)選擇狀態(tài) pi 和和 符號(hào)串符號(hào)串 j , i j。下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）-狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)piq aaZ i下推自動(dòng)機(jī)（下推

9、自動(dòng)機(jī)（ PDA ）約定約定 - 按以下方式規(guī)定按以下方式規(guī)定 PDA 中符號(hào)：中符號(hào)：英文字母較前面的英文字母較前面的小寫字母小寫字母,如如 a,b,c,表示表示輸入符號(hào)輸入符號(hào)；英文字母較后面英文字母較后面的小寫字母的小寫字母,如如 x,y,z,表示表示輸入符號(hào)串輸入符號(hào)串;英文字母表的英文字母表的大寫字母大寫字母,如如 X, Y, Z, , 表示堆棧中符號(hào)表示堆棧中符號(hào);西臘字母西臘字母 , , ,表示表示堆棧中符號(hào)串堆棧中符號(hào)串。2、空動(dòng)作（稱為空動(dòng)作（稱為 動(dòng)作動(dòng)作 - 沒有輸入符號(hào)）沒有輸入符號(hào)）： ( q2, , R ) = ( q2, ) 1、非空動(dòng)作非空動(dòng)作（有輸入符號(hào)）有輸

10、入符號(hào)）： ( q1, 0, R ) = ( q1, BR ) ( q1, c, R ) = ( q2, R ) ( q1, 0, B ) = ( q1, ) ( q1, 0, ) = ( q1, R ) 把把R壓進(jìn)壓進(jìn)棧頂棧頂下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）彈出棧頂符號(hào)彈出棧頂符號(hào) R, BR 壓入棧壓入棧 改變控制器改變控制器狀態(tài)狀態(tài)彈彈棧棧彈棧。彈棧。下推自動(dòng)機(jī)多種轉(zhuǎn)移動(dòng)作舉例：下推自動(dòng)機(jī)多種轉(zhuǎn)移動(dòng)作舉例：PDA 的兩個(gè)基本概念：的兩個(gè)基本概念： 1、瞬時(shí)描述；、瞬時(shí)描述； 2、PDA 接受的句子方式接受的句子方式下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）定義定義 7 - 2： 設(shè)設(shè) PD

11、A M = ( Q, , , , q0, Z0, F ), ( q, w, ) ( Q, *, *) 稱為稱為 M 的一的一個(gè)即時(shí)描述個(gè)即時(shí)描述 (instantaneous description, ID),下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）lq是控制器的當(dāng)前狀態(tài)是控制器的當(dāng)前狀態(tài)lw 是當(dāng)前尚未處理的輸入字符串是當(dāng)前尚未處理的輸入字符串。 M 在狀態(tài)在狀態(tài) q 下下,正注正注 視視輸入字符串輸入字符串 w 的首的首字符字符,l棧棧中符號(hào)串為中符號(hào)串為 , 的的最左最左符號(hào)為棧頂符號(hào)為棧頂符號(hào)符號(hào), 最最右符號(hào)為棧底右符號(hào)為棧底符號(hào)符號(hào),較左的符號(hào)在棧的較上面較左的符號(hào)在棧的較上面, 較右

12、的符號(hào)在棧的較下面較右的符號(hào)在棧的較下面qab = bcdcdbcw = abc下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）：）：即時(shí)轉(zhuǎn)移描述即時(shí)轉(zhuǎn)移描述(1) 如果如果（p, ） （ q, a, Z ）, 且且M 在狀態(tài)在狀態(tài) q, 棧棧頂為頂為 Z,讀讀 入入 a 時(shí)時(shí) , 選擇選擇進(jìn)入狀態(tài)進(jìn)入狀態(tài) p, 用用 替換棧頂替換棧頂 Z, 讀讀頭指向頭指向 w 的的首首字符字符,記記為：為： （q, aw, Z ） （p, w, ）此時(shí)此時(shí), M 做了一次做了一次非空非空移動(dòng)移動(dòng),其其 ID 由由（ q, aw, Z ）變?yōu)樽優(yōu)?（p, w, ）。Mpq aaZ w =bcde b c d e b c

13、 d e(2) 如果如果（p, ） （ q, , Z ）, 表示當(dāng)前表示當(dāng)前 M 在狀態(tài)在狀態(tài) q,棧棧頂為頂為 Z時(shí)時(shí),不不讀讀字符字符,選擇選擇進(jìn)入狀態(tài)進(jìn)入狀態(tài) p,用用 替換棧頂替換棧頂 Z,讀讀頭位頭位置置不變不變,記記為：為： （q, w, Z ） （p, w, ）此時(shí)此時(shí), M 做了一次做了一次空空移動(dòng)移動(dòng), 其其 ID 由（由（ q, w, Z ） 變?yōu)樽優(yōu)?（p, w, ）。）。Mpq aaZ w=abcde b c d e b c d e下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）:瞬時(shí)轉(zhuǎn)移序列描述瞬時(shí)轉(zhuǎn)移序列描述（ q1, w1, 1 ） （qn, wn, n ）：）：表示表示 M

14、 的的 ID 從（從（ q1, w1, 1 ）出發(fā)出發(fā), 經(jīng)過經(jīng)過 n 次次移動(dòng)移動(dòng), 變?yōu)樽優(yōu)?(qn, wn, n ), 亦即亦即, 存在存在一個(gè)一個(gè) ID 序列：序列： （ q1, w1, 1 ） （ q2, w2, 2） . （qn, wn, n ）其中其中, 對(duì)于對(duì)于字符串字符串 w1, w2, wn, 當(dāng)當(dāng) i j 時(shí)時(shí), w j 是是 w i 的后綴的后綴。nMMMM下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）:特殊的瞬時(shí)轉(zhuǎn)移序列描述特殊的瞬時(shí)轉(zhuǎn)移序列描述 這里這里,1、字符串、字符串 x 是是w 的后綴；的后綴；（ q, w, ） （ p, x, ）：）：表示表示 M 的的 ID 從（

15、從（ q, w, ）出出發(fā)發(fā), 經(jīng)過經(jīng)過若干次（包含零次）若干次（包含零次）移動(dòng)移動(dòng),變成變成（ p, x, ）M（ q, w, ） （ p, x, ）：）：表示表示 M 的的 ID 從（從（ q, w, ）出發(fā)出發(fā),經(jīng)經(jīng)過過至少一次至少一次移動(dòng)移動(dòng),變成變成（ p, x, ）+Mn2、意義清楚、意義清楚時(shí)時(shí),可可省去省去 ID 推導(dǎo)符中的推導(dǎo)符中的 M, 分別分別記為：記為：兩個(gè)基本概念：兩個(gè)基本概念： 1、PDA 的瞬時(shí)描述；的瞬時(shí)描述； 2、PDA 接受的句子方式接受的句子方式下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）定義定義 7 - 3： 設(shè)有設(shè)有PDA

16、M=(Q, , , , q0, Z0, F ), 則則M具有具有兩種接受語(yǔ)言的兩種接受語(yǔ)言的方式方式: 1、用、用終態(tài)方式終態(tài)方式接受接受語(yǔ)言語(yǔ)言, 定義定義為：為： L(M)= w | ( q0, w, Z0 ） ( p, , ) 且且 p F ； * 2、 用用空棧方式空棧方式接受接受語(yǔ)言語(yǔ)言,定義定義為：為： N(M)= w | ( q0, w, Z0） ( p, , ) *到達(dá)終止?fàn)顟B(tài),棧不一定為空棧為空,不一定到達(dá)終止?fàn)顟B(tài)例：例：構(gòu)造接受語(yǔ)言構(gòu)造接受語(yǔ)言 L = w2wR | w 0,1* 的的 PDA。二、下推自動(dòng)機(jī)的構(gòu)造二、下推自動(dòng)機(jī)的構(gòu)造解：解：1、構(gòu)造產(chǎn)生、構(gòu)造產(chǎn)生 L 的的

17、 CFG G1：S 0S0 | 1S1 | 2。 2、將文法、將文法 G1 轉(zhuǎn)換成轉(zhuǎn)換成格雷巴赫范式格雷巴赫范式（ GNF ） G2： S 0SA | 1SB | 2 A 0 B 1根據(jù)根據(jù) GNF 定義各種識(shí)別語(yǔ)言定義各種識(shí)別語(yǔ)言 L 的的 PDA 。解解1：構(gòu)造空棧方式接受語(yǔ)言的：構(gòu)造空棧方式接受語(yǔ)言的 PDA G2： S 0SA | 1SB | 2A 0B 1派生派生產(chǎn)生規(guī)則產(chǎn)生規(guī)則M應(yīng)該完成的動(dòng)作應(yīng)該完成的動(dòng)作S0SAS0SA從從q0啟動(dòng)啟動(dòng),讀入讀入0,將將S彈出棧彈出棧,將將SA壓入棧壓入棧,狀態(tài)不變狀態(tài)不變01SBAS1SB在狀態(tài)在狀態(tài)q0,讀入讀入1,將將S彈出棧彈出棧,將將S

18、B壓入棧壓入棧,狀態(tài)不變狀態(tài)不變 010SABA S0SA在狀態(tài)在狀態(tài)q0,讀入讀入0,將將S彈出棧彈出棧,將將SA壓入棧壓入棧,狀態(tài)不變狀態(tài)不變0102ABA A0在狀態(tài)在狀態(tài)q0,讀入讀入2,將將S彈出棧彈出棧,將將壓入棧壓入棧,狀態(tài)不變狀態(tài)不變01020BAB1在狀態(tài)在狀態(tài)q0,讀入讀入0,將將A彈出棧彈出棧,將將壓入棧壓入棧,狀態(tài)不變狀態(tài)不變010201AA0在狀態(tài)在狀態(tài)q0,讀入讀入1,將將B彈出棧彈出棧,將將壓入棧壓入棧,狀態(tài)不變狀態(tài)不變0102010在狀態(tài)在狀態(tài)q0,讀入讀入0,將將A彈出棧彈出棧,將將壓入棧壓入棧,狀態(tài)不變狀態(tài)不變模擬模擬 PDA M1識(shí)別句子識(shí)別句子 0102

19、010 過程：過程：1(q0,0,S)=(q0,SA)1(q0,1,S)=(q0,SB)1(q0,0,S)=(q0,SA)1(q0,2,S)=(q0,)1(q0,0,A)=(q0,)1(q0,1,B)=(q0,)1(q0,0,A)=(q0,)G2： S 0SA | 1SB | 2A 0B 1解解1：構(gòu)造空棧方式接受語(yǔ)言的：構(gòu)造空棧方式接受語(yǔ)言的 PDA PDA 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)

20、=(q0,)N ( M1 ) = L；空棧標(biāo)志：；空棧標(biāo)志：( q0, , ) 根據(jù)最左派生過程定義狀態(tài)轉(zhuǎn)移：根據(jù)最左派生過程定義狀態(tài)轉(zhuǎn)移：當(dāng)對(duì)應(yīng)的文法變量派生出一個(gè)字符當(dāng)對(duì)應(yīng)的文法變量派生出一個(gè)字符時(shí)時(shí),相應(yīng)的相應(yīng)的PDA讀入這個(gè)字符讀入這個(gè)字符,并將棧并將棧頂符號(hào)換成相應(yīng)產(chǎn)生式右部除了首頂符號(hào)換成相應(yīng)產(chǎn)生式右部除了首字符之外的后綴字符之外的后綴解解2-1：構(gòu)造終態(tài)方式接受語(yǔ)言的構(gòu)造終態(tài)方式接受語(yǔ)言的PDA。 PDA M2 = ( q0, q1, 0 , 1, 2 , S, A, B, Z, Z0 , 2, q0, Z0, q1 )L(M2)= L ；結(jié)束標(biāo)志結(jié)束標(biāo)志：終態(tài)終態(tài) -（qf ,

21、 , ）實(shí)際上實(shí)際上 = L = w2wR | w 0,1* 設(shè)計(jì)思路：設(shè)計(jì)思路：在空棧接受方式下在空棧接受方式下,當(dāng)棧空了當(dāng)?？樟?字符串字符串又正好識(shí)別完畢又正好識(shí)別完畢,讓它進(jìn)入終止態(tài)讓它進(jìn)入終止態(tài)2(q1, ,Z0)=(q0,SZ)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,Z)=(qf,)其中其中, q1初始態(tài)初始態(tài)； q0工作態(tài)；工作態(tài)；qf- 終止態(tài)終止態(tài)；棧符號(hào)：棧符號(hào)： A-0；B-1； Z 棧底標(biāo)志棧底標(biāo)志, Z0/SZ0, S/SA 1, S/SB2

22、, S/q1q00, A/1, B/qf, Z/G2： S 0SA | 1SB | 2A 0B 1解解2-2：構(gòu)造終態(tài)方式接受語(yǔ)言的構(gòu)造終態(tài)方式接受語(yǔ)言的PDA。 PDA M2 = ( q0, qf, 0, 1, 2 , S, A, B, Z, Z0 , 2, q0, Z0, qf )其中其中, q0工作態(tài)；工作態(tài)；qf- 終止態(tài)終止態(tài)； 棧符號(hào)：棧符號(hào)： A-0；B-1； Z 棧底標(biāo)志棧底標(biāo)志L（M2）= L ；結(jié)束標(biāo)志：終態(tài)結(jié)束標(biāo)志：終態(tài) -（qf , , ）實(shí)際上實(shí)際上 = L = w2wR | w 0,1* 2(q0,0,Z0)=(q0,SAZ)2(q0,1,Z0)=(q0,SBZ)2

23、(q0,2,Z0)=(qf,)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,Z)=(qf,)G2： S 0SA | 1SB | 2A 0B 1BBBBBABBAABBABBBL = w2wR | w 0,1* 回文： 110020011記錄過程匹配過程解解3：將：將 PDA M 工作過程分為工作過程分為兩個(gè)兩個(gè)階段階段, 按按階段劃分狀態(tài)：階段劃分狀態(tài)：設(shè)計(jì)思路：設(shè)計(jì)思路：不考慮不考慮GNF,但從棧但從棧的特性來設(shè)計(jì)的特性來設(shè)計(jì),棧是先入后出的棧是先入后出的0A1B1、讀字

24、符讀字符“2”之前為之前為“記錄記錄”階段階段：M 每讀入一個(gè)每讀入一個(gè)字符字符,則則在棧中做在棧中做一次一次記錄記錄讀讀 “0”, 在在棧中壓入棧符號(hào)棧中壓入棧符號(hào) “A”；讀讀 “1”, 在在棧中壓棧符號(hào)棧中壓棧符號(hào) “B”, 讀讀到到 “2” 時(shí)進(jìn)入符號(hào)匹配階段；時(shí)進(jìn)入符號(hào)匹配階段；解解3：將：將 PDA M 工作過程分為工作過程分為兩個(gè)兩個(gè)階段階段, 按按階段劃分狀態(tài)：階段劃分狀態(tài)：2、讀字符讀字符“2”之后為之后為“匹配匹配”階段階段：每讀一個(gè)：每讀一個(gè)字符字符,則則將其與棧頂符將其與棧頂符號(hào)相號(hào)相匹配匹配 棧棧頂符號(hào)為頂符號(hào)為 “A”,讀讀 “0” - 匹配匹配成功成功,讀讀 “1

25、” - 匹配失敗匹配失??； 棧棧頂符號(hào)為頂符號(hào)為 “B”,讀讀 “1” - 匹配匹配成功成功,讀讀 “0” - 匹配失??；匹配失敗；3、匹配失敗表示匹配失敗表示讀入的字符號(hào)串不是語(yǔ)言的讀入的字符號(hào)串不是語(yǔ)言的句子句子, 此時(shí)此時(shí),可可讓讓 M 停機(jī)停機(jī)或進(jìn)入或進(jìn)入 “陷阱陷阱” 狀態(tài)。狀態(tài)。L = w2wR | w 0,1* 設(shè)計(jì)思路：設(shè)計(jì)思路：不考慮不考慮GNF,但從棧但從棧的特性來設(shè)計(jì)的特性來設(shè)計(jì),棧是先入后出的棧是先入后出的回文的特點(diǎn)：110020011解解3-1：構(gòu)造構(gòu)造空棧方式空棧方式接受語(yǔ)言的接受語(yǔ)言的 PDA M3 = ( q0, q1, q2 , 0, 1, 2 , A, B,

26、 Z0 , 3 , q0, Z0, )其中其中, 狀態(tài)狀態(tài)定義：定義： q0：開始：開始狀態(tài)狀態(tài) ; q1：記錄狀態(tài)；：記錄狀態(tài)； q2： 匹配狀態(tài)。匹配狀態(tài)。 棧符號(hào)：棧符號(hào)：A - 0；B - 1；Z0 -棧底符號(hào)棧底符號(hào)N(M3)= L ；結(jié)束標(biāo)志：（結(jié)束標(biāo)志：（ p, , ） L = w2wR | w 0,1* 3(q0,0,Z0)=(q1,A)3(q0,1,Z0)=(q1,B)3(q0,2,Z0)=(q2,)3(q1,0,A)=(q1,AA)3(q1,1,A)=(q1,BA)3(q1,0,B)=(q1,AB)3(q1,1,B)=(q1,BB)3(q1,2,A)=(q2,A)3(q1,

27、2,B)=(q2,B)3(q2,0,A)=(q2,)3(q2,1,B)=(q2,)記錄階段記錄階段判斷是否讀到字符判斷是否讀到字符2匹配階段匹配階段0A1BL = w2wR | w 0,1* 解解3-2：構(gòu)造構(gòu)造終態(tài)方式終態(tài)方式接受語(yǔ)言的接受語(yǔ)言的 PDA。M4 = ( q0, q1, q2 , qf, qt , 0, 1, 2 , A, B, Z0 , 4 , q0, Z0,qf )其中其中, q0: 初始態(tài)；初始態(tài)； qf: 終態(tài)終態(tài)；qt: 陷阱態(tài)陷阱態(tài) q1: 記錄狀態(tài)；記錄狀態(tài)； q2: 匹配狀態(tài)匹配狀態(tài) 棧符號(hào)：棧符號(hào)：A - 0；B - 1；Z0 初始棧初始棧底底N（M4）= L

28、 ；結(jié)束標(biāo)志：（結(jié)束標(biāo)志：（ qf, , ） 實(shí)際上實(shí)際上 = 4(q0,0,Z0)=(q1, AZ0)4(q0,1,Z0)=(q1, BZ0)4(q0,2,Z0)=(qf, )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,0,B)=(qt, )4(q2,1,B)=(q2, )4(q2,1,A)=(qt, )4(q2,Z0)=(qf, )到達(dá)終止?fàn)顟B(tài)，且棧為空記錄階段記錄階段判斷是否讀到字

29、符判斷是否讀到字符2匹配階段匹配階段第七章第七章 下推自動(dòng)機(jī)下推自動(dòng)機(jī)下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）PDA 兩種接受語(yǔ)言方式的等價(jià)兩種接受語(yǔ)言方式的等價(jià)確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)（DPDA）PDA 與與 CFG 等價(jià)等價(jià)定理定理 7 - 1：對(duì)于任意對(duì)于任意終態(tài)方式終態(tài)方式接受語(yǔ)言接受語(yǔ)言 L 的的 PDA M1,存在存在空棧方式空棧方式接受語(yǔ)接受語(yǔ)言言 L 的的 PDA M2, 使得使得 N (M2) = L(M1)。定理定理 7 - 2：對(duì)于任意對(duì)于任意空棧方式空棧方式接受語(yǔ)言接受語(yǔ)言 L 的的 PDA M1,存在存在終態(tài)終態(tài)方式方式接受語(yǔ)接受語(yǔ)言言 L 的的 PDA M2,

30、 使得使得 L ( M2 ) = N(M1) 。PDA 兩種接受語(yǔ)言方式等價(jià)兩種接受語(yǔ)言方式等價(jià)證明思路證明思路:給定給定M1，構(gòu)造，構(gòu)造M2模擬模擬M1 ： M1與與M2的基本動(dòng)作應(yīng)該是相同的的基本動(dòng)作應(yīng)該是相同的 兩個(gè)問題：兩個(gè)問題： w引導(dǎo)引導(dǎo)M1進(jìn)入終止?fàn)顟B(tài)進(jìn)入終止?fàn)顟B(tài)后后, M1的的棧未棧未空空,此時(shí)此時(shí)M2必須將必須將棧清空；棧清空； M1運(yùn)行中未進(jìn)入運(yùn)行中未進(jìn)入終止?fàn)顟B(tài)終止?fàn)顟B(tài),而而此時(shí)此時(shí)M1的的棧已經(jīng)空棧已經(jīng)空了了, M2要能夠避免出現(xiàn)這種情況時(shí)發(fā)生的誤接受要能夠避免出現(xiàn)這種情況時(shí)發(fā)生的誤接受例：接受例：接受L = w2wR | w 0,1* 的的PDA 定理定理 7 - 1

31、：對(duì)于任意對(duì)于任意終態(tài)方式終態(tài)方式接受語(yǔ)言接受語(yǔ)言 L 的的 PDA M1,存在存在空棧方式空棧方式接受語(yǔ)言接受語(yǔ)言 L 的的 PDA M2, 使得使得 N (M2) = L(M1)。定理定理 7-1 的構(gòu)造證明的構(gòu)造證明 - 步驟步驟 1:設(shè)終態(tài)方式設(shè)終態(tài)方式 PDA M1 = ( Q, , , 1, q01, Z01, F ), 構(gòu)造構(gòu)造空棧方式空棧方式 PDA M2 = ( Q q02 , qe , , Z02 , 2, q02, Z02, ), 其中其中, Q q02 , qe = Z02 = ； 2 模擬轉(zhuǎn)移函數(shù)定義模擬轉(zhuǎn)移函數(shù)定義如下：如下： ( 1 ) 初始化初始化： 2 ( q

32、02, , Z02 ) = ( q01, Z01Z02 ) /轉(zhuǎn)轉(zhuǎn)M1運(yùn)行運(yùn)行 ( 2 ) M2完全模完全模擬擬 M1 的的非空移動(dòng)非空移動(dòng)：對(duì)于：對(duì)于 ( q, a, Z ) Q 2(q, a, Z)=1(q, a, Z) ( 3 ) M2在在非終止?fàn)顟B(tài)下非終止?fàn)顟B(tài)下完全模擬完全模擬M1的空移動(dòng)：對(duì)于的空移動(dòng)：對(duì)于 ( q, Z ) (Q F) , 2 ( q, , Z ) = 1 ( q, , Z ) qe 解決第一個(gè)問題q02 Z02解決第二個(gè)問題定理定理 7-1 的構(gòu)造證明的構(gòu)造證明 - 步驟步驟 1:設(shè)終態(tài)方式設(shè)終態(tài)方式 PDA M1 = ( Q, , , 1, q01, Z01,

33、F ), 構(gòu)造構(gòu)造空棧方式空棧方式 PDA M2 = ( Q q02 , qe , , Z02 , 2, q02, Z02, ), 其中其中, Q q02 , qe = Z02 = ； 2 模擬轉(zhuǎn)移函數(shù)定義模擬轉(zhuǎn)移函數(shù)定義如下如下(續(xù)續(xù))：（4）M1在在終止?fàn)顟B(tài)終止?fàn)顟B(tài)下下, M2除了模擬除了模擬M1的空移動(dòng)外的空移動(dòng)外,還需模擬還需模擬M1的的“接受動(dòng)作接受動(dòng)作”。由于在此動(dòng)作之后。由于在此動(dòng)作之后, M1的?？赡苋匀徊豢盏臈？赡苋匀徊豢?故故M2需要進(jìn)入清棧狀態(tài)。需要進(jìn)入清棧狀態(tài)。 ( q, Z ) F , 2 ( q, , Z ) = 1 ( q, , Z ) ( qe, ) ( 5 )

34、 M1 棧已空棧已空, 并已進(jìn)入終止?fàn)顟B(tài)并已進(jìn)入終止?fàn)顟B(tài), 所以所以, M2進(jìn)入清棧狀態(tài)進(jìn)入清棧狀態(tài)qe,準(zhǔn)備將棧清空準(zhǔn)備將棧清空 qF, 2(q, , Z02)= (qe, ) ( 6) M2完成清棧工作：完成清棧工作： 對(duì)于對(duì)于 Z Z02 , 2 ( qe, , Z ) = ( qe, ) 。 由于由于 q F, 故故根據(jù)根據(jù) M2 構(gòu)造定義構(gòu)造定義 (4,5,6), 有有( q01, x , Z01Z02 ) ( q, , Z02 ) ( qe, , Z02 ) ( qe, , ) 且且 q FM 2M 2M 2根據(jù)根據(jù) M2 構(gòu)造定義構(gòu)造定義 (2, 3, 4) , M2 可模擬可模

35、擬 M1的所有移動(dòng)的所有移動(dòng)操作操作, 故有故有, ( q01, x , Z01Z02 ) ( q, , Z02 ) 且且 q F。同理可證：同理可證： N（M1） L（M2）設(shè)任意字符串設(shè)任意字符串 x L（M1）, 根據(jù)根據(jù) PDA 接受語(yǔ)言接受語(yǔ)言定義定義, 有有 ( q01, x , Z01 ) ( q, , ) 且且 q F。M 1定理定理 7-1 的構(gòu)造證明的構(gòu)造證明 ：步驟步驟 2：求證：求證 L（M1）= N（M2）首先證明：首先證明：L（M1） N（M2）。由由 M2 構(gòu)造定義構(gòu)造定義 (1) ：( q02, x , Z02 ) ( q01, x , Z01Z02 ) ( q

36、e, , ) 即由：即由：( q02, x , Z02 ) ( qe, , ) ,知知 x N ( M2 ), 得：得：L( M2 ) N( M1 ) M 2M2M 2M 2PDA 兩種接受語(yǔ)言方式等價(jià)兩種接受語(yǔ)言方式等價(jià)定理定理 7- 2 的證明思路的證明思路: 給定給定M1是空棧狀態(tài)接受語(yǔ)言是空棧狀態(tài)接受語(yǔ)言, 構(gòu)造構(gòu)造M2以終止?fàn)顟B(tài)接受相同的語(yǔ)言以終止?fàn)顟B(tài)接受相同的語(yǔ)言, 且且L(M1)=L(M2) 只要只要M2發(fā)現(xiàn)發(fā)現(xiàn)M1已將棧彈空就可以進(jìn)入終止?fàn)顟B(tài)已將棧彈空就可以進(jìn)入終止?fàn)顟B(tài)定理定理 7 - 2：對(duì)于任意對(duì)于任意空棧方式空棧方式接受語(yǔ)言接受語(yǔ)言 L 的的 PDA M1,存在存在存在存

37、在終態(tài)方式終態(tài)方式接接受語(yǔ)言受語(yǔ)言 L 的的 PDA M2, 使得使得 L ( M2 ) = N(M1) 。定理定理 7- 2 的構(gòu)造證明的構(gòu)造證明 - 步驟步驟 1:設(shè)空棧方式設(shè)空棧方式 PDA M1 = (Q, , , 1, q01, Z01, ), 構(gòu)造構(gòu)造終態(tài)方式終態(tài)方式 PDA M2 = ( Q q02 , qf , , Z02 , 2, q02, Z02, qf ) , 其中其中,Q q02 , qf = Z02 = ； 2 模擬轉(zhuǎn)移函數(shù)定義模擬轉(zhuǎn)移函數(shù)定義如下：如下： (1) 起始轉(zhuǎn)移狀態(tài)：起始轉(zhuǎn)移狀態(tài)： 2 ( q02, , Z02 ) = ( q01, Z01Z02 )。 (

38、2) 模擬模擬 M1 轉(zhuǎn)移：轉(zhuǎn)移： 對(duì)于對(duì)于 ( q, a, Z ) Q( ) , 2 ( q, a, Z ) = 1 ( q, a, Z ) 。 (3) 模擬結(jié)束：模擬結(jié)束： 若若 M1 棧已空棧已空,則則 M2 轉(zhuǎn)轉(zhuǎn)終態(tài)終態(tài), 2 ( q, , Z02 ) = ( q f, ) 。步驟步驟 2： 求證求證 N ( M1 ) = L（M2）首先求證：首先求證：L（M2） N（M1） 設(shè)設(shè) x L ( M2 ), 根據(jù)根據(jù) M2 的定義以及構(gòu)造的第一個(gè)移動(dòng)的定義以及構(gòu)造的第一個(gè)移動(dòng) ( 1 ) ： ( q02, x , Z02 ) ( qf , , )； ( q02, x , Z02 ) (

39、q01, x , Z01Z02 ) 有：有： ( q02, x , Z02 ) ( q01, x , Z01Z02 ) ( qf , , )； M 2M 2M 2M 2根據(jù)根據(jù) M2 的構(gòu)造的構(gòu)造 ( 3 ), 必有一中間狀態(tài)必有一中間狀態(tài) q Q,此時(shí)?？沾藭r(shí)?？?使得使得, ( q01, x , Z01Z02 ) ( q, , Z02 ) 和和 ( q, , Z02 ) ( qf , , ) 成立。成立。M 2M 2由構(gòu)造由構(gòu)造(2) 知知, M1 移動(dòng)與移動(dòng)與 M2 移動(dòng)移動(dòng)相同相同, 故有故有: ( q01, x , Z01Z02 ) ( q, , Z02 )由于由于 Z02 僅是僅是

40、 M2 的棧的棧底底,與與 M1 的棧的棧無關(guān)無關(guān),故此故此時(shí)應(yīng)有：時(shí)應(yīng)有： 故由故由( q01, x, Z01 ) ( q, , ) 可知可知 x L (M1), 得：得：L（M2） N（M1） M 1M 1同理可證：同理可證： N（M2） L（M1）PDA 兩種接受語(yǔ)言方式等價(jià)兩種接受語(yǔ)言方式等價(jià)第七章第七章 下推自動(dòng)機(jī)下推自動(dòng)機(jī)下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）PDA 兩種接受語(yǔ)言的方式兩種接受語(yǔ)言的方式確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)（DPDA）PDA 與與 CFG 等價(jià)等價(jià)定義定義 7 - 4：確定的確定的 PDA M = ( Q, , , , q0, Z0, F ) 滿足如下條

41、件滿足如下條件:對(duì)于對(duì)于 ( q, a, Z ) Q ,有有| ( q, a, Z ) | + | ( q, , Z ) | 1；確定的確定的 PDA M 簡(jiǎn)記為簡(jiǎn)記為 DPDA M。確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)（DPDA）定義定義 7 4：確定的確定的 PDA M = ( Q, , , , q0, Z0, F ) 滿足如下條件滿足如下條件:1、對(duì)于、對(duì)于 q Q, Z ：若若 ( q, , Z）有有 定義定義, 則則 a , ( q, a, Z ) 無定義；無定義；2、對(duì)于對(duì)于 q Q,Z , a ： ( q, a, Z ) 最多有一個(gè)值；最多有一個(gè)值；則稱則稱 M 為一個(gè)確定的為一個(gè)

42、確定的 PDA M, 簡(jiǎn)記為簡(jiǎn)記為 DPDA M。確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)（DPDA）| ( q, a, Z ) | + | ( q, , Z ) | 1第七章第七章 下推自動(dòng)機(jī)下推自動(dòng)機(jī)下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（ PDA ）PDA 兩種接受語(yǔ)言的方式兩種接受語(yǔ)言的方式確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)（DPDA）PDA 與與 CFG 等價(jià)等價(jià)定理定理 7-3 對(duì)于任意對(duì)于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模擬模擬GNF的最左派生的最左派生(1) 構(gòu)造構(gòu)造PDA。 設(shè)設(shè)L為不含為不含 的的CFL, 根據(jù)定理根據(jù)定理 6-10，存在，存

43、在GNF G=(V,T,P,S), 使使得得L(G)=L(G)。取取 PDA M=(q,T, V, , q, S, )對(duì)于任意的對(duì)于任意的AV, aT,(q, a, A)= (q, )| AaP 也就是說也就是說, (q,) (q, a, A)的充分必要條件是的充分必要條件是AaP。PDA 與與 CFG 等價(jià)等價(jià)GNF的最左派生過程中，變量決定派生如何進(jìn)行，只需要一個(gè)狀態(tài) (q,) (q, a, A) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A aP (q, ) (q, a, A) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A aPa: 輸入輸入A: 棧頂符號(hào)棧頂符號(hào)：壓入棧的符號(hào)串：壓入棧的符號(hào)串定理定理 7-3 對(duì)于任意對(duì)于任意CFL

44、 L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模擬模擬GNF的最左派生的最左派生(2) 證明構(gòu)造的正確性：證明構(gòu)造的正確性：N(M)=L(G)。 施歸納施歸納于于 w 的的長(zhǎng)度長(zhǎng)度n, 證明證明 (q, w, S)Mn (q, , )的充分必要條件為的充分必要條件為Snw。 （必要性）（必要性） (a) 當(dāng)當(dāng)n=1時(shí)，有時(shí)，有(q, a, S)M (q, , )， aT, 且且（q, ） (q, a, S) 根據(jù)根據(jù)的定義，的定義， S a P, 因此因此Sa證明更一般的結(jié)論(q,) (q, a, A)的的充分必要條件是充分必要條件是AaP定理定理 7-3 對(duì)于任

45、意對(duì)于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模擬模擬GNF的最左派生的最左派生(2) 證明構(gòu)造的正確性：證明構(gòu)造的正確性：N(M)=L(G)。 施歸納于施歸納于w的長(zhǎng)度的長(zhǎng)度n, 證明證明 (q, w, S)Mn (q, , )的充分必要條件為的充分必要條件為Snw。（必要性（續(xù)必要性（續(xù) ）（b）假設(shè)結(jié)論對(duì)假設(shè)結(jié)論對(duì)n=k成立成立, 下面下面證明結(jié)論對(duì)證明結(jié)論對(duì)n=k+1成立。成立。 取取w= xa, |x|=k, aT，則有，則有 (q, w, S) = (q, xa, S)Mk (q, a, )M(q, , ) 由由(q, a, )M(q,

46、 , ) 知知，必定存在，必定存在 A V, =A1, = 21， (q, 2) (q, a, A)。即即(q, a, )=(q, a, A1)M (q, , 21) =(q, , ) 彈彈出出A, 壓入壓入2又由又由(q, 2) (q, a, A)得得 A a2 P.再?gòu)脑購(gòu)?q, xa, S)Mk (q, a, ) 得得 (q, x, S)Mk (q, , )，由歸納假設(shè)知由歸納假設(shè)知 S kx , 注意到注意到=A1, 且且A a2P，得，得S kx A1 x a21即即S k+1w。（。（w=xa, =21）故結(jié)論對(duì)故結(jié)論對(duì)k+1成立。由歸納法原理，結(jié)論對(duì)任意成立。由歸納法原理，結(jié)論對(duì)

47、任意n成立。成立。同理可證充分性。同理可證充分性。由由的任意性，知的任意性，知(q, w, S)Mn (q, , )的充分必的充分必要條件為要條件為Snw，即，即N(M)=L(G).定理定理 7-3 對(duì)于任意對(duì)于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模擬模擬GNF的最左派生的最左派生(3)考慮考慮L的情況。的情況。 先先按照按照 (1)的構(gòu)造方法構(gòu)造出的構(gòu)造方法構(gòu)造出PDA M=(q, T, V, , q, S, )，使得，使得N(M)=L。然后然后取取M1=( q,q0, T, VZ, 1, q0, Z, )其中其中, q0q, Z V, 令令

48、 1(q0, , Z) = (q0,), (q,S) ,且對(duì)于且對(duì)于 (a, A)TV，有，有 1(q, a, A)=(q, a, A) ，可證可證N(M)=N(M) 。例：例：構(gòu)造與如下構(gòu)造與如下GNF等價(jià)的等價(jià)的PDA S aT | a T aT | aT | a | b(q, a, S)= (q, T), (q, ) (q, a, T)= (q, T), (q, ) (q, b, T)= (q, T), (q, ) (q, ) (q, a, A)的的充分必要條件是充分必要條件是AaPM=(q, T, V, , q, S, ), 其中其中定理定理 7-4 對(duì)于任意的對(duì)于任意的PDA M,

49、存在存在CFG G使得使得L(G) = N(M) 思路：用思路：用CFG G的派生來模擬相應(yīng)的的派生來模擬相應(yīng)的PDA M的移動(dòng)的移動(dòng)PDA 與與 CFG 等價(jià)等價(jià)q, A a q1, A1A2An（q, A與與q1, A1A2An看成兩個(gè)看成兩個(gè)變量）變量）(q1, A1A2An) (q, a, A) M在狀態(tài)在狀態(tài) q，棧頂符號(hào)為，棧頂符號(hào)為A時(shí)時(shí) 讀入字符讀入字符a 將狀態(tài)改為將狀態(tài)改為q1 彈出棧頂符號(hào)彈出棧頂符號(hào)A 將符號(hào)將符號(hào)A1, , An從右至左依次壓入棧從右至左依次壓入棧存在的問題存在的問題：1. 以以q1, A1A2An為左為左邊的產(chǎn)生式不好定義邊的產(chǎn)生式不好定義2. 沒有

50、體現(xiàn)沒有體現(xiàn)A1A2An一一個(gè)個(gè)被彈出個(gè)個(gè)被彈出q, A a q1, A1 q2, A2 qn, An（q, A與每個(gè)與每個(gè)qi, Ai都看成一個(gè)變量）都看成一個(gè)變量）定理定理 7-4 對(duì)于任意的對(duì)于任意的PDA M,存在存在CFG G使得使得L(G)=N(M) 思路：用思路：用CFG G的派生來模擬相應(yīng)的的派生來模擬相應(yīng)的PDA M的移動(dòng)的移動(dòng)PDA 與與 CFG 等價(jià)等價(jià)(q1, A1A2An) (q, a, A) M在狀態(tài)在狀態(tài) q，棧頂符號(hào)為，棧頂符號(hào)為A時(shí)讀入字符時(shí)讀入字符a 將狀態(tài)改為將狀態(tài)改為q1 彈出棧頂符號(hào)彈出棧頂符號(hào)A 將符號(hào)將符號(hào)A1,An依次壓入棧依次壓入棧q, A a

51、 q1, A1 q2, A2 qn, An（q, A與每個(gè)與每個(gè)qi, Ai都看成一個(gè)變量）都看成一個(gè)變量）注意：注意：1.當(dāng)當(dāng)Ai被彈出后，接下可能會(huì)壓被彈出后，接下可能會(huì)壓入其他字符串，并重復(fù)彈出、入其他字符串，并重復(fù)彈出、壓入過程，直到進(jìn)入狀態(tài)壓入過程，直到進(jìn)入狀態(tài)qi+1且且棧頂為棧頂為Ai+1q, A,qn+1 a q1, A1,q2 q2, A2,q3 qn, An,qn+1（q, A,qn+1與每個(gè)與每個(gè)qi, Ai,qi+1都看成一個(gè)變量）都看成一個(gè)變量）q2, qn+1窮舉Q中可能的狀態(tài)取取CFG G= (V, , P, S),其中其中：V=SQQP=Sq0, Z0, q|q

52、Q q, A, qn+1 aq1, A1, q2 q2, A2, q3qn, An, qn+1 | (q1, A1A2An)(q, a,A)且且a, q2,q3, , qn, qn+1Q且且n1 q, A, q1 a|(q1, )(q, a, A) 定理定理 7-4 對(duì)于任意的對(duì)于任意的PDA M,存在存在CFG G使得使得L(G)=N(M) 思路：用思路：用CFG G的派生來模擬相應(yīng)的的派生來模擬相應(yīng)的PDA M的移動(dòng)的移動(dòng)q2, qn+1窮舉Q中可能的狀態(tài)構(gòu)造構(gòu)造的的正確性。正確性。 v先證一個(gè)更一般的結(jié)論先證一個(gè)更一般的結(jié)論： q, A, p *x的充分必要條件的充分必要條件是是 (q,

53、x,A)(p, , ), 然然后得到后得到q=q0, A=S時(shí)的特殊結(jié)論時(shí)的特殊結(jié)論構(gòu)造的正確性。構(gòu)造的正確性。必要性：設(shè)必要性：設(shè) q,A,p i x,施施歸納于歸納于i,證明證明(q,x,A)*(p,) 充分性：設(shè)充分性：設(shè)(q,x,A)i(p,)成立成立,施施歸納于歸納于i證明證明q,A,p *X 。定理定理 7- 4 對(duì)于任意的對(duì)于任意的PDA M,存在存在CFG G使得使得L(G)=N(M) 思路：用思路：用CFG G的派生來模擬相應(yīng)的的派生來模擬相應(yīng)的PDA M的移動(dòng)的移動(dòng)例：例：構(gòu)造構(gòu)造CFG G, 使得使得G產(chǎn)生的語(yǔ)言為如下產(chǎn)生的語(yǔ)言為如下PDA M用空棧接用空棧接受的語(yǔ)言。受

54、的語(yǔ)言。M=(q0, 0,1,2, Z, A, B, , q0, Z, )( q0, 0, Z)=(q0, ZA)( q0, 1, Z)=(q0, ZB)( q0, 2, Z)=(q0, )( q0, 0, A)=(q0, )( q0, 1, B)=(q0, )q0, Z, q0 0q0, Z, q0 q0, A, q0q0, Z, q0 1q0, Z, q0 q0, B, q0q0, Z, q0 2q0, A, q0 0q0, B, q0 1S q0, Z, q0 Z 0Z AZ 1ZBZ 2A 0B 1S Z S 0ZA|1ZB|2Z 0ZA|1ZB|2A 0B 1化簡(jiǎn)化簡(jiǎn)例例7-5：構(gòu)造

55、構(gòu)造CFG G, 使得使得G產(chǎn)生的語(yǔ)言為如下產(chǎn)生的語(yǔ)言為如下PDA M用空棧用空棧接受的語(yǔ)言。接受的語(yǔ)言。M=(q0, q1, q2, 0,1,2, B, A, Z, , q0, Z, ), 其中，其中，設(shè)設(shè)S為開始符號(hào)，為開始符號(hào)，G的產(chǎn)生式集合的構(gòu)造的產(chǎn)生式集合的構(gòu)造過程如下：過程如下：S產(chǎn)生式：產(chǎn)生式： S q0, Z, q0 | q0, Z, q1 | q0, Z, q2例例7-5：構(gòu)造構(gòu)造CFG G, 使得使得G產(chǎn)生的語(yǔ)言為如下產(chǎn)生的語(yǔ)言為如下PDA M用空棧用空棧接受的語(yǔ)言。接受的語(yǔ)言。M=(q0, q1, q2, 0,1,2, B, A, Z, , q0, Z, ), 其中，其中，3*3=9例例7-5：構(gòu)造構(gòu)造CFG G, 使得使得G產(chǎn)生的語(yǔ)言為如下產(chǎn)生的語(yǔ)言為如下PDA M用空棧用空棧接受的語(yǔ)言。接受的語(yǔ)言。M=(q0, q1, q2, 0,1,2, B, A, Z, , q0, Z, ), 其中，其中，小結(jié)小結(jié)重點(diǎn)回顧：重點(diǎn)回顧：1、下推自動(dòng)機(jī)、下推自動(dòng)機(jī) PDA 的定義、瞬時(shí)移動(dòng)描述概念、的定義、瞬時(shí)移動(dòng)描述概念、根據(jù)給定語(yǔ)言的特