計(jì)算理論基礎(chǔ)章

計(jì)算理論基礎(chǔ)章第一頁(yè)，共一百一十七頁(yè)，2022年，8月28日上下文無(wú)關(guān)文法（CFG）在程序設(shè)計(jì)語(yǔ)言和編譯原理中有著重要的應(yīng)用，因?yàn)樯舷挛臒o(wú)關(guān)文法可以用來(lái)闡述絕大多數(shù)的程序設(shè)計(jì)語(yǔ)言的句法結(jié)構(gòu)。此外上下文無(wú)關(guān)語(yǔ)言也可以作為描述語(yǔ)言翻譯方案的基礎(chǔ)。本章重點(diǎn)討論:CFG的簡(jiǎn)化

CFG的兩種范式下推自動(dòng)機(jī)（PDA）的概念

PDA與CFG之間的等價(jià)轉(zhuǎn)換上下文無(wú)關(guān)語(yǔ)言運(yùn)算的封閉性以及CFL的有關(guān)判定問(wèn)題。第二頁(yè)，共一百一十七頁(yè)，2022年，8月28日3.1

上下文無(wú)關(guān)文法的派生樹(shù)(推導(dǎo)樹(shù))

一個(gè)上下文無(wú)關(guān)文法中的一個(gè)句型的派生過(guò)程可以用—棵樹(shù)來(lái)描述?！纠?-1.1】

給定文法G=({S,A},{a,b},P,S)，其中

P：SaAS|a,ASbA|ba|SS。句型aabbaa的派生過(guò)程就可以用一棵樹(shù)來(lái)描述，如圖3-1.1所示。將此樹(shù)的葉結(jié)點(diǎn)符號(hào)從左到右讀取下來(lái)構(gòu)成的符號(hào)串就是aabbaa。S?a?A??SS?b??Aa?b??a?a圖3-.11aabbaa的派生樹(shù)第三頁(yè)，共一百一十七頁(yè)，2022年，8月28日1．派生樹(shù)的定義設(shè)文法G=(ＶＮ,ＶＴ,Ｐ,S)是上下文無(wú)關(guān)文法,如果一棵有序樹(shù)滿足下面四個(gè)條件，則它是棵派生樹(shù)：(1)它的每個(gè)結(jié)點(diǎn)標(biāo)記的符號(hào)是(ＶＮ∪ＶＴ∪{ε})中的符號(hào)；(2)根結(jié)點(diǎn)標(biāo)記開(kāi)始變?cè)猄；(3)內(nèi)結(jié)點(diǎn)標(biāo)記的符號(hào)是變?cè)?，即是ＶＮ中的符?hào)。(4)如果一個(gè)內(nèi)結(jié)點(diǎn)標(biāo)記為A，且X1,X2,…,Xk是A的從左到右的所有子結(jié)點(diǎn),則AX1X2…Xk是P中一個(gè)產(chǎn)生式。(5)如果一個(gè)結(jié)點(diǎn)標(biāo)記符號(hào)是ε，則它是其父結(jié)點(diǎn)的唯一兒子結(jié)點(diǎn)。第四頁(yè)，共一百一十七頁(yè)，2022年，8月28日其中第(5)條是為了防止下面情況發(fā)生：如產(chǎn)生式Aa(a是個(gè)終極符)被誤認(rèn)為是Aaε或Aεa，而在派生樹(shù)中被畫(huà)成如圖3-2形式。2．派生樹(shù)的結(jié)果設(shè)T是棵派生樹(shù)，將此樹(shù)的葉結(jié)點(diǎn)符號(hào)從左到右依次讀取下來(lái)構(gòu)成的符號(hào)串就是此派生樹(shù)的結(jié)果。例如，圖3-1.1派生樹(shù)的結(jié)果就是aabbaa。3．派生樹(shù)與句型的派生關(guān)系設(shè)G=(ＶＮ,ＶＴ,Ｐ,S)是CFG，如果G中有派生S*α，則在G中必有一棵以α為結(jié)果的派生樹(shù)。反之，如果G中有一棵以α為結(jié)果的派生樹(shù)，則G中也必有派生S*

α?？梢哉f(shuō)派生與派生樹(shù)是一一對(duì)應(yīng)的。A??ε?Aa?ε??a圖3-1.2第五頁(yè)，共一百一十七頁(yè)，2022年，8月28日4．最左派生與最右派生所謂最左派生，就是在一個(gè)派生的每一步都是對(duì)句型中最左邊的變?cè)M(jìn)行替換。例如，例3-1中aabbaa的派生：

SaASaSbASaabASaabbaSaabbaa，此派生是最左派生。所謂最右派生，就是在一個(gè)派生的每一步都是對(duì)句型中最右邊的變?cè)M(jìn)行替換。

SaASaAaaSbAaaSbbaaaabbaa,此派生是最右派生。5．上下文無(wú)關(guān)文法的二義性設(shè)G是個(gè)CFG，如果它的某個(gè)句子有兩棵不同構(gòu)的派生樹(shù)，則稱G是二義性的上下文無(wú)關(guān)文法。第六頁(yè)，共一百一十七頁(yè)，2022年，8月28日【例3-1.2】

給定CFGG=({S},{a,b},P,S)，其中P：

SaSbS|bSaS|ε。句子abab的兩棵不同構(gòu)的派生樹(shù)，如圖3-1.3所示。圖3-1.3abab的兩棵不同構(gòu)的派生樹(shù)S?a?S??Sb?S??aε??ε?ε?S?bS?a?S??Sb??Sa?ε??εε?S??b這說(shuō)明此CFGG是有二義性的。第七頁(yè)，共一百一十七頁(yè)，2022年，8月28日3.2

上下文無(wú)關(guān)文法的簡(jiǎn)化

一個(gè)上下文無(wú)關(guān)文法有時(shí)可以去掉一些符號(hào)，或者去掉一些產(chǎn)生式以后，仍然和原來(lái)的文法等價(jià)，這就是所謂文法的簡(jiǎn)化。這里簡(jiǎn)化文法主要是指：去掉無(wú)用符號(hào)、去掉ε產(chǎn)生式和去掉單一產(chǎn)生式。1．去掉無(wú)用符號(hào)

定義：給定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，如果在G中存在派生S*αXβ*w，其中w∈ＶＴ*，X∈ＶＮ∪ＶＴ，則稱符號(hào)X是有用的，否則X是無(wú)用的。簡(jiǎn)單地說(shuō)，無(wú)用符號(hào)就是G中對(duì)任何w∈L(G)的派生中都不會(huì)出現(xiàn)的符號(hào)。第八頁(yè)，共一百一十七頁(yè)，2022年，8月28日【例3-2.1】給定文法G=({S,A,B,C},{a,b},P,S)，其中P：SAB|a,ABC|a,Cb。G中有派生：可見(jiàn)再往下就無(wú)法推導(dǎo)了，因而由S只能推出a，不能推出其他符號(hào)串。所以此文法中，A、B、C、b都是無(wú)用的符號(hào)，只有S和a是有用符號(hào)。如何去掉無(wú)用符號(hào)？分兩步走，使用兩個(gè)引理，就可以做到這一點(diǎn)。下面介紹這兩個(gè)引理。第九頁(yè)，共一百一十七頁(yè)，2022年，8月28日引理3-2.1給定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，且L(G)≠Φ，可以找到一個(gè)與G等價(jià)的CFGG’=(ＶＮ’,ＶＴ,Ｐ’,S)，使得每個(gè)A∈ＶＮ’，都有w∈ＶＴ*，且在G’中有A*w。證明：1）求ＶＮ’的算法：begin⑴OLDＶＮ:=Φ⑵NEWＶＮ:={A|Aw∈P且w∈ＶＴ*}⑶WhileOLDＶＮ≠NEWＶＮdobegin⑷OLDＶＮ:=NEWＶＮ⑸

