有限自動(dòng)機(jī)理論章下推自動(dòng)機(jī)

有限自動(dòng)機(jī)理論章下推自動(dòng)機(jī)第1頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月FA只能處理正則語(yǔ)言正則文法生成無(wú)窮語(yǔ)言是由于A->wA不需要記錄w的個(gè)數(shù)第2頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月無(wú)關(guān)文法生成無(wú)窮語(yǔ)言

A->αAβ

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

的論文中。與上下文無(wú)關(guān)文法的等價(jià)性由Chomsky于1962年發(fā)現(xiàn)。第5頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月與FA比較PDA具有一個(gè)棧存儲(chǔ)器有兩個(gè)操作：入棧---將內(nèi)容壓入棧中

出棧---將棧頂元素移出第6頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月下推自動(dòng)機(jī)物理模型a1a2a3…aj…anan+1…FSC…存儲(chǔ)帶棧存儲(chǔ)器第7頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月棧存儲(chǔ)器

存放不同于字母的符號(hào)只能對(duì)棧頂元素進(jìn)行操作。第8頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月下推自動(dòng)機(jī)動(dòng)作根據(jù)

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

棧頂符號(hào)進(jìn)行狀態(tài)改變和入?；虺鰲２僮鲗⒆x頭向右移動(dòng)一個(gè)單元第9頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月5.1.1確定的下推自動(dòng)機(jī)

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

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

(或PDA僅有一個(gè)狀態(tài))第10頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月初始棧為空從左到右逐個(gè)掃描串w∈(a，b)*第11頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月入棧若棧為空,當(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入棧第12頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月出棧若棧頂為A,當(dāng)前符號(hào)是b，則A出棧若棧頂為B,當(dāng)前符號(hào)是a，則B出棧第13頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月若串w有相同個(gè)數(shù)的a和b當(dāng)且僅當(dāng)w掃描結(jié)束后，棧為空。第14頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月注意PDA在兩種情況下停機(jī)：串掃描結(jié)束沒(méi)有對(duì)應(yīng)的規(guī)則第15頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月串掃描結(jié)束棧如果為空就接收掃描過(guò)的串。第16頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月對(duì)于非正式的算法，用形式化的方式進(jìn)行描述：第17頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月特殊的符號(hào)Z0表示棧底初始化時(shí)先壓入棧第18頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月<x，D，V>規(guī)則(指令)若x是w的當(dāng)前符號(hào)

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

PDA處于read狀態(tài)時(shí)，處理整個(gè)串的前半部分，將對(duì)應(yīng)的符號(hào)壓入棧第30頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月掃描到字母c時(shí)PDA的狀態(tài)轉(zhuǎn)為match開始處理整個(gè)串的后半部分，將棧中的內(nèi)容出棧。第31頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月規(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第32頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月（在本例中）用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>第33頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月用下列的規(guī)則來(lái)描述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，ε>第34頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月若串w是該語(yǔ)言的合法的串當(dāng)且僅當(dāng)w掃描結(jié)束后，棧為空。第35頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月Z0符號(hào)棧串a(chǎn)bbcbba的處理過(guò)程ABreadmatch=>B第36頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月掃描到字母c棧內(nèi)的內(nèi)容（從棧頂?shù)綏５祝┦菕呙柽^(guò)的串的逆與未掃描過(guò)的串的順序相同此時(shí)，不作出棧和入棧操作，僅僅把PDA的狀態(tài)從read改變到match。第37頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月接收語(yǔ)言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，ε>第38頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月5.1.2不確定的下推自動(dòng)機(jī)例5-3語(yǔ)言L={wwT|w∈(a,b)*}第39頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月

沒(méi)有中心點(diǎn)字符在掃描過(guò)程中，就沒(méi)有確定的位置進(jìn)行狀態(tài)的變換具有不確定性。第40頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月使用規(guī)則〈read，ε，Z，match，Z>來(lái)代替〈read，c，Z，match，Z>即在read狀態(tài)時(shí)，可隨時(shí)改變?yōu)閙atch狀態(tài)（棧的內(nèi)容和掃描符號(hào)不變）第41頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月〈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，ε>第42頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月該P(yáng)DA是不確定的處于狀態(tài)read狀態(tài)時(shí)

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

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

