有限自動(dòng)機(jī)理論章下推自動(dòng)機(jī)第一頁，共一百六十六頁，2022年，8月28日FA只能處理正則語言正則文法生成無窮語言是由于A->wA不需要記錄w的個(gè)數(shù)第二頁，共一百六十六頁，2022年，8月28日無關(guān)文法生成無窮語言

A->αAβ

需要記錄α和β之間的對(duì)應(yīng)關(guān)系無法用FA的有窮個(gè)狀態(tài)來表示。第三頁，共一百六十六頁，2022年，8月28日為FA擴(kuò)充一個(gè)無限容量的棧用棧的內(nèi)容和FA的狀態(tài)結(jié)合起來就可以表示無限存儲(chǔ)。這種模型就是下推自動(dòng)機(jī)PDA第四頁，共一百六十六頁，2022年，8月28日PDA作為形式系統(tǒng)最早于1961年出現(xiàn)在Oettinger

的論文中。與上下文無關(guān)文法的等價(jià)性由Chomsky于1962年發(fā)現(xiàn)。第五頁，共一百六十六頁，2022年，8月28日與FA比較PDA具有一個(gè)棧存儲(chǔ)器有兩個(gè)操作：入棧---將內(nèi)容壓入棧中

出棧---將棧頂元素移出第六頁，共一百六十六頁，2022年，8月28日下推自動(dòng)機(jī)物理模型a1a2a3…aj…anan+1…FSC…存儲(chǔ)帶棧存儲(chǔ)器第七頁，共一百六十六頁，2022年，8月28日棧存儲(chǔ)器

存放不同于字母的符號(hào)只能對(duì)棧頂元素進(jìn)行操作。第八頁，共一百六十六頁，2022年，8月28日下推自動(dòng)機(jī)動(dòng)作根據(jù)

FSC當(dāng)前的狀態(tài)輸入帶上的當(dāng)前字符

棧頂符號(hào)進(jìn)行狀態(tài)改變和入棧或出棧操作將讀頭向右移動(dòng)一個(gè)單元第九頁，共一百六十六頁，2022年，8月28日5.1.1確定的下推自動(dòng)機(jī)

例5-1語言L={w|w∈(a,b)*，且a、b個(gè)數(shù)相等}

暫時(shí)不考慮狀態(tài)

(或PDA僅有一個(gè)狀態(tài))第十頁，共一百六十六頁，2022年，8月28日初始棧為空從左到右逐個(gè)掃描串w∈(a，b)*第十一頁，共一百六十六頁，2022年，8月28日入棧若棧為空,當(dāng)前符號(hào)是a,則A入棧若棧為空,當(dāng)前符號(hào)是b,則B入棧若棧頂為A,當(dāng)前符號(hào)是a,則A入棧若棧頂為B,當(dāng)前符號(hào)是b,則B入棧第十二頁，共一百六十六頁，2022年，8月28日出棧若棧頂為A,當(dāng)前符號(hào)是b，則A出棧若棧頂為B,當(dāng)前符號(hào)是a，則B出棧第十三頁，共一百六十六頁，2022年，8月28日若串w有相同個(gè)數(shù)的a和b當(dāng)且僅當(dāng)w掃描結(jié)束后，棧為空。第十四頁，共一百六十六頁，2022年，8月28日注意PDA在兩種情況下停機(jī)：串掃描結(jié)束沒有對(duì)應(yīng)的規(guī)則第十五頁，共一百六十六頁，2022年，8月28日串掃描結(jié)束棧如果為空就接收掃描過的串。第十六頁，共一百六十六頁，2022年，8月28日對(duì)于非正式的算法，用形式化的方式進(jìn)行描述：第十七頁，共一百六十六頁，2022年，8月28日特殊的符號(hào)Z0表示棧底初始化時(shí)先壓入棧第十八頁，共一百六十六頁，2022年，8月28日<x，D，V>規(guī)則(指令)若x是w的當(dāng)前符號(hào)