NEWＶＮ:=OLDＶＮ∪{A|Aα∈P,且α∈(ＶＴ∪

OLDＶＮ)*}end⑹

ＶＮ’:=NEWＶＮ,end第十頁(yè)，共一百一十七頁(yè)，2022年，8月28日下面證明此算法的有效性。顯然對(duì)任何變?cè)狝∈NEWＶＮ,不論A是在第⑵步還是在第⑸步加入到NEWＶＮ中的,都有派生A*w,其中w∈ＶＴ*。只證明G中任何派生A*w，w∈ＶＴ*,必有A∈NEWＶＮ。(對(duì)派生的步數(shù)歸納證明)a）若此派生是一步完成的，即有Aw，則說(shuō)明P中有產(chǎn)生式Aw，于是A在算法的第⑵步被添加到NEWＶＮ中。b）假設(shè)G中派生A*w是少于k步完成的,則A∈NEWＶＮ。c）當(dāng)G中有k步派生AX1X2…Xnk-1w，不妨設(shè)w=w1w2…wn，其中Xi*wi，(i=1,2,…,n)，而且由于這些派生的步數(shù)少于k步，如果Xi是變?cè)?，則根據(jù)假設(shè)b）得Xi最終會(huì)加入到NEWＶＮ中。在執(zhí)行算法的第⑷步時(shí)OLDＶＮ:=NEWＶＮ,當(dāng)最后一個(gè)Xi加入OLDＶＮ時(shí)，在執(zhí)行算法的第⑸步時(shí)，就將A加入到NEWＶＮ中。

第十一頁(yè)，共一百一十七頁(yè)，2022年，8月28日這說(shuō)明此算法是有效的，即凡是可以推出終極符串的變?cè)紩?huì)添加到NEWＶＮ中。于是，最后得到變?cè)希郑巍?）構(gòu)造文法G’：G’＝(ＶＮ’,ＶＴ,Ｐ’,S)，其中

P’：由P中只含有(ＶＮ’∪ＶＴ)的符號(hào)的產(chǎn)生式構(gòu)成的。3）下面證明L(G)=L(G’)a）顯然有L(G’)L(G)，因?yàn)椋郑巍郑危琍’Ｐ，所以G’中任何派生S*w，在G中也有S*w。所以L(G’)L(G)。b）證明L(G)L(G’)，(反證法)任取w∈L(G)，假設(shè)wL(G’),則說(shuō)明在G中w的派生S*w中必用到P－P’中的產(chǎn)生式，即用到了ＶＮ－ＶＮ’中的變?cè)?，而這些變?cè)帜芡瞥鼋K極符串，這與上面證明的此算法有效矛盾。所以必有w∈L(G’),從而L(G)L(G’)。最后得L(G)=L(G’)。第十二頁(yè)，共一百一十七頁(yè)，2022年，8月28日【例3-2.2】

給定CFGG=({S,A,B,C},{a,b},P,S)，其中P：SA|B,AaB|bS|b,BAB|Ba,CAS|b求一個(gè)與之等價(jià)的文法G’，使得G’中的每個(gè)變?cè)伎梢酝瞥鼋K極符串。解：對(duì)G應(yīng)用引理3-2.1，執(zhí)行上述算法，得到的結(jié)果如表3-2.1所示。

循環(huán)次數(shù)i初值123OLDＶＮNEWＶＮ當(dāng)算法執(zhí)行第三次循環(huán)時(shí)，判定OLDＶＮ=NEWＶＮ,算法終止。最后得G’CFGG’=({S,A,C},{a,b},P’,S),其中P’：SA,AbS|b,CAS|b實(shí)際上，只去掉了不能推出終極符串的變?cè)狟。{A,C,S}{A,C}

Φ{A,C}{A,C,S}{A,C,S}第十三頁(yè)，共一百一十七頁(yè)，2022年，8月28日引理3-2.2

給定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，

可以找到一個(gè)與G等價(jià)的CFGG’，

G’=(ＶＮ’,ＶＴ’,Ｐ’,S)，使得每個(gè)X∈(ＶＮ’∪ＶＴ’)，都有α,β∈(ＶＮ’∪ＶＴ’)*，且在G’中有派生S*αXβ。證明：1．執(zhí)行下面迭代算法求ＶＮ’和ＶＴ’。

1）置初值：ＶＮ’:={S}，ＶＴ’:=Φ;2）如果A∈ＶＮ’，在P中又有產(chǎn)生式Aα1|α2|…|αm

，則可以將α1,α2,…,αm中的所有變?cè)拥剑郑巍校瑢ⅵ?,α2,

…,αm中的所有終極符加到中ＶＴ’中。重復(fù)2)。

3）若沒(méi)有新的符號(hào)可加入到ＶＮ’、ＶＴ’中，算法停止。最后得到ＶＮ’、ＶＴ’。第十四頁(yè)，共一百一十七頁(yè)，2022年，8月28日2．構(gòu)造P’：是由P中只含有(ＶＮ’∪ＶＴ’)中的符號(hào)的產(chǎn)生式構(gòu)成的。3．證明L(G)=L(G’)a）顯然有L(G’)L(G)，因?yàn)椋郑巍郑?，ＶT’ＶT，P’Ｐ，所以G’中任何派生S*w，在G中也有S*w。所以L(G’)L(G)。b）證明L(G)L(G’)，任取w∈L(G)，不妨設(shè)w在G中的派生為S*αXβ*w，其中α,β∈(ＶＮ∪ＶＴ)*，由上述算法可知，在此派生中出現(xiàn)的所有符號(hào)，都不會(huì)因?yàn)閷?duì)G使用此引理而被去掉，所以這些符號(hào)必在ＶＮ’∪ＶＴ’中，此派生中所用到的產(chǎn)生式也在P’中，所以這個(gè)派生在G’中也可以實(shí)現(xiàn)，因而必有w∈L(G’)。故L(G)L(G’)。最后得L(G)=L(G’)。第十五頁(yè)，共一百一十七頁(yè)，2022年，8月28日定理3-2.1

設(shè)L是一個(gè)非空的上下文無(wú)關(guān)語(yǔ)言，則L可由一個(gè)不含無(wú)用符號(hào)的上下文無(wú)關(guān)文法產(chǎn)生。證明：設(shè)G=(ＶＮ,ＶＴ,Ｐ,S)是個(gè)CFG，且L(G)=L≠Φ。先對(duì)G用引理3-2.1處理后，得G’＝(ＶＮ’,ＶＴ,Ｐ’,S)，再將G’用引理3-2.2處理得G’’＝(ＶＮ’’,ＶＴ’’,Ｐ’’,S)，由兩個(gè)引理得L(G’’)=L(G)。下面證明G’’中不含無(wú)用符號(hào)。假設(shè)G’’中有無(wú)用符號(hào)Y。根據(jù)引理3-2.2得，在G’’中必存在派生S*αYβ，其中α,β∈(ＶＮ’’∪ＶＴ’’)

*，因?yàn)镚’’的符號(hào)也都是G’中的符號(hào)，所以此派生在G’中也可以實(shí)現(xiàn)，又根據(jù)引理3-2.1得，α和β中的變?cè)约癥都可以推出終極符串，于是G’中有派生：S*αYβ*w，w∈ＶＴ*，又因?yàn)榕缮罽β*w中的符號(hào)不會(huì)因?yàn)閷?duì)G’用引理3-2.2而被去掉，所以在G’’中也會(huì)實(shí)現(xiàn)派生αYβ*