∑是輸入串的字母集合

Г是棧內(nèi)符號(hào)集合第48頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月q0∈Q是開始狀態(tài)Z0∈Г是棧底符號(hào)FQ是接收狀態(tài)集合第49頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月δ：Q×(∑∪{ε})×Г→Q×Г*對(duì)于確定的PDA，有δ（q，x，D）=(q′，V)對(duì)于不確定的PDA，有(q′，V)∈δ（q，x，D）第50頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月一般使用

<q，x，D，q′，V>表示δ函數(shù)第51頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定義5-2PDA格局(或瞬間描述ID)格局代表某個(gè)時(shí)刻PDA的情況PDA的格局是一個(gè)三元式(q，w，σ)其中，q為狀態(tài)第52頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月w=x1x2…xn還沒(méi)有被掃描到的串(將掃描x1)σ=Z1Z2…Zm棧的內(nèi)容(Z1在棧頂，Zm在棧底)第53頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月PDA初始格局為(q0，w，Z0)接收格局為(q，ε，ε)其中:q∈Q（與接收狀態(tài)無(wú)關(guān)）第54頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月格局的轉(zhuǎn)換是由于狀態(tài)轉(zhuǎn)換函數(shù)的作用引起的第55頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月確定的PDA<q，x，A，q1，A1A2…Ak>引起的格局轉(zhuǎn)換為：

(q，xw，Aσ)=>(q1，w，A1A2…Akσ)第56頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月不確定的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σ)第57頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月不確定的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σ)第58頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月用=>*代表格局的任意次變換第59頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月不確定PDA對(duì)于某一格局可能會(huì)有不同的下一格局。第60頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月5.1.3PDA接收語(yǔ)言的兩種方式定義5-3PAD以空棧方式接收的語(yǔ)言為L(zhǎng)(M），且L(M)={w|(q0，w，Z0)=>*(q,ε,ε)

q∈Q}第61頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月接收格局與接收狀態(tài)無(wú)關(guān)只要當(dāng)串w掃描結(jié)束，而棧為空則串w被PDA以空棧方式所接收。第62頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定義5-4PAD以終態(tài)方式接收的語(yǔ)言為F(M)，且F(M)={w|(q0,w，Z0)=>*(q′,ε,σ)q′∈F,σ∈Г*}

第63頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月接收格局與棧是否為空無(wú)關(guān)只要當(dāng)串w掃描結(jié)束，而PDA處于某個(gè)接收狀態(tài)則串w被PDA以終態(tài)方式所接收。第64頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定理5-1語(yǔ)言L被PDA以終態(tài)方式所接收當(dāng)且僅當(dāng)

它被PDA以空棧方式所接收。即終態(tài)接收與空棧接收方式等價(jià)。第65頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明：略第66頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月5.1.4廣義PDA和單態(tài)PDA定義5-5廣義的PDA是七元式

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

廣義的PDA的一條規(guī)則一般PDA的多條規(guī)則的組合就是第72頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明：對(duì)于廣義的PDA的任意一條規(guī)則<q,x,B1B2…Bk，q′，C1C2…Cn>增加狀態(tài)r1，r2，…，rk-1，第73頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月<q，x，B1B2…Bk，q′，C1C2…Cn>改造為：

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

>第74頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月得到一般的PDA′且L=L(PDA′)。第75頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定義5-6單態(tài)PDA

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

規(guī)則簡(jiǎn)化為<x，D，V>第76頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月(等價(jià)性)問(wèn)題一個(gè)NFA是否可以轉(zhuǎn)換為一個(gè)單態(tài)PDA？第77頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月思路NFA=（Q，∑,δ，q0，F(xiàn)）將NFA的狀態(tài)當(dāng)作PDA的棧內(nèi)符號(hào)構(gòu)造單態(tài)的PDA

=（{*}，∑，Q，δ′，*，q0，{*})第78頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月NFA：δ(q，x)={q1，q2，…

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

<x，q，q1

><x，q，q2

>…<x，q，qn

>第79頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月NFA：若q∈δ*(q0，w)單態(tài)的PDA：有（*，w，q0）=>*（*，ε，q）第80頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月NFA：若δ(q，x)∩F≠ф

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

，q

，ε

>第81頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月因此NFA：

δ*(q0，w)∩F≠ф單態(tài)的PDA：（*，w，q0）=>*（*，ε，ε）即L(NFA)=L(PDA)第82頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月右線性文法G=（∑，V，S，P）也可以對(duì)應(yīng)一個(gè)單態(tài)的PDA，第83頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月產(chǎn)生式

A→bB

A→b

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

<b，A，ε>第84頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月將文法的開始符號(hào)S當(dāng)作是單態(tài)PDA的棧底符號(hào)，則第85頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月對(duì)于文法GS=>*w1A=>w1bB=>*w1bw2=w對(duì)于單態(tài)PDA(*，w1bw2，S)=>*(*，bw2，A)=>(*，w2，B)=>*(*，ε，ε)第86頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月例5-4語(yǔ)言L={anbn|n≥1}文法S→aSBS→aBB→b<a，S，SB><a，S，B><b，B，ε>單態(tài)PDA第87頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月對(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)出②和③的中間過(guò)程；第88頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月②會(huì)導(dǎo)致停機(jī)，因?yàn)闆](méi)有合適的規(guī)則<a，B，？>③可以完成最后的轉(zhuǎn)換：（*，bn，Bn）=>*（*，ε，ε）第89頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月使用n-1次規(guī)則<a，S，SB>

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

