形式語言自動機——上下文無關(guān)文法與下推自動機四學(xué)習(xí)教案

1、會計學(xué)1形式語言自動機形式語言自動機上下文無關(guān)上下文無關(guān)(wgun)文法與下推自動機四文法與下推自動機四第一頁，共23頁。2 構(gòu)造方法構(gòu)造方法 設(shè)設(shè) CFG G = (N, T, P , S ) ，構(gòu)造一個空棧接受方式構(gòu)造一個空棧接受方式(fngsh)的的 PDA M（Q，T，q0，z0，F(xiàn)）其中其中 Qq, =NT, q0q，z0S, F (以空棧接受以空棧接受)即即 M = ( q , T, NT, , q, S , F) , 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù) 定義如下：定義如下： (1) 對每一對每一 AN, (q, , A) = (q,)A”P ; （即將棧頂?shù)模磳ｍ數(shù)腁換為換為） (2) 對每一

2、對每一 aT, (q, a, a) = (q, ) . （即若棧頂為終結(jié)符，則退棧）（即若棧頂為終結(jié)符，則退棧） 從上下文無關(guān)從上下文無關(guān)(wgun)文法構(gòu)造等價的下推文法構(gòu)造等價的下推自動機自動機第2頁/共23頁第二頁，共23頁。3q，z0z0S/S/ 若若SPSP ，A/ A/ 若若APAP a,a/ a,a/ a T, 從上下文無關(guān)從上下文無關(guān)(wgun)文法構(gòu)造等價的下推自動機文法構(gòu)造等價的下推自動機用圖形用圖形(txng)(txng)表示：表示： 例例1 對右邊產(chǎn)生式所代表對右邊產(chǎn)生式所代表 CFG， 依上述方法依上述方法(fngf)構(gòu)造的構(gòu)造的 PDA 為為E EOE (E) v