w，于是G’’中也有派生S*αYβ*w，這與符號(hào)Y是無(wú)用符號(hào)矛盾。所以G’’中不含無(wú)用符號(hào)。第十六頁(yè)，共一百一十七頁(yè)，2022年，8月28日值得注意的是，去掉G中無(wú)用符號(hào)時(shí)，一定要先用引理3-2.1，后用引理3-2.2。應(yīng)用引理的次序不可顛倒，否則可能遺漏一些無(wú)用符號(hào)。請(qǐng)看下面例子?！纠?-2.3】

給定CFGG=({S,A,B},{a,b},P,S)，其中P：SAB|a,Aa求一個(gè)與之等價(jià)的文法G”，使得G”中不含無(wú)用符號(hào)。解：先對(duì)G應(yīng)用引理3-2.1方法處理，執(zhí)行此算法得到的結(jié)果如表3-2.2所示。循環(huán)次數(shù)i初值123OLDＶＮ

Φ{S,A}NEWＶＮ{S,A}{S,A}第十七頁(yè)，共一百一十七頁(yè)，2022年，8月28日當(dāng)算法執(zhí)行第二次循環(huán)時(shí)，判定OLDＶＮ＝NEWＶＮ，算法終止。最后得G’：CFGG’=({S,A},{a,b},P,S)，其中

P’：Sa,Aa。再對(duì)G’用引理3-2.2處理，執(zhí)行算法的結(jié)果如表3-2.3所示：循環(huán)次數(shù)i初值123ＶＮ’’{S}{S}ＶT’’

Φ{a}最后得文法G’’＝({S},{a},P’’,S)，其中P’’={Sa}。但是，如果先對(duì)G用引理3-2.2，后用引理3-2.1就得到如下結(jié)果：第十八頁(yè)，共一百一十七頁(yè)，2022年，8月28日對(duì)G用引理3-2.2執(zhí)行算法的結(jié)果，如表3-2.4所示：循環(huán)次數(shù)i初值123ＶＮ’{S}{S,A,B}ＶT’

Φ{a}得文法G’=({S,A,B},{a},P’,S)，P’：SAB|a,Aa。再對(duì)G’用引理3-2.1執(zhí)行算法的結(jié)果如表3-2.5所示：循環(huán)次數(shù)i初值123OLDＶＮ’’Φ{S,A}NEWＶＮ’’

{S,A}{S,A}最后得文法G’’=({S,A},{a},P’’,S)，P’’：Sa,Aa。顯然，這樣做，無(wú)用符號(hào)A沒(méi)有被去掉。可見(jiàn)去掉文法中無(wú)用符號(hào)時(shí)，使用這兩個(gè)引理的先后次序是很重要的。第十九頁(yè)，共一百一十七頁(yè)，2022年，8月28日2．去掉ε產(chǎn)生式定義：所謂ε產(chǎn)生式，就是形如Aε的產(chǎn)生式，其中A為變?cè)?。給定CFGG，如果εL(G)，則G中所有ε產(chǎn)生式都可以去掉。如果ε∈L(G)，則除了開(kāi)始變?cè)猄的ε產(chǎn)生式(即Sε)外，其余ε產(chǎn)生式都可以去掉。為了去掉ε產(chǎn)生式，先定義一個(gè)概念可為零的變?cè)?。定義：設(shè)A是個(gè)變?cè)?，如果A*ε，則稱A是可為零的。去掉CFGG中的ε產(chǎn)生式的思路是：首先，找出G中所有可為零的變?cè)?。然后，?duì)P中每個(gè)形如AX1X2…Xn的產(chǎn)生式進(jìn)行如下處理：要添加一些這樣的產(chǎn)生式：這些產(chǎn)生式是通過(guò)去掉X1X2…Xn中某些可為零的變?cè)玫降?。但是，如果所有Xi(i=1,2,…n)都是可為零的，則不可全去掉，因?yàn)槟菢訒?huì)產(chǎn)生新的ε產(chǎn)生式Aε。第二十頁(yè)，共一百一十七頁(yè)，2022年，8月28日【例3-2.6】有產(chǎn)生式：SaSAbB,設(shè)A與B都是可為零的，則由這個(gè)產(chǎn)生式變成如下四個(gè)產(chǎn)生式：SaSAbB,SaSbB(去掉A),SaSAb(去掉B),SaSb(A和B全去掉)。注意，要將所有可能的情況均考慮到，才能保證新的文法與原文法等價(jià)。定理3-2.2

給定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，可以找到一個(gè)不含無(wú)用符號(hào)，又無(wú)ε產(chǎn)生式的CFGG’，使得L(G’)＝L(G)－{ε}。證明：假設(shè)G已經(jīng)去掉了無(wú)用符號(hào)，從G中去掉ε產(chǎn)生式后得到文法G’，令G’＝(ＶＮ,ＶＴ,Ｐ’,S)，其中P’構(gòu)成如下：第二十一頁(yè)，共一百一十七頁(yè)，2022年，8月28日1．用下面迭代算法確定G中可為零的變?cè)希?

。begin

⑴OLDＶ0:=Φ⑵NEWＶ0:={A|Aε∈P}⑶WhileOLDＶ0≠NEWＶ0dobegin⑷OLDＶ0:=NEWＶ0⑸NEWＶ0:=OLDＶ0∪{A|Aα∈P,且∈(OLDＶ0)*}end⑹Ｖ0:=NEWＶ0

end當(dāng)OLDＶ0=NEWＶ0時(shí)，算法終止，最后得到可為零的變?cè)希?。此算法與引理3-2.1中算法相似，類似可證此算法的有效性第二十二頁(yè)，共一百一十七頁(yè)，2022年，8月28日2．構(gòu)造P’：如果AX1X2…Xn∈P，則將所有形如Aα1α2…αn的產(chǎn)生式都加到P’中，其中

⑴

如果Xi不是可為零的，則αi＝Xi。

⑵

如果Xi是可為零的，則αi＝Xi或者αi＝ε。但是，如果所有Xi(i=1,2,…n)都是可為零的，則不可所有αi＝ε。3．用歸納法證明：對(duì)任何A∈ＶＮ,任何w∈ＶＴ＋

，有如果AG’*w，當(dāng)且僅當(dāng)

AG*w。1）先證明充分性。設(shè)G中有派生AG*w，w≠ε。⑴如果此派生是一步完成的，即G中有派生AGw，則Aw∈P，因?yàn)閣≠ε，所以Aw∈P’，所以G’中也有派生AG’*w。⑵假設(shè)G中派生AG*w是少于k步完成的，則G’中有派生AG’*w。第二十三頁(yè)，共一百一十七頁(yè)，2022年，8月28日⑶

當(dāng)G中有派生AGX1X2…XnG*w＝w1w2…wn是由k步完成的時(shí)，其中Xi∈(ＶＴ∪ＶＮ)且有XiG*wi(i=1,2,…,n)，其中有的wi可能為ε。如果某個(gè)wi＝ε，則對(duì)應(yīng)的Xi是可為零的變?cè)?。由G中派生AGX1X2…Xn得AX1X2…Xn∈P，根據(jù)P’的構(gòu)成得，必有產(chǎn)生式Aα1α2…αn∈P’，其中a）如果XiG*

wi≠ε，則αi＝Xi，于是有αiG*

wi，且此派生少于k步完成，由假設(shè)⑵得G’中有派生αiG’*wi。b）如果XiG*