A→BCA，B，C∈V

A→a

A∈V，a∈∑

S→ε且S不出現(xiàn)在產(chǎn)生式的右邊則G是Chomsky范式(CNF)。第98頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定理5-6G是一個(gè)上下文無(wú)關(guān)文法，則存在一個(gè)等價(jià)的上下文無(wú)關(guān)文法G′使得L(G)=L(G′)，且G′是CNF。第99頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明對(duì)于任意的上下文無(wú)關(guān)文法G首先使它滿足定理5-5的要求對(duì)于文法中的任意的產(chǎn)生式A→B1B2…Bm

第100頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月假設(shè)每個(gè)Bi都是非終結(jié)符

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

第101頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月A→B1B2…Bm若m=2，滿足了CNF要求；m≥3，將它改造為m-1個(gè)產(chǎn)生式：第102頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月A→B1B2…Bm

A→B1C1 C1→B2C2…Cm-3→Bm-2Cm-2 Cm-2→Bm-1Bm第103頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月其中C1，C2，…，Cm-2是新加的非終結(jié)符得到的文法G′是CNF且L(G)=L(G′)。證畢。第104頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月5.2.2Greibach范式(GNF)定義5-8上下文無(wú)關(guān)文法G=(∑，V，S，P)是GNF，若G的每個(gè)產(chǎn)生式形式為A→bWb∈∑，W∈V*第105頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定理5-7G是一個(gè)上下文無(wú)關(guān)文法，則存在一個(gè)等價(jià)的上下文無(wú)關(guān)文法G′，使得L(G)=L(G′)且G′中沒(méi)有直接左遞歸的產(chǎn)生式，即不存在A→Av形式的產(chǎn)生式其中：A∈V，v∈(∑UV)+。第106頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月沒(méi)有直接左遞歸的文法也稱為無(wú)直接左遞歸范式（NLR）。第107頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明見2.7。第108頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月某些文法可能沒(méi)有直接左遞歸，但可能會(huì)有間接左遞歸。第109頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定理5-8G是一個(gè)上下文無(wú)關(guān)文法，則存在一個(gè)等價(jià)的上下文無(wú)關(guān)文法G′，使得L(G)=L(G′)且G′中沒(méi)有間接左遞歸的產(chǎn)生式。第110頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月沒(méi)有間接左遞歸的文法也稱為無(wú)間接左遞歸范式。第111頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明見2.7。第112頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定理5-9G是任意一個(gè)上下文無(wú)關(guān)文法，則存在一個(gè)等價(jià)的上下文無(wú)關(guān)文法G′，使得L(G)=L(G′)且G′是Greibach范式(GNF)。第113頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月對(duì)于任意的上下文無(wú)關(guān)文法G，產(chǎn)生式形式為Ai→AjwAi→aw或第114頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月假設(shè)w包含的字符全為非終結(jié)符對(duì)于Ai→aw，本身就是GNF的形式第115頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月對(duì)于Ai→Ajw

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

