1、第第7章下推自動機章下推自動機 FA是識別和處理是識別和處理RL的裝置，而的裝置，而RL是是CFL的一個子集，所以在構(gòu)造的一個子集，所以在構(gòu)造PDA時應(yīng)該兼顧時應(yīng)該兼顧到到FA對對RL的處理方式。的處理方式。 理解：理解：構(gòu)造下推自動機的思路，首先我們構(gòu)造下推自動機的思路，首先我們要構(gòu)造處理要構(gòu)造處理CFL的工具，所以從的工具，所以從CFL出發(fā)，出發(fā)，CFL可以經(jīng)過若干部轉(zhuǎn)化成為可以經(jīng)過若干部轉(zhuǎn)化成為GNF，主要，主要因為因為GNF的語法規(guī)則是最左派生，由于有的語法規(guī)則是最左派生，由于有統(tǒng)一的規(guī)則決定其更容易被處理。統(tǒng)一的規(guī)則決定其更容易被處理。通過提出的棧，再來構(gòu)造下推自動機。通過提出的棧，

2、再來構(gòu)造下推自動機。問題：為什么用棧，而不用隊列或者問題：為什么用棧，而不用隊列或者樹等其他模型？樹等其他模型？第第7章下推自動機章下推自動機 第第7章下推自動機章下推自動機 PDA描述描述CFL，所以它應(yīng)該與，所以它應(yīng)該與CFG等價。等價。 PDA應(yīng)該包含應(yīng)該包含F(xiàn)A的各個元素，或者包含那的各個元素，或者包含那些可以取代些可以取代FA的各個元素的功能的元素。的各個元素的功能的元素。 PDA按照最左派生的派生順序，處理處于按照最左派生的派生順序，處理處于當(dāng)前句型最左邊的變量，因此，需要采用當(dāng)前句型最左邊的變量，因此，需要采用棧作為其存儲機構(gòu)。棧作為其存儲機構(gòu)。 按照按照FA的的“習(xí)慣習(xí)慣”，P

3、DA用終態(tài)接受語言。用終態(tài)接受語言。 模擬模擬GNF的派生的派生PDA用空棧接受語言。用空棧接受語言。 怎怎么理解？么理解？第第7章下推自動機章下推自動機 主要內(nèi)容主要內(nèi)容 PDA的基本概念。的基本概念。 PDA的構(gòu)造舉例。的構(gòu)造舉例。 用終態(tài)接受語言和用空棧接受語言的等價性。用終態(tài)接受語言和用空棧接受語言的等價性。 PDA是是CFL的接受器。的接受器。 重點重點 PDA的基本定義及其構(gòu)造，的基本定義及其構(gòu)造，PDA是是CFLCFL的等價描述。的等價描述。 難點難點 根據(jù)根據(jù)PDA構(gòu)造構(gòu)造CFGCFG。 7.1 基本定義基本定義 PDA應(yīng)該應(yīng)該含有三個基本結(jié)構(gòu)含有三個基本結(jié)構(gòu) 存放輸入符號串的