wi＝ε，則Xi是可為零的變?cè)?，與Xi對(duì)應(yīng)αi＝ε，于是有αiG’*

wi＝ε。最后G’中有派生：

AG’

α1α2…αnG’*

w1α2…αnG’*

w1w2α3…αnG’*

w1w2…wn＝w,即G’中有派生AG’*w,充分性成立。第二十四頁(yè)，共一百一十七頁(yè)，2022年，8月28日2）再證明必要性。設(shè)G’中有派生AG’*w，顯然w≠ε。⑴.如果此派生是一步完成的，即G’中有Aw，則Aw∈P’，因?yàn)閣≠ε，于是P中有產(chǎn)生式Aw或者Aα，使得從α中去掉某些可為零的變?cè)蟮玫絯，總之G中有派生AGw，或者AGαG*

w。⑵.

假設(shè)G’中有派生AG’*w是少于k步完成的，則G中有派生AG*w。⑶.當(dāng)G’中派生AG’X1X2…XnG’*w1w2…wn＝w是由k步完成時(shí)，此派生的第一步派生是用P’中的產(chǎn)生式AX1X2…Xn。根據(jù)P’的構(gòu)成知，P中必存在產(chǎn)生式Aβ，使得從β中去掉某些可為零的變?cè)缶偷玫絏1X2…Xn，于是G中有派生：AGβG*

X1X2…Xn,第二十五頁(yè)，共一百一十七頁(yè)，2022年，8月28日而在G’的第二步及以后的派生X1X2…XnG’*w1w2…wn＝w中，令XiG’*wi(i=1,2,..,n)，由于這些派生的步數(shù)少于k，由假設(shè)⑵得，XiG*wi，于是G中也有派生：

AGβG*X1X2…XnG*

w1X2…XnG*

w1w2X3…Xn

G*

w1w2…wn＝w。所以必要性成立。最后得此結(jié)論成立。即如果AG’*w，當(dāng)且僅當(dāng)

AG*w。當(dāng)A=S時(shí)，則有SG’*w，當(dāng)且僅當(dāng)

SG*w。于是有L(G’)=L(G)－{ε}。第二十六頁(yè)，共一百一十七頁(yè)，2022年，8月28日3．去掉單一產(chǎn)生式定義：所謂單一產(chǎn)生式，就是形如AB的產(chǎn)生式，其中A和B都是變?cè)６ɡ?-2.3

每個(gè)不含有ε的上下文無(wú)關(guān)語(yǔ)言L，都可以由一個(gè)不含無(wú)用符號(hào)、無(wú)ε產(chǎn)生式、也無(wú)單一產(chǎn)生式的上下文無(wú)關(guān)文法產(chǎn)生。證明：令G＝(ＶＮ,ＶＴ,Ｐ,S)是一個(gè)不含有無(wú)用符號(hào)，無(wú)ε產(chǎn)生式的上下文無(wú)關(guān)文法，且L(G)=L。構(gòu)造一個(gè)CFGG’＝(ＶＮ,ＶＴ,Ｐ’,S)，其中P’的構(gòu)成如下：⑴

包含P中所有非單一產(chǎn)生式。⑵

對(duì)任何A,B∈ＶＮ，如果有AG*B，且Bα1|α2|…|αn是P中B的所有非單一產(chǎn)生式，則把所有Aα1|α2|…|αn加到P’中。第二十七頁(yè)，共一百一十七頁(yè)，2022年，8月28日(例如G中有產(chǎn)生式：AB,BC,CD,Bα,Cβ,Dγ，于是有A*B,A*C,A*D，B*C，B*D,C*D，則G’中有產(chǎn)生式：Aα|β|γ，Bα|β|γ，Cβ|γ，Dγ。)下面證明L(G’)=L(G)a）首先證明L(G’)L(G)容易看出任何Aα∈P’，則G中必有派生AG*α。因?yàn)椋绻鸄α∈P，G中當(dāng)然有派生AGα，如果AαP，則必有變?cè)狟，使得G中有派生AG*BGα。所以對(duì)任何w∈L(G’),即SG’*w，此派生中用到的所有產(chǎn)生式Aα∈P’,則G中必有派生AG*α。所以G中必有派生SG*w，所以w∈L(G)。因而L(G’)L(G)。第二十八頁(yè)，共一百一十七頁(yè)，2022年，8月28日b）再證明L(G)L(G’)任取w∈L(G)，設(shè)w在G中的最左派生如下：

S＝α0α1

α2

α3…αn－1

αn

＝w，下面分兩種情況討論：①如果上述派生用的都是非單一產(chǎn)生式，則這些產(chǎn)生式在P’中也有，所以這些派生在G’中也可以實(shí)現(xiàn)。②如果上述派生既用了單一產(chǎn)生式，也用了非單一產(chǎn)生式，不妨取出其中一段：

αi－1

αi

αi+1…

αj

αj+1,

非單一單一非單一設(shè)從αi-1

到αi

用的是非單一產(chǎn)生式，從αi到αj用的是單一產(chǎn)生式，αj到αj+1用的又是非單一產(chǎn)生式。下面主要考察G中從αi到αj＋1的派生(此派生是先用單一產(chǎn)生式，后用非單一產(chǎn)生式)，看看這段派生在G’中是如何實(shí)現(xiàn)的。第二十九頁(yè)，共一百一十七頁(yè)，2022年，8月28日先看看從αi到αj用的是單一產(chǎn)生式的派生，不妨設(shè)

αi＝y(tǒng)Aiγ,αi+1＝y(tǒng)Ai+1γ,…αj＝y(tǒng)Ajγ，其中y∈ＶＴ*，γ∈(ＶＴ∪ＶＮ)*從αi到αj的派生寫(xiě)成yAiγyAi+1γ…yAjγ，這些派生都是用單一產(chǎn)生式進(jìn)行的。實(shí)際上相當(dāng)于派生AiAi+1

…Aj，所以有Ai*Aj。再看看αj到αj+1的派生αj

αj+1，它用的是非單一產(chǎn)生式，不妨設(shè)αj+1＝y(tǒng)βγ，β∈(ＶＴ∪ＶＮ)*，于是此派生寫(xiě)成yAjγyβγ，實(shí)際上此派生用的是非單一產(chǎn)生式Ajβ。于是G中有派生Ai*Ajβ，根據(jù)P’的構(gòu)成，則P’中必有產(chǎn)生式Aiβ。于是在G’中有派生：αi＝y(tǒng)Aiγyβγ＝αj+1，即在G’中從αi到αj+1的派生是一步完成的。所以當(dāng)SG*w用了兩種產(chǎn)生式時(shí)，G’中也有派生SG’*w。所以L(G)L(G’)。最后得L(G)＝L(G’)。第三十頁(yè)，共一百一十七頁(yè)，2022年，8月28日作業(yè)題1．給定CFGG=({S,A,B,C},{a,b,c},P,S)，其中，

P：S→A|B,A→Ab|bS|C|b,B→AB|Ba,C→AS∣b,去掉G中的無(wú)用符號(hào)和單一生成式。2．給定CFGG=({S,A,B,C},{a,b},P,S)，其中，

P：S→ABC,A→BB|ε,B→CC|a,C→AA|b,去掉G中的ε生成式。第三十一頁(yè)，共一百一十七頁(yè)，2022年，8月28日

3.3

上下文無(wú)關(guān)文法的Chomsky范式

(ChomskyNormalForm，CNF)

Chomsky范式形式是：每個(gè)產(chǎn)生式的形式要么是ABC,要么是Da,其中A,B,C,D是變?cè)?，a是終極符。這種范式在形式語(yǔ)言的理論和應(yīng)用上都具有重要的意義。下面介紹如何把一個(gè)CFGG寫(xiě)成CNF形式。定理3-3.1

