形式語言與自動(dòng)機(jī)

1、1College of Computer Science & Technology, BUPT4.4 下推自動(dòng)機(jī)（下推自動(dòng)機(jī)（PDA）n主要內(nèi)容nPDA的基本概念。nPDA的構(gòu)造舉例。n用終態(tài)接受語言和用空棧接受語言的等價(jià)性。nPDA是上下文無關(guān)語言的接收器。n重點(diǎn)nPDA的基本定義及其構(gòu)造nPDA與上下文無關(guān)語言等價(jià)n難點(diǎn)n根據(jù)PDA構(gòu)造上下文無關(guān)文法。2College of Computer Science & Technology, BUPT問題的引出問題的引出 類似于an bn 的語言無法由一般的有限自動(dòng)機(jī)識別。 有限有限狀態(tài)識別器中必須有無限個(gè)無限個(gè)狀態(tài) (不允許不允許!)!) 需要

2、擴(kuò)充機(jī)器的能力。需要擴(kuò)充機(jī)器的能力。 aaaabbbbbb識別an bn 的無限狀態(tài)自動(dòng)機(jī) 3College of Computer Science & Technology, BUPT下推自動(dòng)機(jī)的結(jié)構(gòu)下推自動(dòng)機(jī)的結(jié)構(gòu)n擴(kuò)充辦法：引入一個(gè)下推棧足夠簡單可解決許多有意義的問題，如識別有效的程序n下推自動(dòng)機(jī)PDA（PushDownAutomaton）由一條輸入帶,一個(gè)有限狀態(tài)控制器和一個(gè)下推棧組成nPDA的動(dòng)作在有限狀態(tài)控制器的控制下根據(jù)它的當(dāng)前狀態(tài)、棧頂符號、以及輸入符號作出相應(yīng)的動(dòng)作。有時(shí)，不需要考慮輸入符號（空轉(zhuǎn)移）。 n棧：后進(jìn)先出表對棧的操作（壓入、彈出）均在棧頂進(jìn)行。4College

3、of Computer Science & Technology, BUPT下推自動(dòng)機(jī)的定義下推自動(dòng)機(jī)的定義nNPDA的形式定義：七元組 M（Q，T，q0，z0，F(xiàn)）其中：Q：有限控制器的狀態(tài)集合 T：有限輸入字母表 ：有限下推棧字母表： Q （T） Q* 當(dāng)前狀態(tài) 當(dāng)前輸入 當(dāng)前棧頂符號 有限子集 q0：初始狀態(tài)，q0Q z0：下推棧的起始符號，z0 F： 終態(tài)集合，F(xiàn) Q5College of Computer Science & Technology, BUPT下推自動(dòng)機(jī)的下推自動(dòng)機(jī)的轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)n轉(zhuǎn)換函數(shù)(q，a，Z) (p，) q、pQ，aT，Z，*表示在狀態(tài)q，輸入字符a，且棧

4、頂符Z時(shí)，轉(zhuǎn)入狀態(tài)p，棧頂符Z由代替，同時(shí)讀頭右移一格。n約定：的最左符號放在棧頂。表示下推棧的頂符被彈出如（q，a，Z）(p，)（q，Z）(p，)稱為轉(zhuǎn)換。即不考慮當(dāng)前輸入字符，讀頭不移動(dòng)，但控制器狀態(tài)可以改變且棧頂符可以調(diào)整。6College of Computer Science & Technology, BUPT下推自動(dòng)機(jī)的下推自動(dòng)機(jī)的格局格局n格局：用于描述PDA的瞬時(shí)工作狀況PDA格局(q,)其中T*，*q當(dāng)前狀態(tài)待輸入串(時(shí)，表示輸入字符已讀完)下推棧中的內(nèi)容(時(shí)表示棧已彈空)n(q，a，Z ) (p，r) 用格局可表示為 (q, a,Z) (p, ,r)對PDA而言， 初始格

5、局為（q0，z0） 終止格局為（q，） qF，*7College of Computer Science & Technology, BUPT下推自動(dòng)機(jī)接受的下推自動(dòng)機(jī)接受的語言語言n兩種接受方式n終態(tài)接受：L(M)= (q0，z0)*(q，)，qF,*n空棧接受：L(M)= (q0，z0)*(q，),qQ（當(dāng)空棧接受時(shí)，終止?fàn)顟B(tài)可為Q中任意狀態(tài)，換言之，終止?fàn)顟B(tài)集是與狀態(tài)無關(guān)的。此時(shí)，取F）8College of Computer Science & Technology, BUPT下推自動(dòng)機(jī)例下推自動(dòng)機(jī)例n例：構(gòu)造PDA M，接受語言L(M)= anbnn0n思路：把輸入的字符a入棧，當(dāng)開

