7形式語言與自動機-2015-下推自動機

1、形式語言與自動機形式語言與自動機Formal Languages and Automata Theory胡春明胡春明 鄧婷鄧婷 趙永望趙永望第第七七章章 下推自動機下推自動機2第七章第七章 下推自動機下推自動機 下推自動機（下推自動機（ PDA ）下推自動機的構造下推自動機的構造PDA 兩種接受語言方式的等價兩種接受語言方式的等價確定的下推自動機（確定的下推自動機（DPDA）PDA 與與 CFG 等價等價第七章第七章 下推自動機下推自動機正則文法與有窮狀態(tài)自動機正則文法與有窮狀態(tài)自動機 例：構造與給定右正則文法等價的例：構造與給定右正則文法等價的 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文法及機器：文法及機器：有有窮狀態(tài)自動機窮狀態(tài)自動機(FA) - 正則語言正則語言(RL)下推自動機下推自動機(PDA) - 上下文無關語言上下文無關語言(CFL)上下文無關文法與下推自動機上下文無關文法與下推自動機（ PDA ）PDA提出的思路：提出的思路： 對于對于CFG, 當它是當它是GNF的時候的時候, 派生總是從左往右進行派生總是從左往右進行, 而且右邊變量而且右邊變量后綴的長度是不定

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