D是棧頂符號(hào)則用符號(hào)串V代替D即將D彈出棧，而將串V壓入棧第十九頁，共一百六十六頁，2022年，8月28日具體若x是w的當(dāng)前符號(hào)，棧頂符號(hào)為D<x，D，ε>將D彈出棧<x，D，AD>將A壓入棧，成為新的棧頂?shù)诙摚惨话倭摚?022年，8月28日一般地若x是w的當(dāng)前符號(hào)，棧頂符號(hào)為D<x，D，A1A2…Ak>表示：將D彈出棧將串A1A2…Ak壓入棧(A1為新棧頂)第二十一頁，共一百六十六頁，2022年，8月28日例5-1算法的形式化描述<a，Z0，AZ0><b，Z0，BZ0><a，A，AA><b，B，BB><a，B，ε><b，A，ε><ε，Z0，ε>第二十二頁，共一百六十六頁，2022年，8月28日規(guī)則<ε，Z0，ε>表示將w掃描結(jié)束后，將棧置成空也表示該P(yáng)DA可以接收空串ε第二十三頁，共一百六十六頁，2022年，8月28日思考：如何接收語言L={w|w∈(a,b)+,且a和b個(gè)數(shù)相等}?第二十四頁，共一百六十六頁，2022年，8月28日例：語言L={anbn|n≥0}定義：<a，Z0，AZ0><a，A，AA><b，A，ε><ε，Z0，ε>第二十五頁，共一百六十六頁，2022年，8月28日則還可以接收語言{(ab)n|n≥0}，或{ambm(ab)n|m≥0,n≥0}等語言。第二十六頁，共一百六十六頁，2022年，8月28日思考：如何接收語言L={anbn|n>0}L={anbn|n≥0}L={(ab)n|n>0}L={(ab)n|n≥0}第二十七頁，共一百六十六頁，2022年，8月28日例5-2L={wcwT|w∈(a，b)*}識(shí)別語言第二十八頁，共一百六十六頁，2022年，8月28日思想：將w的各個(gè)字符壓入棧后棧中的內(nèi)容從棧頂?shù)綏５椎捻樞騽偤檬莣T的順序第二十九頁，共一百六十六頁，2022年，8月28日為了區(qū)別壓棧和出棧動(dòng)作增加兩個(gè)狀態(tài)----read和match

PDA處于read狀態(tài)時(shí)，處理整個(gè)串的前半部分，將對(duì)應(yīng)的符號(hào)壓入棧第三十頁，共一百六十六頁，2022年，8月28日掃描到字母c時(shí)PDA的狀態(tài)轉(zhuǎn)為match開始處理整個(gè)串的后半部分，將棧中的內(nèi)容出棧。第三十一頁，共一百六十六頁，2022年，8月28日規(guī)則<q，x，D，q′，V>

若PDA處于狀態(tài)qw的當(dāng)前字母是x當(dāng)前棧頂符號(hào)為D則自動(dòng)機(jī)的狀態(tài)改變?yōu)閝′并用符號(hào)串V代替D第三十二頁，共一百六十六頁，2022年，8月28日（在本例中）用Z代表任意的棧頂符號(hào)規(guī)則〈read，a，Z，read，AZ>可以表示以下3條規(guī)則：〈read，a，Z0，read，AZ0>〈read，a，A，read，AA>〈read，a，B，read，AB>第三十三頁，共一百六十六頁，2022年，8月28日用下列的規(guī)則來描述PDA〈read，a，Z，read，AZ>〈read，b，Z，read，BZ>〈read，c，Z，match，Z>〈match，a，A，match，ε>〈match，b，B，match，ε>〈match，ε，Z0，match，ε>第三十四頁，共一百六十六頁，2022年，8月28日若串w是該語言的合法的串當(dāng)且僅當(dāng)w掃描結(jié)束后，棧為空。第三十五頁，共一百六十六頁，2022年，8月28日Z0符號(hào)棧串a(chǎn)bbcbba的處理過程ABreadmatch=>B第三十六頁，共一百六十六頁，2022年，8月28日掃描到字母c棧內(nèi)的內(nèi)容（從棧頂?shù)綏５祝┦菕呙柽^的串的逆與未掃描過的串的順序相同此時(shí)，不作出棧和入棧操作，僅僅把PDA的狀態(tài)從read改變到match。第三十七頁，共一百六十六頁，2022年，8月28日接收語言L={anbn|n>0}〈q0，a，Z0，q0，AZ0>〈q0，a，A，q0，AA>〈q0，b，A，q1，ε>〈q1，b，A，q1，ε>〈q1，ε，Z0，q1，ε>第三十八頁，共一百六十六頁，2022年，8月28日5.1.2不確定的下推自動(dòng)機(jī)例5-3語言L={wwT|w∈(a,b)*}第三十九頁，共一百六十六頁，2022年，8月28日

