形式語言與自動機

1、1,College of Computer Science & Technology, BUPT,4.4,下推自動機（,PDA,）,?,主要內(nèi)容,?,PDA,的基本概念。,?,PDA,的構(gòu)造舉例。,?,用終態(tài)接受語言和用空棧接受語言的等價性。,?,PDA,是上下文無關(guān)語言的接收器。,?,重點,?,PDA,的基本定義及其構(gòu)造,?,PDA,與上下文無關(guān)語言等價,?,難點,?,根據(jù),PDA,構(gòu)造上下文無關(guān)文法。,2,College of Computer Science & Technology, BUPT,問題的引出,?,類似于,a,n,b,n,的語言無法由一般的有限自動機識別。,?,有限,狀態(tài)識

2、別器中必須有,無限個,狀態(tài),(,不允許,!),需要擴充機器的能力。,a,a,a,a,b,b,b,b,b,b,識別,a,n,b,n,的無限狀態(tài)自動機,3,College of Computer Science & Technology, BUPT,下推自動機的結(jié)構(gòu),?,擴充辦法：引入一個下推棧,足夠簡單,可解決許多有意義的問題，,如識別有效的程序,?,下推自動機,PDA,（,Push Down Automaton,）,由一條輸入帶,一個有限狀態(tài)控制器和一個下推棧組成,?,PDA,的動作,在有限狀態(tài)控制器的控制下根據(jù)它的當前狀態(tài)、棧頂符號、以,及輸入符號作出相應(yīng)的動作。有時，不需要考慮輸入符號（空

3、,轉(zhuǎn)移）,。,?,棧：后進先出表,對棧的操作（壓入、彈出）均在棧頂進行。,4,College of Computer Science & Technology, BUPT,下推自動機的定義,?,NPDA,的形式定義：,七元組,M,（,Q,，,T,，,q,0,，,z,0,，,F,）,其中：,Q,：有限控制器的狀態(tài)集合,T,：有限輸入字母表,：有限下推棧字母表,：,Q,（,T,）,Q,*,當前狀態(tài),當前輸入,當前棧頂符號,有限子集,q,0,：初始狀態(tài)，,q,0,Q,z,0,：下推棧的起始符號，,z,0,F,：,終態(tài)集合，,F,?,Q,5,College of Computer Science &

4、Technology, BUPT,下推自動機的轉(zhuǎn)換函數(shù),?,轉(zhuǎn)換函數(shù),(q,，,a,，,Z), (p,，,) ,q,、,p,Q，aT，Z，,*,表示在狀態(tài),q,，輸入字符,a,，且棧頂符,Z,時，轉(zhuǎn)入狀態(tài),p,，棧,頂符,Z,由,代替，同時讀頭右移一格。,?,約定：,的最左符號放在棧頂。,表示下推棧的頂符被彈出,如,（,q,，,a,，,Z,）,(p,，,),（,q,，,，,Z,）,(p,，,),稱為,轉(zhuǎn)換。,即不考慮當前輸入字符，讀頭不移動，但控制器狀態(tài)可以,改變且棧頂符可以調(diào)整。,6,College of Computer Science & Technology, BUPT,下推自動機的格

5、局,?,格局：用于描述,PDA,的瞬時工作狀況,PDA,格局,(,q, , ),其中,T*,，,*,q,當前狀態(tài),待輸入串,(,時，表示輸入字符已讀完,),下推棧中的內(nèi)容,(,時表示棧已彈空,),?,(,q,，,a,，,Z,),(p,，,r),用格局可表示為,(q,a,Z,),(p,r),對,PDA,而言，,初始格局為（,q,0,，,z,0,）,終止格局為（,q,，）,q,F，,*,7,College of Computer Science & Technology, BUPT,下推自動機接受的語言,?,兩種接受方式,?,終態(tài)接受：,L(M)=,(q,0,，,，,z,0,)*,(q,，,，,)

6、,，,q,F,*,?,空棧接受：,L(M)=,(q,0,，,，,z,0,),*,(,q,，,，,),q,Q,（當空棧接受時，終止狀態(tài)可為,Q,中任意狀態(tài)，換言之，,終止狀態(tài)集是與狀態(tài)無關(guān)的。此時，取,F,）,8,College of Computer Science & Technology, BUPT,下推自動機例,?,例：構(gòu)造,PDA M,，接受語言,L(M)= a,n,b,n,n0,?,思路：把輸入的字符,a,入棧，當開始輸入,b,時，從棧中彈出,a,，,若,a,、,b,個數(shù)相同，則到達終態(tài)，且棧中空。,?,解：設(shè),PDA M,（,Q,，,T,，,q,0,，,z,0,，,F,），,Q,q