任何一個(gè)不含有ε的CFLL都可由一個(gè)具有CNF形式的CFGG產(chǎn)生。證明：由定理3-2.3可知，對(duì)一個(gè)不含有ε的CFLL都可由一個(gè)不含無(wú)用符號(hào)、無(wú)ε產(chǎn)生式、無(wú)單一產(chǎn)生式的CFGG產(chǎn)生。不妨設(shè)CFGG=(ＶＮ,ＶＴ,Ｐ,S)是一個(gè)不含無(wú)用符號(hào)、無(wú)ε產(chǎn)生式、無(wú)單一產(chǎn)生式的CFG,且L(G)=L。第三十二頁(yè)，共一百一十七頁(yè)，2022年，8月28日1.先對(duì)P中產(chǎn)生式做如下處理：⑴保留右側(cè)只有一個(gè)符號(hào)的產(chǎn)生式，(此符號(hào)是終極符，)⑵

處理產(chǎn)生式AX1X2…Xn(n≥2)：如果其中Xi是終極符a，則引入新的變?cè)狢a，用Ca代替a，同時(shí)添加新的產(chǎn)生式Caa。經(jīng)過(guò)此步處理后，使得產(chǎn)生式的形式只有兩種：一種是Aa，a是終極符；另一種是AB1B2…Bn，其中每個(gè)Bi都是變?cè)?包括新引入的變?cè)?。⑶

處理產(chǎn)生式AB1B2…Bn(n≥3)(因?yàn)閚=2時(shí)符合要求)，引進(jìn)新的變?cè)狣1D2…Dn-2，此產(chǎn)生式用下面產(chǎn)生式替換：

AB1D1,D1B2D2,D2B3D3,…,

Dn-3Bn-2Dn-2,Dn-2Bn-1Bn。顯然用這n－1個(gè)產(chǎn)生式代替AB1B2…Bn，這是個(gè)等價(jià)變換。經(jīng)過(guò)此步處理后，所有產(chǎn)生式的形式就具有CNF形式了:ABC,Da,其中A,B,C,D是變?cè)?，a是終極符。第三十三頁(yè)，共一百一十七頁(yè)，2022年，8月28日2.構(gòu)造新的CFGG’=(ＶＮ’,ＶＴ,Ｐ’,S)，其中ＶＮ’中除了原來(lái)ＶＮ中的變?cè)?，還含有新增加的所有變?cè)?。Ｐ’就是由?jīng)過(guò)上述處理后得到的具有CNF形式的產(chǎn)生式構(gòu)成。3.容易證明L(G’)=L(G),這里證明從略?！纠?-3.1】G是個(gè)定義算術(shù)表達(dá)式的CFGG=({E,T,F},{a,b,+,*,(,)},P,E),其中E表示算術(shù)表達(dá)式；T表示項(xiàng)；F表示因子。P含有下面這些產(chǎn)生式：

EE+T|TTT*F|FF(E)|a|b求一個(gè)具有CNF形式的CFGG’,使得L(G’)=L(G)。解：1．先簡(jiǎn)化G，因?yàn)镚中不含無(wú)用符號(hào)，也無(wú)ε產(chǎn)生式，所以只去掉單一產(chǎn)生式。

1）去掉TF，添加如下產(chǎn)生式：T(E)|a|b

2）去掉ET，添加如下產(chǎn)生式：ET*F|(E)|a|b2．保留符合要求的產(chǎn)生式：Ea|b,Ta|b,Fa|b第三十四頁(yè)，共一百一十七頁(yè)，2022年，8月28日3．處理產(chǎn)生式AX1X2…Xn(n≥2)：終極符Xi變成變?cè)?/p>

EE+T變成

EEC+TC++ET*F變成

ETC*FC**E(E)變成

EC(EC)C((C)

)TT*F變成

TTC*F

T(E)變成TC(EC)F(E)變成FC(EC)4．處理產(chǎn)生式AB1B2…Bn(Bi都是變?cè)?n≥3)：引進(jìn)新的變?cè)狣1,D2,

…,Dn-2。

EEC+T變成EED1D1C+TETC*F變成ETD2D2C*FEC(EC)

變成EC(D3D3EC)TTC*F變成TTD2TC(EC)

變成TC(D3FC(EC)

變成FC(D3第三十五頁(yè)，共一百一十七頁(yè)，2022年，8月28日5．最后得具有CNF形式的CFGG’=(ＶＮ’,ＶＴ,P’,E),其中ＶＮ’＝{E,T,F,C+,C*,C(,C),D1,D2,D3}

ＶＴ＝{a,b,+,*,(,)}P’:EED1|TD2|C(D3|a|b

TTD2|C(D3|a|b

FC(D3|a|bD1C+TD2C*FD3EC)C++C**C((C))第三十六頁(yè)，共一百一十七頁(yè)，2022年，8月28日3.4

CFG的Greibach范式

(GNF)下面我們討論CFG的另外一種范式――Greibach范式(GNF)。定義：CFGG=(ＶＮ,ＶＴ,Ｐ,S)，P中產(chǎn)生式形式都是：Aaα，其中a是一個(gè)終極符，a∈ＶＴ，α是變?cè)?hào)串，α∈ＶＮ*，則稱此文法具有GNF形式。任何一個(gè)不含有ε的CFL，都可以由一個(gè)具有GNF形式的CFG產(chǎn)生。那么如何將一個(gè)CFG變成具有GNF形式的CFG，應(yīng)用下面兩個(gè)引理可以實(shí)現(xiàn)。

第三十七頁(yè)，共一百一十七頁(yè)，2022年，8月28日引理3-4.1

設(shè)G=(ＶＮ,ＶＴ,Ｐ,S)是個(gè)CFG，Aα1Bα2是P中一個(gè)產(chǎn)生式，又Bβ1|β2|β3…|βm是P中變?cè)狟的所有產(chǎn)生式。又令G’=(ＶＮ,ＶＴ,Ｐ’,S)，其中P’構(gòu)成如下：從P中刪除Aα1Bα2，再添加產(chǎn)生式Aα1β1α2|α1β2α2|α1β3α2|…|α1βmα2，則L(G’)=L(G)。證明：顯然有L(G’)L(G)。因?yàn)槿绻鸄α1βiα2(1≤i≤m)用在G’的一個(gè)派生中，雖然在G中沒(méi)有此產(chǎn)生式，但是在G中有如下派生：Aα1Bα2α1βiα2(1≤i≤m)。所以G’中的任何派生在G中也可以實(shí)現(xiàn)。所以L(G’)L(G)。第三十八頁(yè)，共一百一十七頁(yè)，2022年，8月28日再證明L(G)L(G’)這里只需注意到G與G’的差別是：只有Aα1Bα2是在G中而不在G’中的產(chǎn)生式，而G中其余的產(chǎn)生式G’中也有。所以只要Aα1Bα2用于G的一個(gè)派生中，在其后的某一步推導(dǎo)肯定用到產(chǎn)生式Bβi，用以改變變?cè)狟，而這二步推導(dǎo)在G’中用一步派生Aα1βiα2(1≤i≤m)以代之。所以

L(G)L(G’)。最后得L(G’)＝L(G)。下面介紹的引理是處理帶有左遞歸的產(chǎn)生式。這里所謂左遞歸的產(chǎn)生式形式：AAα,

顯然左遞歸不去掉，就無(wú)法變成GNF形式。因?yàn)橐螽a(chǎn)生式的右側(cè)第一個(gè)符號(hào)是終極符。當(dāng)然這不像上面引理那么簡(jiǎn)單。應(yīng)用下面引理解決這個(gè)問(wèn)題。