4、輸入帶。存放輸入符號串的輸入帶。 存放文法符號的棧。存放文法符號的棧。 有窮狀態(tài)控制器。有窮狀態(tài)控制器。 PDA的動作的動作 在有窮狀態(tài)控制器的控制下根據(jù)它的當(dāng)前狀態(tài)、在有窮狀態(tài)控制器的控制下根據(jù)它的當(dāng)前狀態(tài)、棧頂符號、以及輸入符號作出相應(yīng)的動作，在棧頂符號、以及輸入符號作出相應(yīng)的動作，在有的時候，不需要考慮輸入符號。有的時候，不需要考慮輸入符號。 7.1 基本定義基本定義 PDA的物理模型的物理模型7.1 基本定義基本定義比較：比較： PDA M= (Q，q0，Z0，F(xiàn)) FA M= (Q， ，q0， F)7.1 基本定義基本定義 下推自動機下推自動機(pushdown automaton，

5、PDA)M= (Q，q0，Z0，F(xiàn)) Q狀態(tài)的非空有窮集合。狀態(tài)的非空有窮集合。 qQ，q稱為稱為M的一個的一個狀態(tài)狀態(tài)(state)；輸入字母表輸入字母表(input alphabet)。要求。要求M的的輸入字符串都是輸入字符串都是上的字符串；上的字符串；棧符號表棧符號表(stack alphabet)。 A，叫，叫做一個棧符號；做一個棧符號； 7.1 基本定義基本定義 Z0Z0叫做叫做開始符號開始符號(start symbol)，是是M啟動時候棧內(nèi)惟一的一個符號。所以，啟動時候棧內(nèi)惟一的一個符號。所以，習(xí)慣地稱其為棧底符號；習(xí)慣地稱其為棧底符號； q0q0Q，是，是M的的開始狀態(tài)開始狀態(tài)(

6、initial state)，也可叫做也可叫做初始狀態(tài)初始狀態(tài)或者或者啟動狀態(tài)啟動狀態(tài)； FF Q，是，是M的的終止?fàn)顟B(tài)終止?fàn)顟B(tài)(final state)集集合，簡稱為終態(tài)集。合，簡稱為終態(tài)集。 qF，q稱為稱為M的終的終止?fàn)顟B(tài)，也可稱為止?fàn)顟B(tài)，也可稱為接受狀態(tài)接受狀態(tài)(accept state)，簡稱為終態(tài)。簡稱為終態(tài)。 7.1 基本定義基本定義 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)(transition function)，有時候又叫做狀態(tài)轉(zhuǎn)換函數(shù)狀態(tài)轉(zhuǎn)換函數(shù)或者移動函數(shù)。移動函數(shù)。 ：Q() *2Q(q，a，Z)=(p1，1)，(p2，2)，(pm，m)思考：思考： 對應(yīng)的轉(zhuǎn)移具有選擇性，這是不對應(yīng)

7、的轉(zhuǎn)移具有選擇性，這是不是表明是表明DFA是非確定的呢？是非確定的呢？7.1 基本定義基本定義 兩種移動兩種移動 (q，a，Z)=(p1，1)，(p2，2)，(pm，m) 有輸入的移動有輸入的移動：表示：表示M在狀態(tài)在狀態(tài)q，棧頂符號，棧頂符號為為Z時，讀入字符時，讀入字符a，對于，對于i=1，2，m，可以選擇地將狀態(tài)變成可以選擇地將狀態(tài)變成pi，并將棧頂符號，并將棧頂符號Z彈出，將彈出，將i中的符號從右到左依次壓入棧，中的符號從右到左依次壓入棧，然后將讀頭向右移動一個帶方格而指向輸然后將讀頭向右移動一個帶方格而指向輸入字符串的下一個字符。入字符串的下一個字符。7.1 基本定義基本定義(q，Z

8、)=(p1，1)，(p2，2)，(pm，m) 空移動空移動：表示：表示M進(jìn)行一次進(jìn)行一次-移動移動(空移動空移動)，即即M在狀態(tài)在狀態(tài)q，棧頂符號為，棧頂符號為Z時，無論輸入時，無論輸入符號是什么，對于符號是什么，對于i=1，2，m，可以選，可以選擇地將狀態(tài)變成擇地將狀態(tài)變成pi，并將棧頂符號，并將棧頂符號Z彈出，彈出，將將i中的符號從右到左依次壓入棧，讀頭不中的符號從右到左依次壓入棧，讀頭不移動。移動。條件響應(yīng)當(dāng)前狀態(tài) 新狀態(tài)有輸入棧頂符號 修改棧頂輸入符號 右移讀寫頭輸入為空 當(dāng)前狀態(tài) 新狀態(tài)棧頂符號 修改棧頂7.1 基本定義基本定義7.1 基本定義基本定義圖像模擬b FSC S c a

9、a p q Z A S A Z S 7.1 基本定義基本定義 M接受的語言接受的語言 ： M用終態(tài)接受的語言用終態(tài)接受的語言 L(M)= | (q0，Z0)*(p，)且且 pF M用空棧接受的語言用空棧接受的語言 N(M) = | (q0，Z0)*(p，) 7.1 基本定義基本定義 符號使用約定符號使用約定 英文字母表較為前面的小寫字母，如英文字母表較為前面的小寫字母，如a，b，c，表示輸入符號；，表示輸入符號； 英文字母表較為后面的小寫字母，如英文字母表較為后面的小寫字母，如x，y，z，表示由輸入字符串；，表示由輸入字符串； 英文字母表的大寫字母，表示棧符號；英文字母表的大寫字母，表示棧符號

