從PDA構(gòu)造CFG的算法

從PDA構(gòu)造CFG的算法《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》1《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》2引理3.15引理3.15:如果一個(gè)語言被PDA

識(shí)別,則這個(gè)語言是CFL.證明思路《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》3引理3.15引理3.15:如果一個(gè)語言被PDA

識(shí)別,則這個(gè)語言是CFL.證明思路用CFG派生出PDA接受的串《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》4引理3.15引理3.15:如果一個(gè)語言被PDA

識(shí)別,則這個(gè)語言是CFL.證明思路用CFG派生出PDA接受的串變?cè)酒馉顟B(tài)的作用

(如DFA到CFG)《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》5引理3.15引理3.15:如果一個(gè)語言被PDA

識(shí)別,則這個(gè)語言是CFL.證明思路用CFG派生出PDA接受的串變?cè)酒馉顟B(tài)的作用如何消除棧的影響?《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》6引理3.15引理3.15:如果一個(gè)語言被PDA

識(shí)別,則這個(gè)語言是CFL.證明思路用CFG派生出PDA接受的串變?cè)酒馉顟B(tài)的作用如何消除棧的影響?

分析PDA工作過程《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》7PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》8PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》9PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》10PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》11PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》12PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》13PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》14PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》15PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》16PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》17PDA的工作過程輸入串棧高度prq《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》18PDA的工作過程輸入串棧高度prqApr《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》19PDA的工作過程輸入串棧高度prApr《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》20PDA的工作過程輸入串棧高度prqAprArq《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》21PDA的工作過程輸入串棧高度prqAprArq《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》22PDA的工作過程輸入串棧高度pqApq《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》23PDA的工作過程輸入串棧高度prqAprArqApq=AprArq《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》24PDA的工作過程輸入串棧高度prqAprArqApq=AprArqApq

AprArq《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》25PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》26PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》27PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》28PDA的工作過程輸入串棧高度《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》29PDA的工作過程輸入串棧高度pqrsArs《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》30PDA的工作過程輸入串棧高度pqrsArsab《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》31PDA的工作過程輸入串棧高度pqrsArsab《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》32PDA的工作過程輸入串棧高度pqrsArsabApq=aArsbApq

aArsbtt《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》33特殊形式的PDA只有唯一接受狀態(tài)qaccept在接受之前排空棧每一個(gè)轉(zhuǎn)移把一個(gè)符號(hào)推入棧,

或把一個(gè)符號(hào)彈出棧,

但不同時(shí)做這兩個(gè)動(dòng)作把同時(shí)推入和彈出的轉(zhuǎn)移分成

兩個(gè)轉(zhuǎn)移,經(jīng)過一個(gè)中間狀態(tài)把既不推入也不彈出的轉(zhuǎn)移分成

兩個(gè)轉(zhuǎn)移,先推入一個(gè)任意符號(hào),

再推出這個(gè)符號(hào)《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》34引理3.15引理3.15:如果一個(gè)語言被PDA

識(shí)別,則這個(gè)語言是CFL.證明:設(shè)PDAP=(Q,,,,q0,{qaccept}),構(gòu)造等價(jià)CFGG=({Apq|p,qQ},,R,Aq0qaccept),R包含如下規(guī)則:ApqaArsb,(任何p,q,r,sQ,a,b

,t,(p,a,)包含(r,t)且

(s,b,t)包含(q,))ApqAprArq,(任何p,q,rQ)App,(任何pQ)ab(p,

)(r,t)(s,t)(q,

)《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》35引理3.15證明(續(xù)):下面證明Apq產(chǎn)生x,

當(dāng)且僅當(dāng)x把P從狀態(tài)p和空棧

一起帶到狀態(tài)q和空棧.斷言3.16:如果Apq產(chǎn)生x,

則x把P從狀態(tài)p和空棧一起

帶到狀態(tài)q和空棧.斷言3.17:如果x把P從狀態(tài)p和

空棧一起帶到