第三十九頁(yè)，共一百一十七頁(yè)，2022年，8月28日引理3-4.2

設(shè)G=(ＶＮ,ＶＴ,Ｐ,S)是個(gè)CFG，AAα1|Aα2|…|Aαm是P中變?cè)狝的所有帶有左遞歸的產(chǎn)生式。又Aβ1|β2|β3|…|βn是P中變?cè)狝的其余的產(chǎn)生式。構(gòu)造CFGG’=(ＶＮ∪{Z},ＶＴ,Ｐ’,S)，其中P’構(gòu)成如下：將P中變?cè)狝的產(chǎn)生式用下面產(chǎn)生式替換：

Aβi|βiZ(1≤i≤n)Zαj|αjZ(1≤j≤m)則L(G’)＝L(G)。證明：此引理的處理思路，就是用變?cè)猌的右遞歸代替變?cè)狝的左遞歸。任取x∈L(G),考慮x的最左派生，

1.如果此派生只使用Aβi型的產(chǎn)生式，則G’中也有這種產(chǎn)生式，所以x的派生在G’中也可以實(shí)現(xiàn)。

2.如果此派生先用AAαj

，最后必用Aβi，才可以消去變?cè)狝，例如有如下派生：第四十頁(yè)，共一百一十七頁(yè)，2022年，8月28日AAαj1Aαj2αj1…Aαjkαjk-1…αj2αj1βiαjkαjk-1…αj2αj1

AAAAAαj1αj2αjkβiAZZZZαj1αj2αjkβi這個(gè)派生在G’中也可以實(shí)現(xiàn)，如下所示：AβiZβiαjkZ…βiαjkαjk-1…αj2Z

βiαjkαjk-1…αj2αj1第四十一頁(yè)，共一百一十七頁(yè)，2022年，8月28日所以x∈L(G’)。反之x∈L(G’)，x在G’中的派生，類似可證在G中也可以實(shí)現(xiàn)，所以x∈L(G)。最后得L(G’)=L(G)。第四十二頁(yè)，共一百一十七頁(yè)，2022年，8月28日定理3-4.1(Greibach定理)

每個(gè)不含有ε的CFLL，都可以由一個(gè)具有GNF形式的CFG產(chǎn)生。證明：令G=(ＶＮ,ＶＴ,Ｐ,A1)是個(gè)CFG，L(G)=L，εL(G)，假設(shè)G已經(jīng)具有CNF形式。不妨設(shè)ＶＮ＝{A1,A2,A3,…,An}，按照如下方法處理P中產(chǎn)生式：

1．先暫時(shí)保留形如AiAjAk的產(chǎn)生式，其中i<j。

2．用引理3-4.1處理所有形如AiAjAk的產(chǎn)生式，其中i>j，即用所有Aj產(chǎn)生式的右側(cè)符號(hào)串代替該產(chǎn)生式中的Aj。

3．用引理3-4.2處理帶有左遞歸的產(chǎn)生式AkAkαj|βi，(1≤j≤m)(1≤i≤n)，用下面產(chǎn)生式替換：Aβi|βiZk,Zkαj|αjZk。

4．經(jīng)過(guò)上述處理后，再依次將An,An-1,…,A2,A1產(chǎn)生式以及所有新增加的變?cè)猌k(1≤k≤n)的產(chǎn)生式用引理3-4.1方法處理，使之都變成GNF形式。第四十三頁(yè)，共一百一十七頁(yè)，2022年，8月28日

由于我們對(duì)G的產(chǎn)生式的處理都是使用上面兩個(gè)引理，所以最后得到的具有GNF形式的文法G’必與G等價(jià)，即L(G’)=L(G)。下面我們通過(guò)一個(gè)例子說(shuō)明如何將G變成具有GNF形式的文法G’的過(guò)程?！纠?-4.1】.令G=({A1,A2,A3},{a,b},P,A1)，其中P：⑴A1A2A3,⑵A2A3A1,⑶A2b,⑷A3A1A2,

⑸A3a,將G寫(xiě)成GNF形式。解：1.

先暫時(shí)保留產(chǎn)生式⑴、⑵。2．處理產(chǎn)生式⑷

A3A1A2：用⑴的A1產(chǎn)生式右側(cè)的A2A3替換⑷中A1，得新產(chǎn)生式⑹A3A2A3A2。⑹仍然不滿足要求，再次對(duì)⑹處理：用⑵⑶的A2產(chǎn)生式右側(cè)符號(hào)串分別替換A2，得⑺A3A3A1A3A2,⑻A3bA3A2。這兩個(gè)產(chǎn)生式符合要求。第四十四頁(yè)，共一百一十七頁(yè)，2022年，8月28日3.處理有左遞歸的產(chǎn)生式⑺

A3A3A1A3A2,⑻A3bA3A2，⑸A3a。用引理3-4.2得：A3bA3A2|a|bA3A2Z3|aZ3,Z3A1A3A2|A1A3A2Z3?？梢钥闯?，到此所有A3的產(chǎn)生式都已經(jīng)符合GNF形式了。4．用引理3-4.1將A2、A1產(chǎn)生式變成GNF形式。對(duì)⑵A2A3A1,⑶A2b,應(yīng)用所有A3產(chǎn)生式的右側(cè)符號(hào)串替換A3得：A2bA3A2A1|aA1|bA3A2Z3A1|aZ3A1|b,到此A2已經(jīng)滿足GNF形式了。對(duì)⑴A1A2A3,應(yīng)用所有A2產(chǎn)生式的右側(cè)符號(hào)串替換A2得：A1bA3A2A1A3|aA1A3|bA3A2Z3A1A3|aZ3A1A3|bA3到此A1已經(jīng)滿足GNF形式了。第四十五頁(yè)，共一百一十七頁(yè)，2022年，8月28日5．將所有Z3產(chǎn)生式變成GNF形式，用所有A1產(chǎn)生式得：

Z3A1A3A2變成

Z3bA3A2A1A3A3A2|aA1A3A3A2|bA3A2Z3A1A3A3A2

|aZ3A1A3A3A2|bA3A3A2Z3A1A3A2Z3變成

Z3bA3A2A1A3A3A2Z3|aA1A3A3A2Z3

|bA3A2Z3A1A3A3A2Z3|aZ3A1A3A3A2Z3|bA3A3A2Z3第四十六頁(yè)，共一百一十七頁(yè)，2022年，8月28日最后得文法G’=({A1,A2,A3,Z3},{a,b},P’,A1)，其中P’：A1bA3A2A1A3|aA1A3|bA3A2Z3A1A3|aZ3A1A3|bA3A2bA3A2A1|aA1|bA3A2Z3A1|aZ3A1|bA3bA3A2|a|bA3A2Z3|aZ3Z3bA3A2A1A3A3A2|aA1A3A3A2|bA3A2Z3A1A3A3A2

|aZ3A1A3A3A2|bA3A3A2Z3bA3A2A1A3A3A2Z3|aA1A3A3A2Z3

|bA3A2Z3A1A3A3A2Z3|aZ3A1A3A3A2Z3|bA3A3A2Z3可見(jiàn)G’具有GNF形式。隨便說(shuō)明一下，上邊定理中介紹的方法是個(gè)將具有CNF形式的文法變成GNF形式的一般的方法，有時(shí)不一定嚴(yán)格按照此法去做，即不一定都得先將給定CFGG變成CNF形式后，再寫(xiě)成GNF形式。