10、； 希臘字母希臘字母，表示棧符號串。，表示棧符號串。 7.1 基本定義基本定義7.1 基本定義基本定義 即時描述即時描述(instantaneous description，ID) (q，)(Q，*，*)稱為稱為M的一個的一個即時描述即時描述。它表示。它表示M處于狀態(tài)處于狀態(tài)q，是當(dāng)前是當(dāng)前還未處理的輸入字符串還未處理的輸入字符串，而且，而且M正注視著正注視著的首字符，的首字符，棧中的符號串棧中的符號串為為，的最左符的最左符號為棧頂符號，最右符號為棧底的符號，號為棧頂符號，最右符號為棧底的符號，較左的符號在棧的較上面，較右的符號在較左的符號在棧的較上面，較右的符號在棧的較下面。棧的較下面。 7

11、.1 基本定義基本定義如果如果(p，)(q，a，Z)，a，則，則(q，a，Z)M(p，)表示表示M做一次做一次非空移動非空移動，從，從ID(q，a，Z)變成變成ID(p，)。 如果如果(p，)(q，Z)，則，則(q，Z)M(p，)表示表示M做一次做一次空移動空移動，從，從ID(q，a，Z)變成變成ID(p，) 。7.1 基本定義基本定義 Mn是是M 的的n次冪次冪 (q1，1，1)Mn(qn，n，n) M*是是M 的克林閉包的克林閉包 (q，)M*(p，x，) M+是是M 的正閉包的正閉包 (q，)M+(p，x，) 7.1 基本定義基本定義 例例 7-1 考慮接受語言考慮接受語言L=2T |

12、0,1*的的PDA的設(shè)計。的設(shè)計。 解法解法1：首先是根據(jù)首先是根據(jù)PDA的構(gòu)造過程、工作的構(gòu)造過程、工作原理和原理和GNF的最左派生來分析。的最左派生來分析。 先設(shè)計產(chǎn)生先設(shè)計產(chǎn)生L的的CFG G1：G1：S2|0S0|1S1 再將此文法轉(zhuǎn)化成再將此文法轉(zhuǎn)化成GNF：G2：S2|0SA|1SBA0B1 7.1 基本定義基本定義句子句子0102010的最左派生和我們希望相應(yīng)的的最左派生和我們希望相應(yīng)的PDA M的動作。的動作。 派生派生M應(yīng)該完成的動作應(yīng)該完成的動作S0SA從從q0啟動，讀入啟動，讀入0，將，將S彈出棧，將彈出棧，將SA壓入棧，狀態(tài)不變壓入棧，狀態(tài)不變01SBA在狀態(tài)在狀態(tài)q0

13、，讀入，讀入1，將，將S彈出棧，將彈出棧，將SB壓入棧，狀態(tài)不變壓入棧，狀態(tài)不變 010SABA在狀態(tài)在狀態(tài)q0，讀入，讀入0，將，將S彈出棧，將彈出棧，將SA壓入棧，狀態(tài)不變壓入棧，狀態(tài)不變0102ABA在狀態(tài)在狀態(tài)q0，讀入，讀入2，將，將S彈出棧，將彈出棧，將壓入棧，狀態(tài)不變壓入棧，狀態(tài)不變01020BA在狀態(tài)在狀態(tài)q0，讀入，讀入0，將，將A彈出棧，將彈出棧，將壓入棧，狀態(tài)不變壓入棧，狀態(tài)不變010201A在狀態(tài)在狀態(tài)q0，讀入，讀入1，將，將B彈出棧，將彈出棧，將壓入棧，狀態(tài)不變壓入棧，狀態(tài)不變0102010在狀態(tài)在狀態(tài)q0，讀入，讀入0，將，將A彈出棧，將彈出棧，將壓入棧，狀態(tài)不變