6、始輸入b時(shí)，從棧中彈出a， 若a、b個(gè)數(shù)相同，則到達(dá)終態(tài)，且棧中空。n解：設(shè)PDA M（Q，T，q0，z0，F(xiàn)）， Qq0 ，q1 ，q2 q0 初態(tài)；接受a q1狀態(tài)；接受b q2狀態(tài)；輸入 回到q0 Ta,b, = z0, a, F = q0定義為：(q0，a，z0) = ( q1 ，a z0) (q1，a，a) = ( q1 ，aa) (q1，b，a) = ( q2 ，) (q2，z0) = ( q0 ，) (q2，b，a) = ( q2 ，) 9College of Computer Science & Technology, BUPT下推自動(dòng)機(jī)的圖形表示下推自動(dòng)機(jī)的圖形表示 n上例的

7、圖形表示： q a, Z/ p表示（p，）（q，a，Z）注：?？站筒荒茉僖苿?dòng)了 a, z0/az0 b, a/ a, a/aa b, a/, z0/q0q2q1用格局表示aabb的識別過程:(q0 ，aabb，z0)（q1，abb，az0） （q1，bb，aaz0） （q2，b，az0） （q2，z0） （q0，） 終態(tài)接受終態(tài)接受10College of Computer Science & Technology, BUPT若對于每個(gè)輸入字符，其后續(xù)狀態(tài)都是確定的，就是DPDA（如前例）。 nDPDA必須滿足下述二個(gè)條件之一： 對 qQ， z, aT有 (q，a，z )最多含一個(gè)后續(xù)選擇且（

8、q，z） 或者 (q，a，z ) 且（q，z）最多含一個(gè)元素。這兩個(gè)限制防止了在動(dòng)作和包含一個(gè)輸入符號的動(dòng)作之間做選擇的可能性（即在同樣狀態(tài)，同樣棧頂符號下最多只能有一個(gè)選擇。）確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)（DPDADPDA） 11College of Computer Science & Technology, BUPT例：例：構(gòu)造PDA M，接受語言L(M) = cTa,b*.解題思路：解題思路： 從狀態(tài)q0接受句子，將輸入存到棧中，狀態(tài)不變，直到看到中心標(biāo)記c。 當(dāng)達(dá)到c時(shí)，將狀態(tài)變?yōu)閝1，棧不變。 將輸入與下推棧匹配，狀態(tài)不變，退棧，直至?？?。 確定的下推自動(dòng)機(jī)（確定的下推自動(dòng)機(jī)

9、（DPDADPDA） q0 c, Z/Z q1 , z0/ qf a, z/az a, a/ b, z/bz b, b/該自動(dòng)機(jī)的形式定義：見書P15712College of Computer Science & Technology, BUPT例：例：構(gòu)造PDA M，接受語言L(M) = Ta,b*. (與前面的例子類似，區(qū)別在于中間沒有標(biāo)志”c” )解：解：非確定的下推自動(dòng)機(jī)（非確定的下推自動(dòng)機(jī)（NPDANPDA） q0 , Z/Z q1 , z0/ qf a, z/az a, a/ b, z/bz b, b/ 把“c，z/z”改為“，z/z”就引進(jìn)了非確定性。因?yàn)闄C(jī)器可在任何時(shí)刻進(jìn)行這

10、種轉(zhuǎn)換。 13College of Computer Science & Technology, BUPT例：例：構(gòu)造PDA M，接受語言L(M) = ai bj ck i = j 或 i = k。解題思路：解題思路： 與前例類似，利用不確定性，PDA可以猜想a應(yīng)與b匹配還是與c匹配。所構(gòu)造的NPDA M利用兩個(gè)不確定的分支實(shí)現(xiàn)不同的猜想。 解：解：非確定的下推自動(dòng)機(jī)（非確定的下推自動(dòng)機(jī)（NPDANPDA） 14College of Computer Science & Technology, BUPT ,z1/z0z1 a, z0/ ,z/,z/ ,z/,z/ MMfq0qfqeq1定理定理

11、4.4.1 如果Lf是PDA Mf以終態(tài)接受的語言，必存在一個(gè)PDA M以空棧接受語言L，使LLf證明：證明：設(shè)Mf（Q，T，q0，z0，F(xiàn)） 構(gòu)造PDA M（Q qe ,q1，T， z1，1，q1，z1，） 用M模擬Mf空棧接受與終態(tài)接受的等價(jià)空棧接受與終態(tài)接受的等價(jià) 對所有qf F和z z1 1(q f，z) = ( q e ，) （當(dāng)M f進(jìn)入終態(tài)時(shí)，用轉(zhuǎn)換進(jìn)入qe狀態(tài)，彈出棧頂） 在q e狀態(tài)下，若棧不為，則不斷彈出棧頂符，直至?？?1定義： 1(q1，z1)=( q0 ，z0z1)(將z1作為棧底符，進(jìn)入Mf的起始狀態(tài)) 對所有qQ，aT,z令1(q，a，z)= (q，a，z) （即M模擬Mf的動(dòng)作）15College of Computer Science & Technology, BUPT定理定理4.4.2 如果L是PDA M 以空棧接受的語言，必存在一個(gè)PDA M f 以終態(tài)接受語言L，使 Lf L證明：證明： 設(shè)M（Q，T，q0，z0，）構(gòu)造PDA Mf （Q q0f ,qf ，T， z1，f，q 0f，z1， qf ） 空棧接受與終態(tài)接受的等價(jià)空棧接受與