第四十七頁(yè)，共一百一十七頁(yè)，2022年，8月28日【例3-4.2】將下面CFGG寫(xiě)成GNF形式。G=({S},{0,1},P,S)，其中

P：S0S0|1S1|00|11。解：因?yàn)榇宋姆ㄋ挟a(chǎn)生式的右側(cè)的第一個(gè)符號(hào)已經(jīng)是終極符，所以問(wèn)題就簡(jiǎn)單了，就不必先將G變成CNF形式，可以直接寫(xiě)成GNF形式。令G’=({S,A,B},{0,1},P’,S)，

P’：S0SA|1SB|0A|1B,A0,B1G’就是與G等價(jià)的具有GNF形式的文法。容易看出L(G)={wwR|w∈{0,1}+}下面用例子驗(yàn)證它們是等價(jià)的。例如，看看它們派生00100100的過(guò)程。在G中的派生：S0S000S00001S10000100100在G’中的派生（最左派生）：S0SA00SAA001SBAA0010ABAA00100BAA001001AA0010010A00100100

第四十八頁(yè)，共一百一十七頁(yè)，2022年，8月28日作業(yè)題：1．給定CFGG=({S,A},{0,1},P,S)，其中，P：S→AA∣0,A→SS∣1,將G寫(xiě)成GNF形式。第四十九頁(yè)，共一百一十七頁(yè)，2022年，8月28日3.5

下推自動(dòng)機(jī)

(PushDownAutomaton,PDA)

下面介紹識(shí)別CFL的自動(dòng)機(jī)——下推自動(dòng)機(jī)。1．PDA的結(jié)構(gòu)有限控制器a1a2a3…………..amZ0Z1Zn-1Zn…….輸入帶：下推棧圖3-5.1PDA的結(jié)構(gòu)輸入帶：帶上存放被識(shí)別的符號(hào)串。有限控制器：存放PDA的狀態(tài)轉(zhuǎn)移函數(shù)。下推棧：后進(jìn)先出的下推棧。

兩個(gè)只讀頭：分別用來(lái)讀取帶上符號(hào)和棧內(nèi)符號(hào)。第五十頁(yè)，共一百一十七頁(yè)，2022年，8月28日2．PDA的形式定義下推自動(dòng)機(jī)M=(K,Σ,Γ,δ,q0,Z0,F)，其中

K——狀態(tài)的有限集合。

Σ——輸入帶上的符號(hào)集合。

Γ——棧內(nèi)符號(hào)集合。

q0——q0∈K，開(kāi)始狀態(tài)。

Z0——Z0∈Γ，開(kāi)始時(shí)棧頂符號(hào)。

F——FK，終止?fàn)顟B(tài)集合。δ：狀態(tài)轉(zhuǎn)移函數(shù)，是映射K×(Σ∪{ε})×Γ2(K×Γ*)。第五十一頁(yè)，共一百一十七頁(yè)，2022年，8月28日有兩種狀態(tài)轉(zhuǎn)移函數(shù)：（1）掃描輸入帶上符號(hào)a，δ(q,a,Z)={(p1,γ1),(p2,γ2),…,(pm,γm)}，

其中q∈K，a∈Σ，Z∈Γ，p1,p2,…,pm∈K,γ1,γ2,…,γm∈Γ*。此動(dòng)作表示：在q狀態(tài)下，當(dāng)前棧頂符號(hào)為Z，讀取帶上符號(hào)a后，狀態(tài)改成pi,，并且用γi代替棧頂符號(hào)Z(1≤i≤m)，然后讀頭右移一個(gè)單元，準(zhǔn)備讀帶上下一個(gè)符號(hào)。（2）ε-動(dòng)作，一般用于讀帶上符號(hào)串的開(kāi)頭或者是末尾。δ(q,ε,Z)={(p1,γ1),(p2,γ2),…,(pm,γm)}此動(dòng)作表示：在q狀態(tài)下，當(dāng)前棧頂符號(hào)為Z，讀取帶上符號(hào)ε(實(shí)際上沒(méi)有讀符號(hào)，或者帶上無(wú)符號(hào)可讀)后，狀態(tài)改成pi,，并且用γi(1≤i≤m)代替棧頂符號(hào)Z,然后，但是讀頭不動(dòng)。

第五十二頁(yè)，共一百一十七頁(yè)，2022年，8月28日注意：假設(shè)棧內(nèi)符號(hào)串γ從底到頂依次是ABCD，則γ要寫(xiě)成DCBA,即棧頂符號(hào)寫(xiě)在左邊，棧底符號(hào)寫(xiě)在右邊。3．通常使用符號(hào)的約定：1）用小寫(xiě)英文字母a、b、c…表示輸入帶上的符號(hào)，即

a,b,c,…∈Σ。2）用小寫(xiě)英文字母x、y、z…表示輸入帶上帶符號(hào)串，即

x,y,z,…∈∑*。3）用大寫(xiě)英文字母A、B、C…表示棧內(nèi)符號(hào)，即

A,B,C,…∈Γ。4）用希臘字母α、β、γ…表示棧內(nèi)符號(hào)串，即α,β,γ,…∈Γ*。第五十三頁(yè)，共一百一十七頁(yè)，2022年，8月28日4.【例3-5.1】

設(shè)計(jì)一個(gè)PDAM，使之接收語(yǔ)言L＝{wcwR|w∈{0,1}*}，例如0101c1010∈L。解：設(shè)計(jì)的思想是：PDAM有兩個(gè)狀態(tài)，即K={q1,q2}，有三個(gè)棧內(nèi)符號(hào)，即Γ＝{R,B,G}。它的動(dòng)作設(shè)想：1).開(kāi)始時(shí)，PDAM的狀態(tài)為q1，棧內(nèi)符號(hào)為R。2).當(dāng)讀c左邊的符號(hào)時(shí)，M是在q1狀態(tài)，此時(shí)如果讀0，則向棧內(nèi)壓入符號(hào)B；如果讀1，則向棧內(nèi)壓入符號(hào)G。例如，帶上符號(hào)串是0101c1010，讀完c左邊的0101后，棧內(nèi)符號(hào)串為：GBGB。3).當(dāng)讀符號(hào)c時(shí)，狀態(tài)變成q2。4).在此狀態(tài)下之后讀c右邊的符號(hào)：如果讀0，此時(shí)棧頂應(yīng)該是B，則B退棧；如果讀1，此時(shí)棧頂應(yīng)該是G，則G退棧。0101c1010入棧

q1出棧

q2第五十四頁(yè)，共一百一十七頁(yè)，2022年，8月28日這樣，當(dāng)帶上符號(hào)都讀完時(shí)，棧內(nèi)應(yīng)該是符號(hào)R。再將R清除，使得棧內(nèi)為空，進(jìn)而接收輸入帶上的符號(hào)串。具體動(dòng)作如下表所示：棧頂當(dāng)前輸入符號(hào)符號(hào)狀態(tài)01c

Bq1B入棧，狀態(tài)為q1G入棧，狀態(tài)為q1狀態(tài)改成q2q2Gq1B入棧，狀態(tài)為q1G入棧，狀態(tài)為q1狀態(tài)改成q2

q2

Rq1B入棧，狀態(tài)為q1G入棧，狀態(tài)為q1狀態(tài)改成q2q2

退棧頂，狀態(tài)為q2

－－－退棧頂，狀態(tài)為q2