14、壓入棧，狀態(tài)不變FSC.0102.S ABAZSq1-qf0S7.1 基本定義基本定義7.1 基本定義基本定義FSC0100.SABAZSq0-q127.1 基本定義基本定義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，) 轉(zhuǎn)化轉(zhuǎn)化1(q0，0，A)=(q0，) 1(q0，1，B)=(q0，) 匹配匹配此時有：此時有：N(M1)=L。注意：從右向左依次壓棧。注意：從右向左依次壓棧。7.1 基本定義基本定義7.1 基本定義基本定義M2=(q0,q1,0,1,2,S,A

15、,B,Z,Z0,2,q0,Z0,q1)2(q0，0，Z0)=(q0，SAZ)2(q0，1，Z0)=(q0，SBZ) 起始起始2(q0，2，Z0)=(q1，)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)=(q1，) 終止終止此時有：此時有：N(M2)=L(M2)=L。 思考：初始棧內(nèi)為空，那么思考：初始棧內(nèi)為空，那么Z0是如何壓棧的？是如何壓棧的？7.1 基本定義基本定義思考：如果沒有棧符號思考：如果沒有棧符號Z可不可以？可不可以？7.1 基本定義

16、基本定義 解法解法2：根據(jù)句子的構(gòu)成來分析問題。根據(jù)句子的構(gòu)成來分析問題。 注意到注意到L=2T|0,1*，所以，所以PDA M3 的工作可以分成兩大階段。的工作可以分成兩大階段。 在讀到字符在讀到字符2之前，為之前，為“記載記載”階段：每讀到階段：每讀到一個符號就在棧中做一次相應(yīng)的記載。一個符號就在棧中做一次相應(yīng)的記載。 在讀到在讀到2以后，再讀到字符時，就應(yīng)該進(jìn)入以后，再讀到字符時，就應(yīng)該進(jìn)入“匹配匹配”階段：由于棧的階段：由于棧的“先進(jìn)后出先進(jìn)后出”特性正特性正好與好與wT相對應(yīng)，所以，用棧頂符號逐一地與輸相對應(yīng)，所以，用棧頂符號逐一地與輸入字符匹配。入字符匹配。 7.1 基本定義基本定

17、義 M3=(q0，q1，q2，qf，qt，0，1，2， A，B， Z0，3，q0，Z0，qf) q0為開始狀態(tài)為開始狀態(tài) q1為記錄狀態(tài)為記錄狀態(tài) q2為匹配狀態(tài)為匹配狀態(tài) qf為終止?fàn)顟B(tài)為終止?fàn)顟B(tài) qt陷阱狀態(tài)：陷阱狀態(tài)：匹配不成功匹配不成功 7.1 基本定義基本定義3(q0，0，Z0)=(q1，AZ0)3(q0，1，Z0)=(q1，BZ0) 起始起始3(q0，2，Z0)=(qf，)3(q1，0，A)=(q1，AA)3(q1，1，A)=(q1，BA) 記錄記錄3(q1，0，B)=(q1，AB)3(q1，1，B)=(q1，BB) 7.1 基本定義基本定義3(q1，2，A)=(q2，A) 狀態(tài)轉(zhuǎn)

18、移狀態(tài)轉(zhuǎn)移3(q1，2，B)=(q2，B)3(q2，0，A)=(q2，)3(q2，1，B)=(q2，) 匹配匹配3(q2，0，B)=(qt，) （正確、錯誤）（正確、錯誤）3(q2，1，A)=(qt，)3(q2，Z0)=(qf，) 終止終止此時有：此時有：N(M3)=L(M3)=L。7.1 基本定義基本定義M3=(q0，q1，q2，qf，qt，0，1，2， A，B， Z0，3，q0，Z0，qf) M4=(q0，q1，q2 ，0，1，2， A，B， Z0，4，q0，Z0，) 7.1 基本定義基本定義 不追求讓不追求讓PDA同時用終止?fàn)顟B(tài)和空棧接受同時用終止?fàn)顟B(tài)和空棧接受同樣的語言同樣的語言，還可

19、以刪除狀態(tài)，還可以刪除狀態(tài)qf。這樣我們。這樣我們可以得到可以得到PDA M4 。 M4=(q0，q1，q2 ，0，1，2， A，B， Z0，4，q0，Z0，) 4(q0，0，Z0)=(q1，A)4(q0，1，Z0)=(q1，B) 起始起始4(q0，2，Z0)=(q2，)7.1 基本定義基本定義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) 狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移4(q1，2，B)=(q2，B)4(q2，0，A)=(q2，) 匹配匹配4(q2，1，B)=(q2，)7.1