沒有中心點(diǎn)字符在掃描過程中，就沒有確定的位置進(jìn)行狀態(tài)的變換具有不確定性。第四十頁，共一百六十六頁，2022年，8月28日使用規(guī)則〈read，ε，Z，match，Z>來代替〈read，c，Z，match，Z>即在read狀態(tài)時(shí)，可隨時(shí)改變?yōu)閙atch狀態(tài)（棧的內(nèi)容和掃描符號(hào)不變）第四十一頁，共一百六十六頁，2022年，8月28日〈read，a，Z，read，AZ>〈read，b，Z，read，BZ>〈read，ε，Z，match，Z>〈match，a，A，match，ε>〈match，b，B，match，ε>〈match，ε，Z0，match，ε>第四十二頁，共一百六十六頁，2022年，8月28日該P(yáng)DA是不確定的處于狀態(tài)read狀態(tài)時(shí)

隨時(shí)都可以進(jìn)行選擇:繼續(xù)掃描，或狀態(tài)變換為match第四十三頁，共一百六十六頁，2022年，8月28日一個(gè)串w能夠由PDA所識(shí)別：僅當(dāng)串是wwT的形式且PDA狀態(tài)在中心點(diǎn)進(jìn)行了變換第四十四頁，共一百六十六頁，2022年，8月28日對(duì)于不確定的PDA和串w若存在至少一個(gè)可能的掃描過程使得當(dāng)串w掃描結(jié)束時(shí)，棧為空則稱串w能夠被PDA所識(shí)別。第四十五頁，共一百六十六頁，2022年，8月28日接收語言L={(ab)n|n≥0}〈q1，a，Z0，q2，AZ0>〈q2，b，A，q1，ε>〈q1，ε，Z0，q1，ε〉第四十六頁，共一百六十六頁，2022年，8月28日接收語言L={(ab)n|n>0}〈q0，a，Z0，q0，AZ0>〈q0，b，A，q1，ε>〈q1，a，Z0，q2，AZ0>〈q2，b，A，q1，ε>〈q1，ε，Z0，q1，ε>第四十七頁，共一百六十六頁，2022年，8月28日定義5-1下推自動(dòng)機(jī)PDA是一個(gè)七元式：M=(Q，∑，Г，δ，q0，Z0，F(xiàn))

Q是一個(gè)有限狀態(tài)的集合

∑是輸入串的字母集合

Г是棧內(nèi)符號(hào)集合第四十八頁，共一百六十六頁，2022年，8月28日q0∈Q是開始狀態(tài)Z0∈Г是棧底符號(hào)FQ是接收狀態(tài)集合第四十九頁，共一百六十六頁，2022年，8月28日δ：Q×(∑∪{ε})×Г→Q×Г*對(duì)于確定的PDA，有δ（q，x，D）=(q′，V)對(duì)于不確定的PDA，有(q′，V)∈δ（q，x，D）第五十頁，共一百六十六頁，2022年，8月28日一般使用<q，x，D，q′，V>表示δ函數(shù)第五十一頁，共一百六十六頁，2022年，8月28日定義5-2PDA格局(或瞬間描述ID)格局代表某個(gè)時(shí)刻PDA的情況PDA的格局是一個(gè)三元式(q，w，σ)其中，q為狀態(tài)第五十二頁，共一百六十六頁，2022年，8月28日w=x1x2…xn還沒有被掃描到的串(將掃描x1)σ=Z1Z2…Zm棧的內(nèi)容(Z1在棧頂，Zm在棧底)第五十三頁，共一百六十六頁，2022年，8月28日PDA初始格局為(q0，w，Z0)接收格局為(q，ε，ε)其中:q∈Q（與接收狀態(tài)無關(guān)）第五十四頁，共一百六十六頁，2022年，8月28日格局的轉(zhuǎn)換是由于狀態(tài)轉(zhuǎn)換函數(shù)的作用引起的第五十五頁，共一百六十六頁，2022年，8月28日確定的PDA<q，x，A，q1，A1A2…Ak>引起的格局轉(zhuǎn)換為：