7、,0,，,q,1,，,q,2,q,0,初態(tài)；接受,a,q,1,狀態(tài)；接受,b,q,2,狀態(tài)；輸入,回到,q,0,T,a,b, = z,0, a, F = q,0,定義為：,(q,0,，,a,，,z,0,) = ( q,1,，,a z,0,),(q,1,，,a,，,a),=,(,q,1,，,aa),(q,1,，,b,，,a),=,(,q,2,，),(q,2,，,z,0,),=,(,q,0,，),(q,2,，,b,，,a) = ( q,2,，),9,College of Computer Science & Technology, BUPT,下推自動機的圖形表示,?,上例的圖形表示,：,q,a,Z

8、/,p,表示（,p,，）（,q,，,a,，,Z,）,注：棧空就不能再移動了,a, z,0,/az,0,b, a/,a,a/aa,b,a/,z,0,/,q,0,q,2,q,1,用格局表示,aabb,的識別過程,:,(q,0,，,aabb,，,z,0,),（,q,1,，,abb,，,az,0,）,（,q,1,，,bb,，,aaz,0,）,（,q,2,，,b,，,az,0,）,（,q,2,，,z,0,）,（,q,0,，）,終態(tài)接受,10,College of Computer Science & Technology, BUPT,若對于每個輸入字符，其后續(xù)狀態(tài)都是確定的，就是,DPDA,（如前例）,

9、。,?,DPDA,必須滿足下述二個條件之一：,對,?,q,Q，,?,z,?,a,T有,(q,，,a,，,z,),最多含一個后續(xù)選擇且（,q,，,z,）,或者,(q,，,a,，,z,),且（,q,，,z,）最多含一個元素。,這兩個限制防止了在動作和包含一個輸入符號的動作之,間做選擇的可能性（即在同樣狀態(tài)，同樣棧頂符號下最多,只能有一個選擇。）,確定的下推自動機（,DPDA,）,11,College of Computer Science & Technology, BUPT,例：,構(gòu)造,PDA M,，接受語言,L(M) = c,T,a,b,*,.,解題思路：,從狀態(tài),q,0,接受句子，將輸入存到

10、棧中，狀態(tài)不變，直到看,到中心標記,c,。,當達到,c,時，將狀態(tài)變?yōu)?q,1,，棧不變。,將輸入與下推棧匹配，狀態(tài)不變，退棧，直至棧空。,確定的下推自動機（,DPDA,）,q,0,c,Z/Z,q,1,z,0,/,q,f,a,z/az,a,a/,b,z/bz,b,b/,該自動機的形式定義：見書,P157,12,College of Computer Science & Technology, BUPT,例：,構(gòu)造,PDA M,，接受語言,L(M) = ,T,a,b,*,.,(,與前面的例子類似，區(qū)別在于中間沒有標志”,c,”,),解：,非確定的下推自動機（,NPDA,）,q,0,?,Z/Z,q

11、,1,z,0,/,q,f,a,z/az,a,a/,b,z/bz,b,b/,把“,c,，,z/z,”,改為“，,z/z,”,就引進了非確定性。因為,機器可在任何時刻進行這種轉(zhuǎn)換。,13,College of Computer Science & Technology, BUPT,例：,構(gòu)造,PDA M,，接受語言,L(M) = a,i,b,j,c,k,i = j,或,i = k,。,解題思路：,與前例類似，利用不確定性，,PDA,可以猜想,a,應(yīng)與,b,匹配還是與,c,匹配。,所構(gòu)造的,NPDA M,利用兩個不確定的分支實現(xiàn)不同的猜想。,解：,非確定的下推自動機（,NPDA,）,14,Colle

12、ge of Computer Science & Technology, BUPT,z,1,/,z,0,z,1,a, z,0,/,z/,z/,M,?,M,f,q,0,q,f,q,e,q,1,定理,4.4.1,如果,L,f,是,PDA M,f,以終態(tài)接受的語言，必存在一個,PDA M,以空棧,接受語言,L,，使,L,L,f,證明：,設(shè),M,f,（,Q,，,T,，,，,，,q,0,，,z,0,，,F,）,構(gòu)造,PDA,M,（,Q,q,e,q,1,，,T,，,z,1,，,1,，,q,1,，,z,1,，）,用,M,模擬,M,f,空棧接受與終態(tài)接受的等價,對所有qf F和z z1,1,(q,f,，,z)

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