20、 基本定義基本定義思考：是否可以q2讓作為終止?fàn)顟B(tài)。7.1 基本定義基本定義 思考：構(gòu)造一個思考：構(gòu)造一個PDA用來識用來識2|0,1* 事實上不可能的，首先在棧內(nèi)變量的倒序是不可能的；其事實上不可能的，首先在棧內(nèi)變量的倒序是不可能的；其次，該語言不是次，該語言不是CFL具體證明過程在第八章。具體證明過程在第八章。 確定的確定的(deterministic)PDA (q，a，Z)Q |(q，a，Z)|+|(q，Z)|1 PDA在每一個在每一個狀態(tài)狀態(tài)q和一個和一個棧頂符號棧頂符號下的動作都是下的動作都是惟一惟一的。的。 關(guān)鍵關(guān)鍵 對于對于 (q，Z)Q，M此時如果有非空移動，就不能有空移動。此

21、時如果有非空移動，就不能有空移動。 每一種情況下的每一種情況下的移動都是惟一移動都是惟一的。的。7.1 基本定義基本定義 例例 7-2 構(gòu)造接受構(gòu)造接受L=T|0,1*的的PDA。 差異差異(q0，0，A)=(q0，AA)，(q1，) 0是是w中的中的0或者是或者是wT的首字符的首字符0；(q0，1，B)=(q0，BB)， (q1，) 1是是w中的中的1或者是或者是wT的首字符的首字符1。具體的狀態(tài)轉(zhuǎn)移函數(shù)具體的狀態(tài)轉(zhuǎn)移函數(shù)參考課本參考課本P2007.1 基本定義基本定義思考：如何判斷進(jìn)入匹配狀態(tài)。思考：如何判斷進(jìn)入匹配狀態(tài)。 7.2 PDA與與CFG等價等價 在證明在證明PDA與與CFG等價

22、之前，我們要先證明等價之前，我們要先證明 對于任意對于任意PDA M1，存在，存在PDA M2，使得，使得L(M2)=N(M1)； 對于任意對于任意PDA M1，存在，存在PDA M2，使得，使得N (M2)= L (M1)。注意：是任意一個而不是同一個注意：是任意一個而不是同一個PDA存在存在N (M1)= L (M1)。 CFL可以用空棧接受語言的可以用空棧接受語言的PDA接受。接受。 PDA接受語言可以用接受語言可以用CFG描述。描述。 7.2 PDA與與CFG等價等價 證明思路：證明思路：1、證明、證明PDA與與CFG等價等價2、先證明、先證明對于任意的對于任意的PDA存在存在L(M2

23、)=N(M1)或者或者N (M2)= L (M1)即：即：PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價。狀態(tài)接受等價。3、證明上面的命題，先構(gòu)造等價的、證明上面的命題，先構(gòu)造等價的PDA7.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 定理定理 7-1 對于任意對于任意PDA M1，存在，存在PDA M2，使，使得得N (M2)= L (M1)。 證明要點：證明要點：構(gòu)造等價的運轉(zhuǎn)狀態(tài)構(gòu)造等價的運轉(zhuǎn)狀態(tài) 注意兩個問注意兩個問題題1.當(dāng)當(dāng)引導(dǎo)引導(dǎo)M1進(jìn)入終止?fàn)顟B(tài)后，進(jìn)入終止?fàn)顟B(tài)后，M1的棧不空，的棧不空，此時此時M2必須將棧清空，以達(dá)到接受狀態(tài)。必須將棧清

24、空，以達(dá)到接受狀態(tài)。2.M1在運行的過程中沒有進(jìn)入終止?fàn)顟B(tài)，但是在運行的過程中沒有進(jìn)入終止?fàn)顟B(tài)，但是此時的棧已經(jīng)空，此時的棧已經(jīng)空，M2要能夠避免出現(xiàn)這種狀要能夠避免出現(xiàn)這種狀況時出現(xiàn)誤接受。（解釋）況時出現(xiàn)誤接受。（解釋）解決辦法：需要引入解決辦法：需要引入一個狀態(tài)一個狀態(tài)，解決問題，解決問題1，它來完成清棧工作。它來完成清棧工作。7.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 解決辦法：還需要解決辦法：還需要一個狀態(tài)一個狀態(tài)和和棧符號棧符號來解決來解決問題問題2，M1未進(jìn)入終止?fàn)顟B(tài)而棧已空的未進(jìn)入終止?fàn)顟B(tài)而棧已空的M2誤接受。誤接受。（1） 構(gòu)造：構(gòu)造：在已