S→ε

A→bA→bW其中：A∈V，W∈V+，<ε，S，ε><b，A，ε><b，A，W>第120頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月需要證明語(yǔ)言L=L(PDA)。為證明之，先證明（*，w1w2，S）=>*（*，w2，σ）iffS=>*w1σ第121頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月即掃描串后w1，M棧內(nèi)符號(hào)串為σ；若上述成立，假設(shè)w2=σ=ε，則（*，w1，S）=>*（*，ε，ε）

iffS=>*w1第122頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月現(xiàn)在用歸納法證明（對(duì)串w1的長(zhǎng)度進(jìn)行歸納）（*,w1w2，S）=>*（*,w2，σ）iffS=>*w1σ第123頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明基礎(chǔ)：當(dāng)w1=ε，有兩種情況：a）（*，w2，S）=>*（*，w2，S）

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

iffS=>*ε是成立的；第124頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月假設(shè)：當(dāng)w1≠ε時(shí)，長(zhǎng)度為n時(shí)；（*,w1w2，S）=>*（*,w2，σ）iffS=>*w1σ令σ=Aг，w2=aw3，（將w1a當(dāng)作新的w1，長(zhǎng)度為n+1），則第125頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月(*,w1aw3，S）=>*（*,aw3，Aг）

iffS=>*w1Aг而（*，aw3，Aг）=>（*，w3，г′г）iffA→aг′第126頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月因此(*，w1aw3，S)=>*(*，w3，г′г)

iffS=>*w1aг′г所以：假設(shè)成立，證畢。第127頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月例5-10文法G為

S→(L|εL→(LL|)對(duì)于串：(()())第128頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月構(gòu)造的單態(tài)的PDA（棧底為S）為：<(，S，L><ε，S，ε><(，L，LL><)，L，ε>S→(LS→εL→(LLL→)第129頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月對(duì)于單態(tài)的PDA可以構(gòu)造對(duì)應(yīng)的上下文無(wú)關(guān)文法G使得L(M)=L(G)第130頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月例5-11有單態(tài)的PDA：<a，Z0，AZ0><b，Z0，BZ0><a，A，AA><b，B，BB><a，B，ε><b，A，ε><ε，Z0，ε>第131頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月構(gòu)造上下文無(wú)關(guān)文法G（用Z代替Z0作為開始符號(hào)）為：Z→aAZ|bBZ|εA→aAA|bB→bBB|a第132頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月例5-12構(gòu)造PDA接收語(yǔ)言L={w2wT|w∈{0,1}*}第133頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月解法1：read--match第134頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月解法2：GNF=>PDA產(chǎn)生L的上下文無(wú)關(guān)文法：S→2|0S0|1S1第135頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月將文法轉(zhuǎn)化成GNF

S→2|0SA|1SBA→0B→1第136頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月構(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第137頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定理5-11對(duì)于單態(tài)的PDA存在一個(gè)上下文無(wú)關(guān)文法G使得L（G）=L(PDA)且G為GNF范式形式。第138頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明PDA文法<a，B，σ>B→aσ<a，B，ε>B→a

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

A→aA1A2…AnA→A1A2…AnA→aA→ε第144頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月定理5-13若M是多態(tài)的PDA，則存在一個(gè)單態(tài)PDA′，使得L(PDA)=L(PDA′)第145頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月證明略。第146頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月總之對(duì)于一個(gè)PDA存在一個(gè)上下文無(wú)關(guān)文法G，使得L(M)=L(G)。第147頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月注意確定PDA和不確定PDA不等價(jià)。第148頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月例構(gòu)造PDA接收語(yǔ)言L={w|w∈{a,b}*

w中a的個(gè)數(shù)為b的2倍且a必須成對(duì)出現(xiàn)}第149頁(yè)，課件共166頁(yè)，創(chuàng)作于2023年2月思路：將一個(gè)a當(dāng)作一個(gè)成對(duì)的aa:構(gòu)造上下文無(wú)關(guān)文法G為：Z→aCAZ|bBZ|εA→aCAA|bB→