－如果帶上無(wú)符號(hào)可讀，則退棧頂R，否則，無(wú)動(dòng)作。表中符號(hào)“－”表示無(wú)動(dòng)作。當(dāng)帶上符號(hào)串都讀完后，棧內(nèi)為空，就說(shuō)明帶上符號(hào)串正是L中的句子。M的形式定義如下：第五十五頁(yè)，共一百一十七頁(yè)，2022年，8月28日M的形式定義：M＝({q1,q2},{0,1,c},{R,B,G},δ,q1,R,Φ)δ：δ(q1,0,R)={(q1,BR)}δ(q1,1,R)={(q1,GR)}δ(q1,0,B)={(q1,BB)}δ(q1,1,B)={(q1,GB)}δ(q1,0,G)={(q1,BG)}δ(q1,1,G)={(q1,GG)}δ(q1,c,R)={(q2,R)}δ(q1,c,B)={(q2,B)}δ(q1,c,G)={(q2,G)}δ(q2,0,B)={(q2,ε)}δ(q2,1,G)={(q2,ε)}δ(q2,ε,R)={(q2,ε)}δ(q2,0,R)=δ(q2,1,R)=δ(q2,c,R)=Φδ(q2,1,B)=δ(q2,c,B)=Φδ(q2,0,G)=δ(q2,c,G)=Φ這里δ(q2,ε,R)={(q2,ε)}的作用是：當(dāng)讀完帶上所有符號(hào)時(shí)，清除下推棧，使之為空，接收帶上符號(hào)串。第五十六頁(yè)，共一百一十七頁(yè)，2022年，8月28日5．PDA的瞬間描述ID(InstantaneousDescription)PDAM的當(dāng)前格局，稱之為M的瞬間描述ID。用有序三元組(q,x,γ)表示瞬間描述ID，其中

q----q∈K,M的當(dāng)前狀態(tài)，

x----x∈∑*,輸入帶上還沒(méi)有被讀到的符號(hào)串，

γ----γ∈Γ*,當(dāng)前棧內(nèi)符號(hào)串。例如上例中，當(dāng)帶上符號(hào)串為0011c1100時(shí)，開(kāi)始的ID0：（q1,0011c1100,R），當(dāng)讀完第一個(gè)0后，變成ID1：（q1,011c1100,BR）。├

：表示由一個(gè)ID，經(jīng)過(guò)一個(gè)動(dòng)作變成另一個(gè)ID時(shí)，ID之間的轉(zhuǎn)變關(guān)系。例如上例中有

ID0├ID1，即（q1,0011c1100,R）├

（q1,011c1100,BR）。├*：表示經(jīng)過(guò)多個(gè)動(dòng)作后,ID之間的轉(zhuǎn)變關(guān)系。第五十七頁(yè)，共一百一十七頁(yè)，2022年，8月28日如上例中（q1,0011c1100,R）├（q1,011c1100,BR）├（q1,11c1100,BBR）├（q1,1c1100,GBBR）├（q1,c1100,GGBBR）├（q2,1100,GGBBR）可以寫(xiě)成

(q1,0011c1100,R)├*(q1,1100,GGBBR)。6．PDAM所接收的語(yǔ)言PDAM接收語(yǔ)言有兩種方式：1).空棧接收的語(yǔ)言,記作N(M)：令

M=(K,Σ,Γ,δ,q0,Z0,Φ),N(M)={w|w∈∑*,(q0,w,Z0)├*

(q,ε,ε),q∈K}即當(dāng)M讀完帶上符號(hào)串w后，棧內(nèi)為空，則接收w。上例中M識(shí)別0011c1100時(shí)，ID的變化過(guò)程：(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。第五十八頁(yè)，共一百一十七頁(yè)，2022年，8月28日2)．用終止?fàn)顟B(tài)接收的語(yǔ)言，記作T(M)：令M=(K,Σ,Γ,δ,q0,Z0,F),T(M)={w|w∈∑*,(q0,w,Z0)├*(q,ε,γ),q∈F,γ∈Γ*}即當(dāng)M讀完帶上符號(hào)串w后，進(jìn)入終止?fàn)顟B(tài)q，而棧內(nèi)不一定為空，則接收輸入符號(hào)串w。后面我們將證明這兩種接收方式可以互相轉(zhuǎn)換。上面介紹的PDAM中，每個(gè)狀態(tài)轉(zhuǎn)移函數(shù)的函數(shù)值最多有一個(gè)序偶。這相當(dāng)于是個(gè)確定的PDA。下面的例子就不同了。7.【例3-5.2】

設(shè)計(jì)一個(gè)PDAM，使之接收語(yǔ)言L如下：

L={wwR|w∈{0,1}*}，例如01011010∈L。此例與前例不同，前例w與wR之間有一個(gè)標(biāo)志c，而此例的w與wR之間無(wú)標(biāo)志，識(shí)別起來(lái)就麻煩一些。第五十九頁(yè)，共一百一十七頁(yè)，2022年，8月28日解：設(shè)計(jì)的思想是：PDAM有兩個(gè)狀態(tài)K={q1,q2}，有三個(gè)棧內(nèi)符號(hào)，即Γ＝{R,B,G}。它的動(dòng)作設(shè)想：1．開(kāi)始時(shí)，PDAM的狀態(tài)為q1，棧頂符號(hào)為R。2．⑴當(dāng)讀左半邊的符號(hào)串w時(shí)，M是在q1狀態(tài)，這時(shí)如果讀0，則向棧內(nèi)壓入符號(hào)B；如果讀1，則向棧內(nèi)壓入符號(hào)G。

⑵當(dāng)讀完左半部分符號(hào)串w后，狀態(tài)變成q2,之后，要

讀右半邊的符號(hào)串wR，這時(shí)如果讀0，此時(shí)棧頂應(yīng)該是B，則B退棧；如果讀1，此時(shí)棧頂應(yīng)該是G，則G退棧；當(dāng)帶上符號(hào)都讀完時(shí)，棧內(nèi)應(yīng)該是符號(hào)R。

第六十頁(yè)，共一百一十七頁(yè)，2022年，8月28日⑶問(wèn)題是：如何判斷w與wR的分界線。我們注意到w的末尾符號(hào)與wR開(kāi)始符號(hào)相同。因此當(dāng)連續(xù)讀的兩個(gè)符號(hào)相同時(shí)，就有兩種可能：一種情況是這兩個(gè)符號(hào)都是w中的符號(hào)，此時(shí)狀態(tài)不變；另一種情況是前一個(gè)符號(hào)是w末尾的符號(hào)，而后一個(gè)符號(hào)是wR的第一個(gè)符號(hào)，此時(shí)就要改變狀態(tài)。構(gòu)造PDAM＝({q1,q2},{0,1},{R,B,G},δ,q1,R,Φ)M的動(dòng)作δ如下：⑴δ(q1,0,R)={(q1,BR)}⑵δ(q1,1,R)={(q1,GR)}⑶δ(q1,0,B)={(q1,BB),(q2,ε)}⑷δ(q1,1,B)={(q1,GB)}⑸δ(q1,0,G)={(q1,BG)}⑹δ(q1,1,G)={(q1,GG),(q2,ε)}⑺δ(q2,0,B)={(q2,ε)}⑻δ(q2,1,G)={(q2,ε)}⑼δ(q2,ε,R)={(q2,ε)}⑽δ(q1,ε,R)={(q2,ε)}δ(q2,0,R)=δ(q2,1,R)=δ(q2,1,B)=δ(q2,0,G)=Φ第六十一頁(yè)，共一百一十七頁(yè)，2022年，8月28日下面看看M識(shí)別110011的ID變換過(guò)程：注：符號(hào)“┣⑽”表示執(zhí)行動(dòng)作⑽得到后面的ID；符號(hào)“┳⑵”表示執(zhí)行動(dòng)作⑵得到下面的