3、dO ( q , v,d,+, ,(,) , E,O,v,d,+, , , q, E, ) , 其中其中 定義為定義為 (q, , E) =(q,EOE), (q,(E), (q,v),(q,d),(q,), (q, ), (q, , O) = (q, ) , (q, v, v) = (q, d, d)= (q, ) (q,) = (q, , ) = (q,(,( ) = (q,),) )= 第3頁/共23頁第三頁，共23頁。4自頂向下的分析自頂向下的分析(fnx)過程過程定理的物理意義：利用下推自動機進行自頂向下的分析，定理的物理意義：利用下推自動機進行自頂向下的分析， 檢查檢查一個句子的最

4、左推導(dǎo)過程一個句子的最左推導(dǎo)過程(guchng)。 步驟如下：步驟如下： (1) 初始時，將文法開始符號壓入空棧初始時，將文法開始符號壓入空棧. (2) 如果棧為空，則分析完成如果棧為空，則分析完成. (3) 如果棧頂為一非終結(jié)符，先將其從棧中彈出如果棧頂為一非終結(jié)符，先將其從棧中彈出. 選擇下選擇下 一個相應(yīng)于該非終結(jié)符的產(chǎn)生式，并將其右部一個相應(yīng)于該非終結(jié)符的產(chǎn)生式，并將其右部 符號從符號從 右至左地一一入棧右至左地一一入棧. 如果沒有可選的產(chǎn)生式，則轉(zhuǎn)出如果沒有可選的產(chǎn)生式，則轉(zhuǎn)出 錯處理錯處理. (4) 如果棧頂為一終結(jié)符，那么這個符號必須與當(dāng)前輸入如果棧頂為一終結(jié)符，那么這個符號必須

5、與當(dāng)前輸入 符號相同，將其彈出棧，讀下一符號，轉(zhuǎn)第符號相同，將其彈出棧，讀下一符號，轉(zhuǎn)第(2)步；否步；否 則，回溯到第則，回溯到第(3)步步.第4頁/共23頁第四頁，共23頁。5例例2：利用下推自動機進行：利用下推自動機進行(jnxng)自頂向下的分析自頂向下的分析過程過程E EOE (E) v dO EEOEEOvEOE EE)(E)E)OEE)OvE)OE)E)d)v ( v d )q，z z0 0E E/ / 若若EPEP ，O/O/* *a,a/ a a,a/ a (,),v,d,+, (,),v,d,+,* * ，O/+O/+第5頁/共23頁第五頁，共23頁。6定理定理(dngl)

6、(dngl)的證明的證明 證明思路證明思路(sl) 欲證，對任何欲證，對任何 wT*, wL(G) wL(M). 先證明如下結(jié)論先證明如下結(jié)論, if A w, then (q,w,A)*(q, , ). 歸納于歸納于 A w 的步數(shù)的步數(shù) n. . 基礎(chǔ)基礎(chǔ)(jch) n=1，Aw 必為產(chǎn)生式，必為產(chǎn)生式， (q,w,A) (q,w,w) *(q, , ).歸納歸納 設(shè)第一步使用產(chǎn)生式設(shè)第一步使用產(chǎn)生式 AX1X2Xm ，必有必有 w=w1w2wm ， (q,w,A) (q,w, X1X2Xm ) * (q, w2wm , X2Xm) * (q, w3wm , X3Xm)* * (q, ,

7、).所以所以: if S w, then (q,w,S)*(q, , ). 即即, w L(G) w L(M). 第6頁/共23頁第六頁，共23頁。7定理定理(dngl)(dngl)的證明的證明 先證明如下結(jié)論先證明如下結(jié)論, if (q, w,A)*(q, , ), then A w. 歸納歸納(gun)于于 (q, w,A)*(q, , ) 的步的步數(shù)數(shù) n.歸納歸納(gun) n1，設(shè)第一步使用產(chǎn)生式，設(shè)第一步使用產(chǎn)生式 AX1X2Xm ， 可以將可以將w 分為分為 w = w 1 w 2 w m ，滿足，滿足 (q, wi , Xi )*(q, , )，所以所以: 對任何對任何 w T

8、*, if (q,w,S)*(q, , ), then S w. 即即, w L(M) w L(G). 因此因此 ，A X1X2Xm ， w 1 w 2 w m = w 無論無論 Xi 為終結(jié)符，還是非終結(jié)符，都有為終結(jié)符，還是非終結(jié)符，都有 Xi w i . 基礎(chǔ)基礎(chǔ) n=1，必有必有 w = ，且且 A 為為 G 的產(chǎn)生式，所以的產(chǎn)生式，所以 A w. 第7頁/共23頁第七頁，共23頁。8例：構(gòu)造一個例：構(gòu)造一個PDA MPDA M，使，使L(M)= L(G)L(M)= L(G)。其中。其中G G是我們常用來生成是我們常用來生成算術(shù)表達式的文法：算術(shù)表達式的文法：G G（N N，T T，P

9、 P，E E） N N E,T,F , T = +, E,T,F , T = +,* *,(,),a , S = E ,(,),a , S = E P: EE+TT ; TT P: EE+TT ; TT* *FF; F( E )aFF; F( E )a解：構(gòu)造解：構(gòu)造M M（qq，T T，q q，E E，） 定義定義(dngy)(dngy)為：為： (q,E) (q,E) (q, E+T ), (q, T) (q, E+T ), (q, T) (q,T) (q,T) (q, T (q, T* *F ), (q, F) F ), (q, F) (q,F) (q,F) (q, (E) ), ( q

10、, a) (q, (E) ), ( q, a) (q, b,b) (q, b,b) (q, ) (q, ) 對所有對所有 b a,+, b a,+,* *,(,) ,(,) 例例3: 從文法從文法(wnf)構(gòu)造等價的下推自動機構(gòu)造等價的下推自動機第8頁/共23頁第八頁，共23頁。9用格局說明句子用格局說明句子(j zi)分析過程分析過程 例如例如 以以a+aa+a* *a a作為輸入作為輸入(shr)(shr)，則，則M M在所有可能移動中可作下列在所有可能移動中可作下列移動（用到文法移動（用到文法G G中從中從E E出發(fā)的最左派生的一系列規(guī)則）出發(fā)的最左派生的一系列規(guī)則） （q q，a aa

11、 a* *a, Ea, E） (q (q，a aa a* *a, E+T)a, E+T) (q (q，a aa a* *a, T+T)a, T+T) (q (q，a aa a* *a, F+T)a, F+T) (q (q，a aa a* *a, a+T)a, a+T) (q (q，a a* *a, +T)a, +T) (q (q，a a* *a, T)a, T) (q (q，a a* *a, Ta, T* *F)F) (q (q，a a* *a, Fa, F* *F)F) 第9頁/共23頁第九頁，共23頁。10從下推自動機構(gòu)造從下推自動機構(gòu)造(guzo)等價的上下文無關(guān)文法等價的上下文無關(guān)文法

12、G G導(dǎo)出導(dǎo)出PDAPDA，其逆定理也成立。，其逆定理也成立。 PDA PDA導(dǎo)出文法導(dǎo)出文法G G）：）：設(shè)下推自動機設(shè)下推自動機M M，以空棧形式接受語言，以空棧形式接受語言 L(M L(M），則存在），則存在(cnzi)(cnzi)一個上下文無關(guān)文法一個上下文無關(guān)文法G G，產(chǎn)生語言，產(chǎn)生語言L(G), L(G), 使使L(G)= L(ML(G)= L(M） 。證明：設(shè)證明：設(shè)M M（ Q Q，T T，q0q0，z0z0，） 思路：構(gòu)造文法思路：構(gòu)造文法G G，使，使串在串在G G中的一個最左推導(dǎo)直接對應(yīng)于中的一個最左推導(dǎo)直接對應(yīng)于PDA PDA M M 在處理在處理時所做的一系列移動時

13、所做的一系列移動 。第10頁/共23頁第十頁，共23頁。11從下推自動機構(gòu)造等價從下推自動機構(gòu)造等價(dngji)的上下文無關(guān)的上下文無關(guān)文法文法采用形如采用形如qq，z,z,的非終結(jié)符的非終結(jié)符, q, q，QQ，zz q q，z,z,的物理意義的物理意義(yy)(yy)：在在q q狀態(tài)，棧頂為狀態(tài)，棧頂為z z時，接受某個字符時，接受某個字符( (可為可為)后將變換后將變換到到狀態(tài)，并保證狀態(tài)，并保證 qq，z, z, 當(dāng)且僅當(dāng)（當(dāng)且僅當(dāng)（q,zq,z）* *（,）. .第11頁/共23頁第十一頁，共23頁。12從下推自動機構(gòu)造等價的上下文無關(guān)從下推自動機構(gòu)造等價的上下文無關(guān)(wgun)文

14、法文法 構(gòu)造構(gòu)造(guzo)(guzo)方法方法 設(shè)設(shè) PDA M PDA M（ Q Q，T T，q0q0，z0z0，） , , 構(gòu)造構(gòu)造(guzo)CFG G(guzo)CFG G（N,T,P,SN,T,P,S） 其中其中 N N q,z,q,Q q,z,q,Q，zSzS 產(chǎn)生產(chǎn)生(chnshng)式集合式集合 P 定義如下：定義如下：對于每個對于每個qQ，將，將Sq0，z0, q 加入到產(chǎn)生加入到產(chǎn)生(chnshng)式中。式中。 若若（q，a，z）含有（）含有（,），則將），則將q,z,a加入到產(chǎn)生加入到產(chǎn)生(chnshng)式中。式中。若若（q，a，z）含有（）含有（，B1,B2, B

15、k）k1，Bi，則對，則對Q中的每一個狀態(tài)序列中的每一個狀態(tài)序列q1,q2,qk,(qiQ),把形如把形如q,z,qka,B1,q1q1,B2,q2qk-1,Bk,qk的產(chǎn)生的產(chǎn)生(chnshng)式加入到式加入到P中。其中，中。其中，a T 或或 a = 第12頁/共23頁第十二頁，共23頁。13（書P169170）由PDA M構(gòu)造(guzo)文法G設(shè)PDA M（q0,q1,a,b,A,z0,q0,z0,）定義為：（q0,a,z0）=( q0,Az0) （q0,a,A）=( q0,AA) （q0,b,A）=( q1,) （q1,b,A）=( q1,) （q1,A）=( q1,) （q1,z0

16、）=( q1,) 例例1: 從下推自動機構(gòu)造等價從下推自動機構(gòu)造等價(dngji)的上下文無關(guān)的上下文無關(guān)文法文法第13頁/共23頁第十三頁，共23頁。14 q0 b, A/ q1 a, z0/Az0 b, A/ a, A/AA , A/ , z0/解：（1） q0,q1Q， 構(gòu)造(guzo) Sq0,z0,q0; Sq0,z0,q1 （2）對式，可構(gòu)造(guzo)由（q0,b,A）=( q1,) 得 q0,A,q1b 由（q1,b,A）=( q1,) 得q1,A,q1b由（q1,A）=( q1,)得 q1,A,q1由（q1,z0）=( q1,)得 q1,z0,q1第14頁/共23頁第十四頁，

17、共23頁。15 q0 b, A/ q1 a, z0/Az0 b, A/ a, A/AA , A/ , , z0/（3） 對式（q0,a,z0）=( q0, A z0) ，所有可能(knng)的狀態(tài)序列為：q0q0，q1q0，q0q1，q1q1可構(gòu)造出產(chǎn)生式： q0,z0,q0 a q0,A, q0 q0,z0, q0 q0,z0,q0 a q0,A, q1 q1,z0, q0 q0,z0,q1 a q0,A, q0 q0,z0, q1 q0,z0,q1 a q0,A, q1 q1,z0, q1 第15頁/共23頁第十五頁，共23頁。16 q0 b, A/ q1 a, z0/Az0 b, A/

18、a, A/AA , A/ , , z0/對式（q0,a,A）=( q0, AA) ，所有可能的狀態(tài)序列為：q0q0，q1q0，q0q1，q1q1可構(gòu)造(guzo)出產(chǎn)生式： q0,A,q0 a q0,A, q0 q0,A, q0 q0,A,q0 a q0,A, q1 q1,A, q0 q0,A,q1 a q0,A, q0 q0,A, q1 q0,A,q1 a q0,A, q1 q1,A, q1 第16頁/共23頁第十六頁，共23頁。17(4)刪除無用符號 q0,A,q1 和 q1,z0,q0及相應(yīng)(xingyng)產(chǎn)生式 重命名 q0,z0,q1為A SA q1,A,q1為B AaCD q0,

19、A,q1為C 得 Bb q1,z0,q1為D CaCBb D注: 構(gòu)造生成式時，可從S生成式出發(fā)，以避免生成無用產(chǎn)生式。第17頁/共23頁第十七頁，共23頁。18定理定理(dngl)的關(guān)鍵：的關(guān)鍵： 當(dāng)存在當(dāng)存在(q，a，z)含有（含有（，B1B2Bk）則對則對Q中的每個可能的狀態(tài)序列中的每個可能的狀態(tài)序列q1 q2 qk排成一條產(chǎn)生式排成一條產(chǎn)生式q, z, qka, B1, q1 q1, B2,q2qk-1,Bk,qk 這是一個猜測過程，實質(zhì)是寫出從這是一個猜測過程，實質(zhì)是寫出從q出發(fā)，棧出發(fā)，棧頂為頂為Z，經(jīng)過一系列推導(dǎo)走到，經(jīng)過一系列推導(dǎo)走到qk的所有可能的所有可能的狀態(tài)序列，其中必有

20、一條路徑是正確的。的狀態(tài)序列，其中必有一條路徑是正確的。 第18頁/共23頁第十八頁，共23頁。19M（q，T，q，E，） 定義為：定義為： (q,E) (q, E+T ), (q, T) (q,T) (q, T*F ), (q, F) (q,F) (q, (E) ), ( q, a) (q, b,b) (q, ) 對所有對所有 b a,+,*,(,) 算術(shù)算術(shù)(sunsh)表達式的文法表達式的文法 G（N，T，P，E） N E,T,F , T = +,*,(,),a , S = E P: EE+T T ; TT*F F; F( E ) a練習(xí)：針對算術(shù)表達式的練習(xí)：針對算術(shù)表達式的PDA反向

21、反向(fn xin)構(gòu)造其等價文法構(gòu)造其等價文法第19頁/共23頁第十九頁，共23頁。20練習(xí)練習(xí): 從從PDA構(gòu)造等價的上下文無關(guān)構(gòu)造等價的上下文無關(guān)(wgun)文法文法對于右下圖的對于右下圖的 PDA，構(gòu)造，構(gòu)造(guzo)CFG G = (N,0,1,P,S) ， 其中其中 N = S p,Y,qp,qq0,q1,q2 YZ0,X Start0, Z0 / XZ00, X / XXq2 q1 q0 Z0 , /1, X / 1, X / 產(chǎn)生式集合產(chǎn)生式集合(jh) P 定義如下：定義如下： (1) S q0 , Z0 , q0 ; S q0 , Z0 , q1 ; S q0 , Z0 , q2 ; (5)由由(q0,XZ0) (q0, 0, Z0) 得得 q0Z0qj 0q0Xq