4、的當前狀態(tài)、棧頂當前狀態(tài)、棧頂符號、以及輸入符號符號、以及輸入符號作出相應的作出相應的動作動作有時有時,不不需要考慮輸入需要考慮輸入符號符號為何為何稱下稱下推自推自動機？動機？存放輸入符號串存放輸入符號串的的輸入帶輸入帶存放文法符號的存放文法符號的棧棧有窮狀態(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：下推自動機：下推自動機(pushdown automaton, PDF) 是一個七元組是一個七元組 M = ( Q, , , , q0, Z0, F ), 其中其中 Q: 狀態(tài)的非空有窮集合；狀態(tài)的非空有窮集合； : 輸入字母表；輸入字母表； : 棧字母表；棧字母表； q0: 初始狀態(tài)初始狀態(tài), （ q0 Q） ； Z0: 開始符號開始符號 或?；驐５椎追柗?（ Z0 ）； F: 終止狀態(tài)終止狀態(tài)集合集合, F Q; : 狀態(tài)轉移函數(shù)狀態(tài)轉移函數(shù),Q ( ) 2Q * 。對于對于 ( q, a , Z ) Q ( ) 1、 (

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

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

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

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

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

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

12、的符號在棧的較下面較右的符號在棧的較下面qab = bcdcdbcw = abc下推自動機（下推自動機（ PDA ）：）：即時轉移描述即時轉移描述(1) 如果如果（p, ） （ q, a, Z ）, 且且M 在狀態(tài)在狀態(tài) q, 棧棧頂為頂為 Z,讀讀 入入 a 時時 , 選擇選擇進入狀態(tài)進入狀態(tài) p, 用用 替換棧頂替換棧頂 Z, 讀讀頭指向頭指向 w 的的首首字符字符,記記為：為： （q, aw, Z ） （p, w, ）此時此時, M 做了一次做了一次非空非空移動移動,其其 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 ）, 表示當前表示當前 M 在狀態(tài)在狀態(tài) q,棧棧頂為頂為 Z時時,不不讀讀字符字符,選擇選擇進入狀態(tài)進入狀態(tài) p,用用 替換棧頂替換棧頂 Z,讀讀頭位頭位置置不變不變,記記為：為： （q, w, Z ） （p, w, ）此時此時, M 做了一次做了一次空空移動移動, 其其 ID 由（由（ q, w, Z ） 變?yōu)樽優(yōu)?（p, w, ）。）。Mpq aaZ w=abcde b c d e b c d e下推自動機（下推自動機（ PDA ）:瞬時轉移序列描述瞬時轉移序列描述（ q1, w1, 1 ） （qn, wn, n ）：）：表示表示 M

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

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

16、M=(Q, , , , q0, Z0, F ), 則則M具有具有兩種接受語言的兩種接受語言的方式方式: 1、用、用終態(tài)方式終態(tài)方式接受接受語言語言, 定義定義為：為： L(M)= w | ( q0, w, Z0 ） ( p, , ) 且且 p F ； * 2、 用用空棧方式空棧方式接受接受語言語言,定義定義為：為： N(M)= w | ( q0, w, Z0） ( p, , ) *到達終止狀態(tài),棧不一定為空棧為空,不一定到達終止狀態(tài)例：例：構造接受語言構造接受語言 L = w2wR | w 0,1* 的的 PDA。二、下推自動機的構造二、下推自動機的構造解：解：1、構造產生、構造產生 L 的的

17、 CFG G1：S 0S0 | 1S1 | 2。 2、將文法、將文法 G1 轉換成轉換成格雷巴赫范式格雷巴赫范式（ GNF ） G2： S 0SA | 1SB | 2 A 0 B 1根據(jù)根據(jù) GNF 定義各種識別語言定義各種識別語言 L 的的 PDA 。解解1：構造空棧方式接受語言的：構造空棧方式接受語言的 PDA G2： S 0SA | 1SB | 2A 0B 1派生派生產生規(guī)則產生規(guī)則M應該完成的動作應該完成的動作S0SAS0SA從從q0啟動啟動,讀入讀入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識別句子識別句子 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：構造空棧方式接受語言的：構造空棧方式接受語言的 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；空棧標志：；空棧標志：( q0, , ) 根據(jù)最左派生過程定義狀態(tài)轉移：根據(jù)最左派生過程定義狀態(tài)轉移：當對應的文法變量派生出一個字符當對應的文法變量派生出一個字符時時,相應的相應的PDA讀入這個字符讀入這個字符,并將棧并將棧頂符號換成相應產生式右部除了首頂符號換成相應產生式右部除了首字符之外的后綴字符之外的后綴解解2-1：構造終態(tài)方式接受語言的構造終態(tài)方式接受語言的PDA。 PDA M2 = ( q0, q1, 0 , 1, 2 , S, A, B, Z, Z0 , 2, q0, Z0, q1 )L(M2)= L ；結束標志結束標志：終態(tài)終態(tài) -（qf ,

21、 , ）實際上實際上 = L = w2wR | w 0,1* 設計思路：設計思路：在空棧接受方式下在空棧接受方式下,當?？樟水敆？樟?字符串字符串又正好識別完畢又正好識別完畢,讓它進入終止態(tài)讓它進入終止態(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)；棧符號：棧符號： A-0；B-1； Z 棧底標志棧底標志, Z0/SZ0, S/SA 1, S/SB2

22、, S/q1q00, A/1, B/qf, Z/G2： S 0SA | 1SB | 2A 0B 1解解2-2：構造終態(tài)方式接受語言的構造終態(tài)方式接受語言的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)； 棧符號：棧符號： A-0；B-1； Z 棧底標志棧底標志L（M2）= L ；結束標志：終態(tài)結束標志：終態(tài) -（qf , , ）實際上實際上 = 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 工作過程分為工作過程分為兩個兩個階段階段, 按按階段劃分狀態(tài)：階段劃分狀態(tài)：設計思路：設計思路：不考慮不考慮GNF,但從棧但從棧的特性來設計的特性來設計,棧是先入后出的棧是先入后出的0A1B1、讀字

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

25、” - 匹配失敗匹配失??； 棧棧頂符號為頂符號為 “B”,讀讀 “1” - 匹配匹配成功成功,讀讀 “0” - 匹配失敗；匹配失敗；3、匹配失敗表示匹配失敗表示讀入的字符號串不是語言的讀入的字符號串不是語言的句子句子, 此時此時,可可讓讓 M 停機停機或進入或進入 “陷阱陷阱” 狀態(tài)。狀態(tài)。L = w2wR | w 0,1* 設計思路：設計思路：不考慮不考慮GNF,但從棧但從棧的特性來設計的特性來設計,棧是先入后出的棧是先入后出的回文的特點：110020011解解3-1：構造構造空棧方式空棧方式接受語言的接受語言的 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)。 棧符號：棧符號：A - 0；B - 1；Z0 -棧底符號棧底符號N(M3)= L ；結束標志：（結束標志：（ 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：構造構造終態(tài)方式終態(tài)方式接受語言的接受語言的 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) 棧符號：棧符號：A - 0；B - 1；Z0 初始棧初始棧底底N（M4）= L

28、 ；結束標志：（結束標志：（ qf, , ） 實際上實際上 = 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, )到達終止狀態(tài)，且棧為空記錄階段記錄階段判斷是否讀到字

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

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

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