25、知在已知M1的基礎(chǔ)上構(gòu)造的基礎(chǔ)上構(gòu)造M2設(shè)設(shè)PDA M1 = (Q，1，q01，Z01，F(xiàn))取取PDA M2 = (Qq02，qe，Z02，q02，Z02，F(xiàn))其中其中Qq02，qe=Z02=。 7.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 .2(q02，Z02)=(q01，Z01Z02) 引導(dǎo)引導(dǎo)M2進(jìn)入進(jìn)入M1的初始的初始ID即開始狀態(tài)，即開始狀態(tài)，模擬模擬M1。 . (q,a,Z)Q, 2(q,a,Z)=1(q,a,Z)；非空移動非空移動 . (q,Z)(Q-F), 2(q,Z)=1(q,Z)；空移動空移動 . (q,Z)F,2(q,Z)=1(q,Z)(

26、qe,)；M1在終止?fàn)顟B(tài)下，在終止?fàn)顟B(tài)下，M2模模擬擬M1的空移動，還需要模擬的空移動，還需要模擬M1接受動作。接受動作。 . qF,2(q,Z02)= (qe,)；M1的棧已經(jīng)空了，并且進(jìn)入終止?fàn)顟B(tài)，的棧已經(jīng)空了，并且進(jìn)入終止?fàn)顟B(tài)，M2進(jìn)入清棧狀態(tài)。進(jìn)入清棧狀態(tài)。 . ZZ02,2(qe,Z)= (qe,)；完成清棧工作完成清棧工作其中第其中第4、5兩步主要是對棧空或非空，兩步主要是對棧空或非空，M1、M2的接受態(tài)和終態(tài)的同步。的接受態(tài)和終態(tài)的同步。7.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 （2） 證明證明N (M2)= L (M1)。 xL(M1) (

27、q01，x，Z01)M1*(q，)且且qF M1經(jīng)過若干步移動到達(dá)終態(tài)經(jīng)過若干步移動到達(dá)終態(tài)(q01，x，Z01Z02)M1*(q，Z02)且且qF 相當(dāng)于沒有相當(dāng)于沒有Z02(q01，x，Z01Z02)M2*(q，Z02)且且qF M2模擬模擬M1，M1能進(jìn)行的移動能進(jìn)行的移動M2都可以都可以進(jìn)行。進(jìn)行。7.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 (q01，x，Z01Z02)M2*(q，Z02)M2*(qe，)且且qF(q01，x，Z01Z02)M2*(qe，) (q02，x，Z02)M2(q01，x，Z01Z02)M2*(qe，) 通過空移動將棧中符號彈

28、出進(jìn)入通過空移動將棧中符號彈出進(jìn)入M2的的空接受狀態(tài)。空接受狀態(tài)。(q02，x，Z02)M2*(qe，)xN(M2)雖與課本上的寫法不同，但基本方法一致P2027.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 定理定理 7-2 對于任意對于任意PDA M1，存在，存在PDA M2，使得使得L (M2)= N (M1)。證明要點：證明要點：依舊是構(gòu)造等價的依舊是構(gòu)造等價的PDA注意問題：需要讓注意問題：需要讓M2在開始時將自己的棧地在開始時將自己的棧地符號壓入棧底，并將符號壓入棧底，并將M1的棧底符號壓棧，的棧底符號壓棧，同時進(jìn)入同時進(jìn)入M1的開始狀態(tài)，模擬的開始狀態(tài)，模擬M1。M2一旦一旦發(fā)現(xiàn)自己的棧底符號成為棧頂，就近入終發(fā)現(xiàn)自己的棧底符號成為棧頂，就近入終止?fàn)顟B(tài)。止?fàn)顟B(tài)。解決辦法：新增一個棧底符號、一個開始狀解決辦法：新增一個棧底符號、一個開始狀態(tài)和一個終止?fàn)顟B(tài)。態(tài)和一個終止?fàn)顟B(tài)。 7.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 模擬模擬7.2.1 PDA用空棧接受和用終止用空棧接受和用終止?fàn)顟B(tài)接受等價狀態(tài)接受等價 (1)構(gòu)造。構(gòu)造。設(shè)設(shè)PDA M1 = (Q，1，q01，Z01， ) 取取PDA M2 = (Qq02，qf，Z02，q02，Z02，qf)其中其中Qq0