(q，xw，Aσ)=>(q1，w，A1A2…Akσ)第五十六頁，共一百六十六頁，2022年，8月28日不確定的PDA（情況1）①<q，x，A，q1，A1A2…Ak>則(q,xw,Aσ)=>(q1，w,A1A2…Akσ)②<q，ε，A，q2，B1B2…Bj>則(q,xw,Aσ)=>(q2，xw，B1B2…Bjσ)第五十七頁，共一百六十六頁，2022年，8月28日不確定的PDA（情況2）①<q，x，A，q1，A1A2…Ak>則(q,xw,Aσ)=>(q1，w，A1A2…Akσ)②<q，x，A，q2，B1B2…Bj>則(q,xw,Aσ)=>(q2，w，B1B2…Bjσ)第五十八頁，共一百六十六頁，2022年，8月28日用=>*代表格局的任意次變換第五十九頁，共一百六十六頁，2022年，8月28日不確定PDA對(duì)于某一格局可能會(huì)有不同的下一格局。第六十頁，共一百六十六頁，2022年，8月28日5.1.3PDA接收語言的兩種方式定義5-3PAD以空棧方式接收的語言為L(M），且L(M)={w|(q0，w，Z0)=>*(q,ε,ε)

q∈Q}第六十一頁，共一百六十六頁，2022年，8月28日接收格局與接收狀態(tài)無關(guān)只要當(dāng)串w掃描結(jié)束，而棧為空則串w被PDA以空棧方式所接收。第六十二頁，共一百六十六頁，2022年，8月28日定義5-4PAD以終態(tài)方式接收的語言為F(M)，且F(M)={w|(q0,w，Z0)=>*(q′,ε,σ)q′∈F,σ∈Г*}

第六十三頁，共一百六十六頁，2022年，8月28日接收格局與棧是否為空無關(guān)只要當(dāng)串w掃描結(jié)束，而PDA處于某個(gè)接收狀態(tài)則串w被PDA以終態(tài)方式所接收。第六十四頁，共一百六十六頁，2022年，8月28日定理5-1語言L被PDA以終態(tài)方式所接收當(dāng)且僅當(dāng)

它被PDA以空棧方式所接收。即終態(tài)接收與空棧接收方式等價(jià)。第六十五頁，共一百六十六頁，2022年，8月28日證明：略第六十六頁，共一百六十六頁，2022年，8月28日廣義PDA和單態(tài)PDA定義5-5廣義的PDA是七元式

PDA=(Q,∑，Г，δ，q0，Z0，F(xiàn))（除了δ外，其余同一般的PDA）其中第六十七頁，共一百六十六頁，2022年，8月28日Q是一個(gè)有限狀態(tài)的集合∑是輸入串的字母集合Г是棧內(nèi)符號(hào)集合q0∈Q是開始狀態(tài)Z0∈Г是初始的棧底符號(hào)FQ是接收狀態(tài)(終止?fàn)顟B(tài))集合第六十八頁，共一百六十六頁，2022年，8月28日δ：Q×(∑∪{ε})×Г+→Q×Г*(q，x，B1B2…Bk)=(q′，C1C2…Cn)一般形式為<q，x,B1B2…Bk，q′，C1C2…Cn>第六十九頁，共一百六十六頁，2022年，8月28日一般的PDA，棧頂只是一個(gè)符號(hào)廣義PDA的棧頂可以為多個(gè)符號(hào)。第七十頁，共一百六十六頁，2022年，8月28日定理5-4若語言L能由廣義PDA所接收則L能夠由一般的PDA所接收。第七十一頁，共一百六十六頁，2022年，8月28日證明思路

廣義的PDA的一條規(guī)則一般PDA的多條規(guī)則的組合就是第七十二頁，共一百六十六頁，2022年，8月28日證明：對(duì)于廣義的PDA的任意一條規(guī)則<q,x,B1B2…Bk，q′，C1C2…Cn>增加狀態(tài)r1，r2，…，rk-1，第七十三頁，共一百六十六頁，2022年，8月28日<q，x，B1B2…Bk，q′，C1C2…Cn>改造為：