32、02, , Z02 ) = ( q01, Z01Z02 ) /轉轉M1運行運行 ( 2 ) M2完全模完全模擬擬 M1 的的非空移動非空移動：對于：對于 ( q, a, Z ) Q 2(q, a, Z)=1(q, a, Z) ( 3 ) M2在在非終止狀態(tài)下非終止狀態(tài)下完全模擬完全模擬M1的空移動：對于的空移動：對于 ( q, Z ) (Q F) , 2 ( q, , Z ) = 1 ( q, , Z ) qe 解決第一個問題q02 Z02解決第二個問題定理定理 7-1 的構造證明的構造證明 - 步驟步驟 1:設終態(tài)方式設終態(tài)方式 PDA M1 = ( Q, , , 1, q01, Z01,

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

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

35、擬 M1的所有移動的所有移動操作操作, 故有故有, ( q01, x , Z01Z02 ) ( q, , Z02 ) 且且 q F。同理可證：同理可證： N（M1） L（M2）設任意字符串設任意字符串 x L（M1）, 根據(jù)根據(jù) PDA 接受語言接受語言定義定義, 有有 ( q01, x , Z01 ) ( q, , ) 且且 q F。M 1定理定理 7-1 的構造證明的構造證明 ：步驟步驟 2：求證：求證 L（M1）= N（M2）首先證明：首先證明：L（M1） N（M2）。由由 M2 構造定義構造定義 (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 兩種接受語言方式等價兩種接受語言方式等價定理定理 7- 2 的證明思路的證明思路: 給定給定M1是空棧狀態(tài)接受語言是空棧狀態(tài)接受語言, 構造構造M2以終止狀態(tài)接受相同的語言以終止狀態(tài)接受相同的語言, 且且L(M1)=L(M2) 只要只要M2發(fā)現(xiàn)發(fā)現(xiàn)M1已將棧彈空就可以進入終止狀態(tài)已將棧彈空就可以進入終止狀態(tài)定理定理 7 - 2：對于任意對于任意空棧方式空棧方式接受語言接受語言 L 的的 PDA M1,存在存在存在存

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

38、2) 模擬模擬 M1 轉移：轉移： 對于對于 ( q, a, Z ) Q( ) , 2 ( q, a, Z ) = 1 ( q, a, Z ) 。 (3) 模擬結束：模擬結束： 若若 M1 棧已空棧已空,則則 M2 轉轉終態(tài)終態(tài), 2 ( q, , Z02 ) = ( q f, ) 。步驟步驟 2： 求證求證 N ( M1 ) = L（M2）首先求證：首先求證：L（M2） N（M1） 設設 x L ( M2 ), 根據(jù)根據(jù) M2 的定義以及構造的第一個移動的定義以及構造的第一個移動 ( 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 的構造的構造 ( 3 ), 必有一中間狀態(tài)必有一中間狀態(tài) q Q,此時棧空此時?？?使得使得, ( q01, x , Z01Z02 ) ( q, , Z02 ) 和和 ( q, , Z02 ) ( qf , , ) 成立。成立。M 2M 2由構造由構造(2) 知知, M1 移動與移動與 M2 移動移動相同相同, 故有故有: ( q01, x , Z01Z02 ) ( q, , Z02 )由于由于 Z02 僅是僅是

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

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

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

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

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

45、意對于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模擬模擬GNF的最左派生的最左派生(2) 證明構造的正確性：證明構造的正確性：N(M)=L(G)。 施歸納于施歸納于w的長度的長度n, 證明證明 (q, w, S)Mn (q, , )的充分必要條件為的充分必要條件為Snw。（必要性（續(xù)必要性（續(xù) ）（b）假設結論對假設結論對n=k成立成立, 下面下面證明結論對證明結論對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.再從再從(q, xa, S)Mk (q, a, ) 得得 (q, x, S)Mk (q, , )，由歸納假設知由歸納假設知 S kx , 注意到注意到=A1, 且且A a2P，得，得S kx A1 x a21即即S k+1w。（。（w=xa, =21）故結論對故結論對k+1成立。由歸納法原理，結論對任意成立。由歸納法原理，結論對

47、任意n成立。成立。同理可證充分性。同理可證充分性。由由的任意性，知的任意性，知(q, w, S)Mn (q, , )的充分必的充分必要條件為要條件為Snw，即，即N(M)=L(G).定理定理 7-3 對于任意對于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模擬模擬GNF的最左派生的最左派生(3)考慮考慮L的情況。的情況。 先先按照按照 (1)的構造方法構造出的構造方法構造出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) ,且對于且對于 (a, A)TV，有，有 1(q, a, A)=(q, a, A) ，可證可證N(M)=N(M) 。例：例：構造與如下構造與如下GNF等價的等價的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 對于任意的對于任意的PDA M,

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

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

51、 q1, A1 q2, A2 qn, An（q, A與每個與每個qi, Ai都看成一個變量）都看成一個變量）注意：注意：1.當當Ai被彈出后，接下可能會壓被彈出后，接下可能會壓入其他字符串，并重復彈出、入其他字符串，并重復彈出、壓入過程，直到進入狀態(tài)壓入過程，直到進入狀態(tài)qi+1且且棧頂為棧頂為Ai+1q, A,qn+1 a q1, A1,q2 q2, A2,q3 qn, An,qn+1（q, A,qn+1與每個與每個qi, Ai,qi+1都看成一個變量）都看成一個變量）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 對于任意的對于任意的PDA M,存在存在CFG G使得使得L(G)=N(M) 思路：用思路：用CFG G的派生來模擬相應的的派生來模擬相應的PDA M的移動的移動q2, qn+1窮舉Q中可能的狀態(tài)構造構造的的正確性。正確性。 v先證一個更一般的結論先證一個更一般的結論： q, A, p *x的充分必要條件的充分必要條件是是 (q,

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

54、的語言。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化簡化簡例例7-5：構造

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