<q，x，B1，r1，ε><r1，ε，B2，r2，ε>…<rk-1，ε，Bk，q′，C1C2…Cn

>第七十四頁，共一百六十六頁，2022年，8月28日得到一般的PDA′且L=L(PDA′)。第七十五頁，共一百六十六頁，2022年，8月28日定義5-6單態(tài)PDA

僅有一個(gè)狀態(tài)的PDA

規(guī)則簡化為<x，D，V>第七十六頁，共一百六十六頁，2022年，8月28日(等價(jià)性)問題一個(gè)NFA是否可以轉(zhuǎn)換為一個(gè)單態(tài)PDA？第七十七頁，共一百六十六頁，2022年，8月28日思路NFA=（Q，∑,δ，q0，F(xiàn)）將NFA的狀態(tài)當(dāng)作PDA的棧內(nèi)符號(hào)構(gòu)造單態(tài)的PDA

=（{*}，∑，Q，δ′，*，q0，{*})第七十八頁，共一百六十六頁，2022年，8月28日NFA：δ(q，x)={q1，q2，…

qn｝單態(tài)的PDA：

<x，q，q1

><x，q，q2

>…<x，q，qn

>第七十九頁，共一百六十六頁，2022年，8月28日NFA：若q∈δ*(q0，w)單態(tài)的PDA：有（*，w，q0）=>*（*，ε，q）第八十頁，共一百六十六頁，2022年，8月28日NFA：若δ(q，x)∩F≠ф

單態(tài)的PDA：<x

，q

，ε

>第八十一頁，共一百六十六頁，2022年，8月28日因此NFA：

δ*(q0，w)∩F≠ф單態(tài)的PDA：（*，w，q0）=>*（*，ε，ε）即L(NFA)=L(PDA)第八十二頁，共一百六十六頁，2022年，8月28日右線性文法G=（∑，V，S，P）也可以對(duì)應(yīng)一個(gè)單態(tài)的PDA，第八十三頁，共一百六十六頁，2022年，8月28日產(chǎn)生式

A→bB

A→b

PDA的規(guī)則<b，A，B>

<b，A，ε>第八十四頁，共一百六十六頁，2022年，8月28日將文法的開始符號(hào)S當(dāng)作是單態(tài)PDA的棧底符號(hào)，則第八十五頁，共一百六十六頁，2022年，8月28日對(duì)于文法GS=>*w1A=>w1bB=>*w1bw2=w對(duì)于單態(tài)PDA(*，w1bw2，S)=>*(*，bw2，A)=>(*，w2，B)=>*(*，ε，ε)第八十六頁，共一百六十六頁，2022年，8月28日例5-4語言L={anbn|n≥1}文法S→aSBS→aBB→b<a，S，SB><a，S，B><b，B，ε>單態(tài)PDA第八十七頁，共一百六十六頁，2022年，8月28日對(duì)于串a(chǎn)nbn，單態(tài)的PDA可能會(huì)有以下的格局轉(zhuǎn)換：①(*，anbn，S）=>n(*，an-jbn，SBj）②(*，anbn，S）=>n（*，an-kbn，Bk）③(*，anbn，S）=>n（*，bn，Bn）其中：①是導(dǎo)出②和③的中間過程；第八十八頁，共一百六十六頁，2022年，8月28日②會(huì)導(dǎo)致停機(jī)，因?yàn)闆]有合適的規(guī)則<a，B，？>③可以完成最后的轉(zhuǎn)換：（*，bn，Bn）=>*（*，ε，ε）第八十九頁，共一百六十六頁，2022年，8月28日使用n-1次規(guī)則<a，S，SB>

1次規(guī)則<a，S，B>n次規(guī)則<b，B，ε>第九十頁，共一百六十六頁，2022年，8月28日5.1.5下推自動(dòng)機(jī)的存儲(chǔ)技術(shù)參考Turing的存儲(chǔ)技術(shù)。略第九十一頁，共一百六十六頁，2022年，8月28日5.1.6PDA掃描多個(gè)符號(hào)參考Turing的掃描多個(gè)符號(hào)技術(shù)。略第九十二頁，共一百六十六頁，2022年，8月28日5.2上下文無關(guān)文法和范式范式是指標(biāo)準(zhǔn)的形式在代數(shù)中，2/4，3/6，…的范式是1/2。本節(jié)討論在上下文無關(guān)文法的幾個(gè)重要的范式。第九十三頁，共一百六十六頁，2022年，8月28日定理5-5G是一個(gè)上下文無關(guān)文法，則存在一個(gè)上下文無關(guān)文法G′，使得：①L(G)=L(G′)②若ε≠L(G)，則G′沒有空串產(chǎn)生式第九十四頁，共一百六十六頁，2022年，8月28日③若ε∈L(G)，則G′有S′→ε，且S′不出現(xiàn)在G′的任何產(chǎn)生式的右邊④G′中沒有A→B形式的產(chǎn)生式。第九十五頁，共一百六十六頁，2022年，8月28日證明前3點(diǎn)是空串定理的內(nèi)容(見2.6)第4點(diǎn)證明參見參考文獻(xiàn)1。第九十六頁，共一百六十六頁，2022年，8月28日5.2.1Chomsky范式(CNF)定義5-7上下文無關(guān)文法G=(∑，V，S，P)若G的每個(gè)產(chǎn)生式是下列形式之一：第九十七頁，共一百六十六頁，2022年，8月28日

A→BCA，B，C∈V

A→a

A∈V，a∈∑

S→ε且S不出現(xiàn)在產(chǎn)生式的右邊則G是Chomsky范式(CNF)。第九十八頁，共一百六十六頁，2022年，8月28日定理5-6G是一個(gè)上下文無關(guān)文法，則存在一個(gè)等價(jià)的上下文無關(guān)文法G′使得L(G)=L(G′)，且G′是CNF。第九十九頁，共一百六十六頁，2022年，8月28日證明對(duì)于任意的上下文無關(guān)文法G首先使它滿足定理5-5的要求對(duì)于文法中的任意的產(chǎn)生式A→B1B2…Bm

第一百頁，共一百六十六頁，2022年，8月28日假設(shè)每個(gè)Bi都是非終結(jié)符

(若不是，則使用非終結(jié)符Bi′來代替Bi，并增加產(chǎn)生式Bi′→Bi)

第一百零一頁，共一百六十六頁，2022年，8月28日A→B1B2…Bm若m=2，滿足了CNF要求；m≥3，將它改造為m-1個(gè)產(chǎn)生式：第一百零二頁，共一百六十六頁，2022年，8月28日A→B1B2…Bm

A→B1C1 C1→B2C2…Cm-3→Bm-2Cm-2 Cm-2→Bm-1Bm第一百零三頁，共一百六十六頁，2022年，8月28日其中C1，C2，…，Cm-2是新加的非終結(jié)符得到的文法G′是CNF且L(G)=L(G′)。證畢。第一百零四頁，共一百六十六頁，2022年，8月28日5.2.2Greibach范式(GNF)定義5-8上下文無關(guān)文法G=(∑，V，S，P)是GNF，若G的每個(gè)產(chǎn)生式形式為A→bWb∈∑，W∈V*第一百零五頁，共一百六十六頁，2022年，8月28日定理5-7G是一個(gè)上下文無關(guān)文法，則存在一個(gè)等價(jià)的上下文無關(guān)文法G′，使得L(G)=L(G′)且G′中沒有直接左遞歸的產(chǎn)生式，即不存在A→Av形式的產(chǎn)生式其中：A∈V，v∈(∑UV)+。第一百零六頁，共一百六十六頁，2022年，8月28日沒有直接左遞歸的文法也稱為無直接左遞歸范式（NLR）。第一百零七頁，共一百六十六頁，2022年，8月28日證明見2.7。第一百零八頁，共一百六十六頁，2022年，8月28日某些文法可能沒有直接左遞歸，但可能會(huì)有間接左遞歸。第一百零九頁，共一百六十六頁，2022年，8月28日定理5-8G是一個(gè)上下文無關(guān)文法，則存在一個(gè)等價(jià)的上下文無關(guān)文法G′，使得L(G)=L(G′)且G′中沒有間接左遞歸的產(chǎn)生式。第一百一十頁，共一百六十六頁，2022年，8月28日沒有間接左遞歸的文法也稱為無間接左遞歸范式。第一百一十一頁，共一百六十六頁，2022年，8月28日證明見2.7。第一百一十二頁，共一百六十六頁，2022年，8月28日定理5-9G是任意一個(gè)上下文無關(guān)文法，則存在一個(gè)等價(jià)的上下文無關(guān)文法G′，使得L(G)=L(G′)且G′是Greibach范式(GNF)。第一百一十三頁，共一百六十六頁，2022年，8月28日對(duì)于任意的上下文無關(guān)文法G，產(chǎn)生式形式為Ai→AjwAi→aw或第一百一十四頁，共一百六十六頁，2022年，8月28日假設(shè)w包含的字符全為非終結(jié)符對(duì)于Ai→aw，本身就是GNF的形式第一百一十五頁，共一百六十六頁，2022年，8月28日對(duì)于Ai→Ajw

利用消除左遞歸的算法，在消除左遞歸的以后，從An-1開始，將An代入到An-1，將An-1代入到An-2，直至A1，再將增加的非終結(jié)符的產(chǎn)生式的開頭符號(hào)代替掉，得到GNF。第一百一十六頁，共一百六十六頁，2022年，8月28日5.3PDA與上下文無關(guān)語言PDA識(shí)別的語言是上下文無關(guān)語言。第一百一十七頁，共一百六十六頁，2022年，8月28日定理5-10對(duì)于上下文無關(guān)語言L和文法G若L=L(G)，則語言L能被(廣義)不確定的PDA所接收第一百一十八頁，共一百六十六頁，2022年，8月28日證明：假設(shè)文法是GNF范式構(gòu)造一個(gè)單態(tài)的PDA來接收語言L；第一百一十九頁，共一百六十六頁，2022年，8月28日文法G中有3種形式的產(chǎn)生式，它們分別對(duì)應(yīng)PDA的規(guī)則：

S→ε

A→bA→bW其中：A∈V，W∈V+，<ε，S，ε><b，A，ε><b，A，W>第一百二十頁，共一百六十六頁，2022年，8月28日需要證明語言L=L(PDA)。為證明之，先證明（*，w1w2，S）=>*（*，w2，σ）iffS=>*w1σ第一百二十一頁，共一百六十六頁，2022年，8月28日即掃描串后w1，M棧內(nèi)符號(hào)串為σ；若上述成立，假設(shè)w2=σ=ε，則（*，w1，S）=>*（*，ε，ε）

iffS=>*w1第一百二十二頁，共一百六十六頁，2022年，8月28日現(xiàn)在用歸納法證明（對(duì)串w1的長度進(jìn)行歸納）（*,w1w2，S）=>*（*,w2，σ）iffS=>*w1σ第一百二十三頁，共一百六十六頁，2022年，8月28日證明基礎(chǔ)：當(dāng)w1=ε，有兩種情況：a）（*，w2，S）=>*（*，w2，S）

iffS=>*S是成立的；b）若S→ε在G中，則有（*,w2，S）=>*（*，w2，ε）

iffS=>*ε是成立的；第一百二十四頁，共一百六十六頁，2022年，8月28日假設(shè)：當(dāng)w1≠ε時(shí)，長度為n時(shí)；（*,w1w2，S）=>*（*,w2，σ）iffS=>*w1σ令σ=Aг，w2=aw3，（將w1a當(dāng)作新的w1，長度為n+1），則第一百二十五頁，共一百六十六頁，2022年，8月28日(*,w1aw3，S）=>*（*,aw3，Aг）

iffS=>*w1Aг而（*，aw3，Aг）=>（*，w3，г′г）iffA→aг′第一百二十六頁，共一百六十六頁，2022年，8月28日因此(*，w1aw3，S)=>*(*，w3，г′г)

iffS=>*w1aг′г所以：假設(shè)成立，證畢。第一百二十七頁，共一百六十六頁，2022年，8月28日例5-10文法G為

S→(L|εL→(LL|)對(duì)于串：(()())第一百二十八頁，共一百六十六頁，2022年，8月28日構(gòu)造的單態(tài)的PDA（棧底為S）為：<(，S，L><ε，S，ε><(，L，LL><)，L，ε>S→(LS→εL→(LLL→)第一百二十九頁，共一百六十六頁，2022年，8月28日對(duì)于單態(tài)的PDA可以構(gòu)造對(duì)應(yīng)的上下文無關(guān)文法G使得L(M)=L(G)第一百三十頁，共一百六十六頁，2022年，8月28日例5-11有單態(tài)的PDA：<a，Z0，AZ0><b，Z0，BZ0><a，A，AA><b，B，BB><a，B，ε><b，A，ε><ε，Z0，ε>第一百三十一頁，共一百六十六頁，2022年，8月28日構(gòu)造上下文無關(guān)文法G（用Z代替Z0作為開始符號(hào)）為：Z→aAZ|bBZ|εA→aAA|bB→bBB|a第一百三十二頁，共一百六十六頁，2022年，8月28日例5-12構(gòu)造PDA接收語言L={w2wT|w∈{0,1}*}第一百三十三頁，共一百六十六頁，2022年，8月28日解法1：read--match第一百三十四頁，共一百六十六頁，2022年，8月28日解法2：GNF=>PDA產(chǎn)生L的上下文無關(guān)文法：S→2|0S0|1S1第一百三十五頁，共一百六十六頁，2022年，8月28日將文法轉(zhuǎn)化成GNF

S→2|0SA|1SBA→0B→1第一百三十六頁，共一百六十六頁，2022年，8月28日構(gòu)造單態(tài)PDA<0，S，SA>//S→0SA<1，S，SB>//S→1SB<2，S，ε>//S→2<0，A，ε>//A→0<1，B，ε>//B→1第一百三十七頁，共一百六十六頁，2022年，8月28日定理5-11對(duì)于單態(tài)的PDA存在一個(gè)上下文無關(guān)文法G使得L（G）=L(PDA)且G為GNF范式形式。第一百三十八頁，共一百六十六頁，2022年，8月28日證明PDA文法<a，B，σ>B→aσ<a，B，ε>B→a

第一百三十九頁，共一百六十六頁，2022年，8月28日根據(jù)單態(tài)的PDA可以得到對(duì)應(yīng)的GNF。而多態(tài)的PDA，不可以直接得到GNF。第一百四十頁，共一百六十六頁，2022年，8月28日問題多態(tài)PDA如何得到對(duì)應(yīng)的上下文無關(guān)文法？第一百四十一頁，共一百六十六頁，2022年，8月28日定理5-12對(duì)于多態(tài)PDA，存在上下文無關(guān)文法G，使得L(G)=L(M)。第一百四十二頁，共一百六十六頁，2022年，8月28日證明構(gòu)造上下文無關(guān)文法G思路為用文法的一個(gè)推導(dǎo)模擬PDA的一個(gè)動(dòng)作。具體過程參考P135。第一百四十三頁，共一百六十六頁，2022年，8月28日對(duì)于多態(tài)PDA得到對(duì)應(yīng)的上下文無關(guān)文法的產(chǎn)生式具有如下的形式：

A→aA1A2…AnA→A1A2…AnA→aA→ε第一百四十四頁，共一百六十六頁，2022年，8月28日定理5-13若M是多態(tài)的PDA，則存在一個(gè)單態(tài)PDA′，使得L(PDA)=L(PDA′)第一百四十五頁，共一百六十六頁，2022年，8月28日證明略。第一百四十六頁，共一百六十六頁，2022年，8月28日總之對(duì)于一個(gè)PDA存在一個(gè)上下文無關(guān)文法G，使得L(M)=L(G)。第一百四十七頁，共一百六十六頁，2022年，8月28日注意確定PDA和不確定PDA不等價(jià)。第一百四十八頁，共一百六十六頁，2022年，8月28日例構(gòu)造PDA接收語言L={w|w∈{a,b}*

w中a的個(gè)數(shù)為b的2倍且a必須成對(duì)出現(xiàn)}第一百四十九頁，共一百六十六頁，2022年，8月28日思路：將一個(gè)a當(dāng)作一個(gè)成對(duì)的aa:構(gòu)造上下文無關(guān)文法G為：Z→aCAZ|bBZ|εA→aCAA|bB→bBB|aCC→a第一百