计算理论课件第三章.ppt_三一办公31ppt.com

资源描述

《计算理论课件第三章.ppt》由会员分享，可在线阅读，更多相关《计算理论课件第三章.ppt（117页珍藏版）》请在三一办公上搜索。

1、,第三章,上下文无关文法与下推自动机,Context Free Grammar(CFG)and Push Down Automaton(PDA),上下文无关文法（CFG）在程序设计语言和编译原理中有着重要的应用，因为上下文无关文法可以用来阐述绝大多数的程序设计语言的句法结构。此外上下文无关语言也可以作为描述语言翻译方案的基础。本章重点讨论:CFG的简化 CFG的两种范式下推自动机（PDA）的概念 PDA与CFG之间的等价转换上下文无关语言运算的封闭性以及CFL的有关判定问题。,3.1 上下文无关文法的派生树(推导树),一个上下文无关文法中的一个句型的派生过程可以用棵树来描述。【例3-1.

2、1】给定文法G=(S,A,a,b,P,S)，其中 P：SaAS|a,ASbA|ba|SS。句型aabbaa的派生过程就可以用一棵树来描述，如图3-1.1所示。将此树的叶结点符号从左到右读取下来构成的符号串就是aabbaa。,1派生树的定义设文法 G=(,S)是上下文无关文法,如果一棵有序树满足下面四个条件，则它是棵派生树：(1)它的每个结点标记的符号是()中的符号；(2)根结点标记开始变元S；(3)内结点标记的符号是变元，即是中的符号。(4)如果一个内结点标记为A，且X1,X2,Xk是A的从左到右的所有子结点,则AX1X2Xk是P中一个产生式。(5)如果一个结点标记符号是，则它是其父结点的唯一

3、儿子结点。,其中第(5)条是为了防止下面情况发生：如产生式Aa(a是个终极符)被误认为是Aa或Aa，而在派生树中被画成如图3-2形式。2派生树的结果设T是棵派生树，将此树的叶结点符号从左到右依次读取下来构成的符号串就是此派生树的结果。例如，图3-1.1派生树的结果就是aabbaa。3派生树与句型的派生关系设G=(,S)是CFG，如果G中有派生S*，则在G中必有一棵以为结果的派生树。反之，如果G中有一棵以为结果的派生树，则G中也必有派生S*。可以说派生与派生树是一一对应的。,4最左派生与最右派生所谓最左派生，就是在一个派生的每一步都是对句型中最左边的变元进行替换。例如，例3-1中aabba

4、a的派生：SaASaSbASaabASaabbaSaabbaa，此派生是最左派生。所谓最右派生，就是在一个派生的每一步都是对句型中最右边的变元进行替换。SaASaAaaSbAaaSbbaaaabbaa,此派生是最右派生。5上下文无关文法的二义性设G是个CFG，如果它的某个句子有两棵不同构的派生树，则称G是二义性的上下文无关文法。,【例3-1.2】给定CFG G=(S,a,b,P,S)，其中P：SaSbS|bSaS|。句子abab的两棵不同构的派生树，如图3-1.3所示。,这说明此CFG G是有二义性的。,3.2 上下文无关文法的简化,一个上下文无关文法有时可以去掉一些符号，或者去掉一些产生式

5、以后，仍然和原来的文法等价，这就是所谓文法的简化。这里简化文法主要是指：去掉无用符号、去掉产生式和去掉单一产生式。1去掉无用符号定义：给定CFG G=(,S)，如果在G中存在派生S*X*w，其中w*，X，则称符号X是有用的，否则X是无用的。简单地说，无用符号就是G中对任何wL(G)的派生中都不会出现的符号。,【例3-2.1】给定文法G=(S,A,B,C,a,b,P,S)，其中P：SAB|a,ABC|a,Cb。G中有派生：可见再往下就无法推导了，因而由S只能推出a，不能推出其他符号串。所以此文法中，A、B、C、b都是无用的符号，只有S和a是有用符号。如何去掉无用符号？分两步走，使用两个引理，就

6、可以做到这一点。下面介绍这两个引理。,引理3-2.1 给定CFG G=(,S)，且L(G)，可以找到一个与G等价的CFG G=(,S)，使得每个A，都有w*，且在G中有A*w。证明：1）求的算法：begin OLD:=NEW:=A|AwP 且w*While OLDNEW do begin OLD:=NEW NEW:=OLDA|AP,且(OLD)*end:=NEW,end,下面证明此算法的有效性。显然对任何变元ANEW,不论A是在第步还是在第步加入到NEW中的,都有派生A*w,其中w*。只证明G中任何派生A*w，w*,必有ANEW。(对派生的步数归纳证明)a）若此派生是一步完成的，即有Aw，则说

7、明P中有产生式Aw，于是A在算法的第步被添加到NEW中。b）假设G中派生A*w是少于k步完成的,则ANEW。c）当G中有k步派生AX1X2 Xnk-1w，不妨设w=w1w2 wn，其中Xi*wi，(i=1,2,n)，而且由于这些派生的步数少于k步，如果Xi是变元，则根据假设b）得Xi最终会加入到NEW中。在执行算法的第步时OLD:=NEW,当最后一个Xi加入OLD时，在执行算法的第步时，就将A加入到NEW中。,这说明此算法是有效的，即凡是可以推出终极符串的变元都会添加到NEW中。于是，最后得到变元集合。2）构造文法G：G(,S)，其中 P：由P中只含有()的符号的产生式构成的。3）下面证明L(

8、G)=L(G)a）显然有L(G)L(G)，因为，P，所以G中任何派生S*w，在G中也有S*w。所以L(G)L(G)。b）证明L(G)L(G)，(反证法)任取wL(G)，假设wL(G),则说明在G中w的派生S*w中必用到PP中的产生式，即用到了中的变元，而这些变元又能推出终极符串，这与上面证明的此算法有效矛盾。所以必有wL(G),从而L(G)L(G)。最后得L(G)=L(G)。,【例3-2.2】给定CFG G=(S,A,B,C,a,b,P,S)，其中P：SA|B,AaB|bS|b,BAB|Ba,CAS|b求一个与之等价的文法G，使得G中的每个变元都可以推出终极符串。解：对G应用引理3-2.1，执

9、行上述算法，得到的结果如表3-2.1所示。,循环次数i 初值 1 2 3,OLD,NEW,当算法执行第三次循环时，判定OLD=NEW,算法终止。最后得GCFG G=(S,A,C,a,b,P,S),其中 P：SA,AbS|b,CAS|b实际上，只去掉了不能推出终极符串的变元B。,A,C,S,A,C,A,C,A,C,S,A,C,S,引理3-2.2 给定CFG G=(,S)，可以找到一个与G等价的CFG G，G=(,S)，使得每个X()，都有,()*，且在G中有派生S*X。证明：1执行下面迭代算法求和。1）置初值：:=S，:=;2）如果A，在P中又有产生式A1|2|m，则可以将1,2,m中的所有变元

10、加到中，将1,2,m中的所有终极符加到中中。重复2)。3）若没有新的符号可加入到、中，算法停止。最后得到、。,2构造P：是由P中只含有()中的符号的产生式构成的。3证明L(G)=L(G)a）显然有L(G)L(G)，因为，TT，P，所以G中任何派生S*w，在G中也有S*w。所以L(G)L(G)。b）证明L(G)L(G)，任取wL(G)，不妨设w在G中的派生为S*X*w，其中,()*，由上述算法可知，在此派生中出现的所有符号，都不会因为对G使用此引理而被去掉，所以这些符号必在中，此派生中所用到的产生式也在P中，所以这个派生在G中也可以实现，因而必有wL(G)。故L(G)L(G)。最后得L(G)=L

11、(G)。,定理3-2.1 设L是一个非空的上下文无关语言，则L可由一个不含无用符号的上下文无关文法产生。证明：设G=(,S)是个CFG，且L(G)=L。先对G用引理3-2.1处理后，得G(,S)，再将G 用引理3-2.2处理得G(,S)，由两个引理得L(G)=L(G)。下面证明G中不含无用符号。假设G中有无用符号Y。根据引理3-2.2得，在G中必存在派生S*Y，其中,()*，因为G的符号也都是G中的符号，所以此派生在G中也可以实现，又根据引理3-2.1得，和中的变元以及Y都可以推出终极符串，于是G中有派生：S*Y*w，w*，又因为派生Y*w中的符号不会因为对G用引理3-2.2而被去掉，所以在G

12、中也会实现派生Y*w，于是G中也有派生S*Y*w，这与符号Y是无用符号矛盾。所以G中不含无用符号。,值得注意的是，去掉G中无用符号时，一定要先用引理3-2.1，后用引理3-2.2。应用引理的次序不可颠倒，否则可能遗漏一些无用符号。请看下面例子。【例3-2.3】给定CFG G=(S,A,B,a,b,P,S)，其中P：SAB|a,Aa求一个与之等价的文法G”，使得G”中不含无用符号。解：先对G应用引理3-2.1方法处理，执行此算法得到的结果如表3-2.2所示。,当算法执行第二次循环时，判定OLDNEW，算法终止。最后得G：CFG G=(S,A,a,b,P,S)，其中 P：Sa,Aa。再对G用引理3

13、-2.2处理，执行算法的结果如表3-2.3所示：,最后得文法G(S,a,P,S)，其中P=Sa。但是，如果先对G用引理3-2.2，后用引理3-2.1就得到如下结果：,对G用引理3-2.2执行算法的结果，如表3-2.4所示：,得文法 G=(S,A,B,a,P,S)，P：SAB|a,Aa。再对G用引理3-2.1执行算法的结果如表3-2.5所示：,最后得文法 G=(S,A,a,P,S)，P：Sa,Aa。显然，这样做，无用符号A没有被去掉。可见去掉文法中无用符号时，使用这两个引理的先后次序是很重要的。,2去掉产生式定义：所谓产生式，就是形如A的产生式，其中A为变元。给定CFG G，如果L(G)，则G中

14、所有产生式都可以去掉。如果L(G)，则除了开始变元S的产生式(即S)外，其余产生式都可以去掉。为了去掉产生式，先定义一个概念可为零的变元。定义：设A是个变元，如果A*，则称A是可为零的。去掉CFG G中的产生式的思路是：首先，找出G中所有可为零的变元。然后，对P中每个形如AX1X2Xn的产生式进行如下处理：要添加一些这样的产生式：这些产生式是通过去掉X1X2Xn中某些可为零的变元而得到的。但是，如果所有Xi(i=1,2,n)都是可为零的，则不可全去掉，因为那样会产生新的产生式A。,【例3-2.6】有产生式：SaSAbB,设A与B都是可为零的，则由这个产生式变成如下四个产生式：SaSAbB,Sa

15、SbB(去掉A),SaSAb(去掉B),SaSb(A和B全去掉)。注意，要将所有可能的情况均考虑到，才能保证新的文法与原文法等价。定理3-2.2 给定CFG G=(,S)，可以找到一个不含无用符号，又无产生式的CFG G，使得L(G)L(G)。证明：假设G已经去掉了无用符号，从G中去掉产生式后得到文法G，令G(,S)，其中P构成如下：,1用下面迭代算法确定G中可为零的变元集合0。begin OLD0:=NEW0:=A|AP While OLD0NEW0 do begin OLD0:=NEW0 NEW0:=OLD0A|AP,且(OLD0)*end 0:=NEW0 end当OLD0=NEW0时，算

16、法终止，最后得到可为零的变元集合0。此算法与引理3-2.1中算法相似，类似可证此算法的有效性,2构造P：如果AX1X2XnP，则将所有形如A12n的产生式都加到P中，其中如果Xi不是可为零的，则iXi。如果Xi是可为零的，则iXi或者i。但是，如果所有Xi(i=1,2,n)都是可为零的，则不可所有i。3用归纳法证明：对任何A,任何w，有如果AG*w，当且仅当 AG*w。1）先证明充分性。设G中有派生AG*w，w。如果此派生是一步完成的，即G中有派生AGw，则AwP，因为w，所以AwP，所以G中也有派生AG*w。假设G中派生AG*w是少于k步完成的，则G中有派生AG*w。,当G中有派生AGX1

17、X2XnG*ww1w2wn是由k步完成的时，其中Xi()且有XiG*wi(i=1,2,n)，其中有的wi可能为。如果某个wi，则对应的Xi是可为零的变元。由G中派生AGX1X2Xn得AX1X2XnP，根据P的构成得，必有产生式A12nP，其中a）如果Xi G*wi，则iXi，于是有i G*wi，且此派生少于k步完成，由假设得G中有派生i G*wi。b）如果Xi G*wi，则Xi是可为零的变元，与Xi对应i，于是有i G*wi。最后G中有派生：A G 12n G*w1 2n G*w1w23n G*w1w2wnw,即G中有派生A G*w,充分性成立。,2）再证明必要性。设G中有派生AG*w，显然w

18、。.如果此派生是一步完成的，即G中有Aw，则AwP，因为w，于是P中有产生式Aw或者A，使得从中去掉某些可为零的变元后得到w，总之G中有派生AGw，或者AGG*w。.假设G中有派生AG*w是少于k步完成的，则G中有派生AG*w。.当G中派生AGX1X2 XnG*w1w2wnw是由k步完成时，此派生的第一步派生是用P中的产生式AX1X2Xn。根据P的构成知，P中必存在产生式A，使得从中去掉某些可为零的变元后就得到X1X2Xn，于是G中有派生：AGG*X1X2Xn,而在G的第二步及以后的派生X1X2XnG*w1w2wnw中，令Xi G*wi(i=1,2,.,n)，由于这些派生的步数少于k，由假设得

19、，Xi G*wi，于是G中也有派生：A GG*X1X2Xn G*w1X2Xn G*w1w2X3Xn G*w1w2wnw。所以必要性成立。最后得此结论成立。即如果AG*w，当且仅当 A G*w。当A=S时，则有SG*w，当且仅当 SG*w。于是有L(G)=L(G)。,3去掉单一产生式定义：所谓单一产生式，就是形如AB的产生式，其中A和B都是变元。定理3-2.3 每个不含有的上下文无关语言L，都可以由一个不含无用符号、无产生式、也无单一产生式的上下文无关文法产生。证明：令G(,S)是一个不含有无用符号，无产生式的上下文无关文法，且L(G)=L。构造一个CFG G(,S)，其中P的构成如下：包含P中

20、所有非单一产生式。对任何A,B，如果有AG*B，且B1|2|n是P中B的所有非单一产生式，则把所有A1|2|n加到P中。,(例如G中有产生式：AB,BC,CD,B,C,D，于是有A*B,A*C,A*D，B*C，B*D,C*D，则G中有产生式：A|，B|，C|，D。)下面证明L(G)=L(G)a）首先证明L(G)L(G)容易看出任何AP，则G中必有派生AG*。因为，如果AP，G中当然有派生AG，如果AP，则必有变元B，使得G中有派生 AG*BG。所以对任何wL(G),即SG*w，此派生中用到的所有产生式AP,则G中必有派生AG*。所以G中必有派生SG*w，所以wL(G)。因而L(G)L(G)。,

21、b）再证明L(G)L(G)任取wL(G)，设w在G中的最左派生如下：S0 1 2 3 n1 n w，下面分两种情况讨论：如果上述派生用的都是非单一产生式，则这些产生式在P中也有，所以这些派生在G中也可以实现。如果上述派生既用了单一产生式，也用了非单一产生式，不妨取出其中一段：i1 i i+1 j j+1,非单一单一非单一设从i-1 到i 用的是非单一产生式，从i到j用的是单一产生式，j到j+1用的又是非单一产生式。下面主要考察G中从i到j1的派生(此派生是先用单一产生式，后用非单一产生式)，看看这段派生在G中是如何实现的。,先看看从i到j用的是单一产生式的派生，不妨设 iyAi,i+1yA

22、i+1,jyAj，其中y*，()*从i到j的派生写成 yAi yAi+1 yAj，这些派生都是用单一产生式进行的。实际上相当于派生AiAi+1 Aj，所以有Ai*Aj。再看看j到j+1 的派生j j+1，它用的是非单一产生式，不妨设j+1y，()*，于是此派生写成yAj y，实际上此派生用的是非单一产生式Aj。于是G中有派生Ai*Aj，根据P的构成，则P中必有产生式 Ai。于是在G中有派生：iyAiyj+1，即在G中从i到j+1的派生是一步完成的。所以当SG*w 用了两种产生式时，G中也有派生SG*w。所以L(G)L(G)。最后得L(G)L(G)。,作业题1给定CFG G=(S,A,B,C,a

24、F形式的CFG G产生。证明：由定理3-2.3可知，对一个不含有的CFL L都可由一个不含无用符号、无产生式、无单一产生式的CFG G产生。不妨设CFG G=(,S)是一个不含无用符号、无产生式、无单一产生式的CFG,且L(G)=L。,1.先对P中产生式做如下处理：保留右侧只有一个符号的产生式，(此符号是终极符，)处理产生式AX1X2Xn(n2)：如果其中Xi是终极符a，则引入新的变元Ca，用Ca代替a，同时添加新的产生式Caa。经过此步处理后，使得产生式的形式只有两种：一种是Aa，a是终极符；另一种是AB1B2Bn，其中每个Bi都是变元(包括新引入的变元)。处理产生式AB1B2Bn(n3)(

25、因为n=2时符合要求)，引进新的变元D1D2Dn-2，此产生式用下面产生式替换：AB1D1,D1 B2D2,D2B3D3,Dn-3Bn-2Dn-2,Dn-2Bn-1Bn。显然用这n1个产生式代替AB1B2Bn，这是个等价变换。经过此步处理后，所有产生式的形式就具有CNF形式了:ABC,Da,其中A,B,C,D是变元，a是终极符。,2.构造新的CFG G=(,S)，其中中除了原来中的变元外，还含有新增加的所有变元。就是由经过上述处理后得到的具有CNF形式的产生式构成。3.容易证明L(G)=L(G),这里证明从略。【例3-3.1】G是个定义算术表达式的CFG G=(E,T,F,a,b,+,*,(,

26、),P,E),其中E表示算术表达式；T表示项；F表示因子。P含有下面这些产生式：EE+T|T TT*F|F F(E)|a|b求一个具有CNF 形式的CFG G,使得L(G)=L(G)。解：1先简化G，因为G中不含无用符号，也无产生式，所以只去掉单一产生式。1）去掉TF，添加如下产生式：T(E)|a|b 2）去掉ET，添加如下产生式：ET*F|(E)|a|b2保留符合要求的产生式：Ea|b,Ta|b,Fa|b,3处理产生式AX1X2Xn(n2)：终极符Xi变成变元。EE+T 变成 EEC+T C+ET*F 变成 ETC*F C*E(E)变成 EC(EC)C(C)TT*F 变成 TTC*F T(E

27、)变成 TC(EC)F(E)变成 FC(EC)4处理产生式AB1B2Bn(Bi都是变元,n3)：引进新的变元D1,D2,Dn-2。EEC+T 变成 EED1 D1C+T ETC*F 变成 ETD2 D2C*F EC(EC)变成 EC(D3 D3EC)TTC*F 变成 TTD2 TC(EC)变成 TC(D3 FC(EC)变成 FC(D3,5最后得具有CNF形式的CFG G=(,P,E),其中E,T,F,C+,C*,C(,C),D1,D2,D3 a,b,+,*,(,)P:EED1|TD2|C(D3|a|b TTD2|C(D3|a|b FC(D3|a|b D1C+T D2C*F D3EC)C+C*C

28、(C),3.4 CFG 的Greibach范式(GNF),下面我们讨论CFG的另外一种范式Greibach范式(GNF)。定义：CFG G=(,S)，P中产生式形式都是：Aa，其中a是一个终极符，a，是变元符号串，*，则称此文法具有GNF形式。任何一个不含有的CFL，都可以由一个具有GNF形式的CFG产生。那么如何将一个CFG变成具有GNF形式的CFG，应用下面两个引理可以实现。,引理3-4.1 设G=(,S)是个CFG，A1B2是P中一个产生式，又B1|2|3|m是P中变元B的所有产生式。又令G=(,S)，其中P构成如下：从P中删除A1B2，再添加产生式A112|122|132|1m2，则L

29、(G)=L(G)。证明：显然有L(G)L(G)。因为如果A1i2(1im)用在G的一个派生中，虽然在G中没有此产生式，但是在G中有如下派生：A1B21i2(1im)。所以G中的任何派生在G中也可以实现。所以L(G)L(G)。,再证明L(G)L(G)这里只需注意到G与G的差别是：只有A1B2是在G中而不在G中的产生式，而G中其余的产生式G中也有。所以只要A1B2用于G的一个派生中，在其后的某一步推导肯定用到产生式Bi，用以改变变元B，而这二步推导在G中用一步派生A1i2(1im)以代之。所以 L(G)L(G)。最后得L(G)L(G)。下面介绍的引理是处理带有左递归的产生式。这里所谓左递归的产生式

31、的派生在G中也可以实现。2.如果此派生先用AAj，最后必用Ai，才可以消去变元A，例如有如下派生：,A Aj1Aj2j1 Ajkjk-1j2j1 ijkjk-1j2j1,这个派生在G中也可以实现，如下所示：Ai Zijk Z ijkjk-1j 2 Z ijkjk-1j2j1,所以xL(G)。反之xL(G)，x在G中的派生，类似可证在G中也可以实现，所以xL(G)。最后得L(G)=L(G)。,定理3-4.1(Greibach定理)每个不含有的CFL L，都可以由一个具有GNF形式的CFG产生。证明：令G=(,A1)是个CFG，L(G)=L，L(G)，假设G已经具有CNF形式。不妨设A1,A2,A

32、3,An，按照如下方法处理P中产生式：1先暂时保留形如AiAjAk的产生式，其中ij，即用所有Aj产生式的右侧符号串代替该产生式中的Aj。3用引理3-4.2处理带有左递归的产生式AkAkj|i，(1jm)(1in)，用下面产生式替换：Ai|i Zk,Zkj|j Zk。4经过上述处理后，再依次将An,An-1,A2,A1产生式以及所有新增加的变元Zk(1kn)的产生式用引理3-4.1方法处理，使之都变成GNF形式。,由于我们对G的产生式的处理都是使用上面两个引理，所以最后得到的具有GNF形式的文法G必与G等价，即L(G)=L(G)。下面我们通过一个例子说明如何将G变成具有GNF形式的文法G的过程

33、。【例3-4.1】.令G=(A1,A2,A3,a,b,P,A1)，其中P：A1A2A3,A2A3A1,A2 b,A3 A1A2,A3 a,将G写成GNF形式。解：1.先暂时保留产生式、。2处理产生式 A3 A1A2：用的A1产生式右侧的A2A3替换中A1，得新产生式A3 A2A3A2。仍然不满足要求，再次对处理：用的A2产生式右侧符号串分别替换A2，得A3 A3A1A3A2,A3 bA3A2。这两个产生式符合要求。,3.处理有左递归的产生式 A3 A3A1A3A2,A3 bA3A2，A3 a。用引理3-4.2得：A3 bA3A2|a|bA3A2Z3|aZ3,Z3A1A3A2|A1A3A2Z3。

37、=(S,A,B,0,1,P,S)，P：S0SA|1SB|0A|1B,A0,B1G就是与G等价的具有GNF 形式的文法。容易看出L(G)=wwR|w0,1+下面用例子验证它们是等价的。例如，看看它们派生00100100的过程。在G中的派生：S0S000S00001S10000100100在G中的派生（最左派生）：S0SA00SAA001SBAA0010ABAA00100BAA001001AA0010010A00100100,作业题：1给定CFG G=(S,A,0,1,P,S)，其中，P：SAA0,ASS1,将G写成GNF形式。,3.5 下推自动机(Push Down Automaton,PDA)

38、,下面介绍识别CFL的自动机下推自动机。1PDA的结构,输入带：带上存放被识别的符号串。有限控制器：存放PDA的状态转移函数。下推栈：后进先出的下推栈。两个只读头：分别用来读取带上符号和栈内符号。,2PDA的形式定义下推自动机M=(K,q0,Z0,F)，其中 K状态的有限集合。输入带上的符号集合。栈内符号集合。q0q0K，开始状态。Z0Z0，开始时栈顶符号。FFK，终止状态集合。：状态转移函数，是映射K()2(K*)。,有两种状态转移函数：（1）扫描输入带上符号a，(q,a,Z)=(p1,1),(p2,2),(pm,m)，其中qK，a，Z，p1,p2,pmK,1,2,m*。此动作表示：在q状

39、态下，当前栈顶符号为Z，读取带上符号a后，状态改成pi,，并且用i代替栈顶符号Z(1im)，然后读头右移一个单元，准备读带上下一个符号。（2）-动作，一般用于读带上符号串的开头或者是末尾。(q,Z)=(p1,1),(p2,2),(pm,m)此动作表示：在q状态下，当前栈顶符号为Z，读取带上符号(实际上没有读符号，或者带上无符号可读)后，状态改成pi,，并且用i(1im)代替栈顶符号Z,然后，但是读头不动。,注意：假设栈内符号串从底到顶依次是ABCD，则要写成 DCBA,即栈顶符号写在左边，栈底符号写在右边。3通常使用符号的约定：1）用小写英文字母a、b、c表示输入带上的符号，即 a,b,c,。

40、2）用小写英文字母x、y、z表示输入带上带符号串，即 x,y,z,*。3）用大写英文字母A、B、C表示栈内符号，即 A,B,C,。4）用希腊字母、表示栈内符号串，即,*。,4.【例3-5.1】设计一个PDA M，使之接收语言LwcwR|w0,1*，例如0101c1010L。解：设计的思想是：PDA M 有两个状态，即K=q1,q2，有三个栈内符号，即R,B,G。它的动作设想：1).开始时，PDA M的状态为q1，栈内符号为R。2).当读c左边的符号时，M是在q1状态，此时如果读0，则向栈内压入符号B；如果读1，则向栈内压入符号G。例如，带上符号串是0101c1010，读完c左边的0101后，

41、栈内符号串为：GBGB。3).当读符号c时，状态变成q2。4).在此状态下之后读c右边的符号：如果读0，此时栈顶应该是B，则B退栈；如果读1，此时栈顶应该是G，则G退栈。,这样，当带上符号都读完时，栈内应该是符号R。再将R清除，使得栈内为空，进而接收输入带上的符号串。具体动作如下表所示：栈顶当前输入符号符号状态 0 1 c B q1 B入栈，状态为q1 G入栈，状态为q1 状态改成q2 q2 G q1 B入栈，状态为q1 G入栈，状态为q1 状态改成q2 q2 R q1 B入栈，状态为q1 G入栈，状态为q1 状态改成q2 q2,退栈顶，状态为q2,退栈顶，状态为q2,如果带上无符

42、号可读，则退栈顶R，否则，无动作。,表中符号“”表示无动作。当带上符号串都读完后，栈内为空，就说明带上符号串正是L中的句子。M的形式定义如下：,M的形式定义：M(q1,q2,0,1,c,R,B,G,q1,R,)：(q1,0,R)=(q1,BR)(q1,1,R)=(q1,GR)(q1,0,B)=(q1,BB)(q1,1,B)=(q1,GB)(q1,0,G)=(q1,BG)(q1,1,G)=(q1,GG)(q1,c,R)=(q2,R)(q1,c,B)=(q2,B)(q1,c,G)=(q2,G)(q2,0,B)=(q2,)(q2,1,G)=(q2,)(q2,R)=(q2,)(q2,0,R)=(q2,

43、1,R)=(q2,c,R)=(q2,1,B)=(q2,c,B)=(q2,0,G)=(q2,c,G)=这里(q2,R)=(q2,)的作用是：当读完带上所有符号时，清除下推栈，使之为空，接收带上符号串。,5PDA的瞬间描述ID(Instantaneous Description)PDA M的当前格局，称之为M的瞬间描述ID。用有序三元组(q,x,)表示瞬间描述ID，其中 q-qK,M的当前状态，x-x*,输入带上还没有被读到的符号串，-*,当前栈内符号串。例如上例中，当带上符号串为0011c1100时，开始的ID0：（q1,0011c1100,R），当读完第一个0后，变成ID1：（q1,011c1

44、100,BR）。：表示由一个ID，经过一个动作变成另一个ID时，ID之间的转变关系。例如上例中有 ID0ID1，即（q1,0011c1100,R）（q1,011c1100,BR）。*：表示经过多个动作后,ID之间的转变关系。,如上例中（q1,0011c1100,R）（q1,011c1100,BR）（q1,11c1100,BBR）（q1,1c1100,GBBR）（q1,c1100,GGBBR）（q2,1100,GGBBR）可以写成(q1,0011c1100,R)*(q1,1100,GGBBR)。6PDA M所接收的语言PDA M接收语言有两种方式：1).空栈接收的语言,记作N(M)：令 M=(K

45、,q0,Z0,),N(M)=w|w*,(q0,w,Z0)*(q,),qK即当M读完带上符号串w后，栈内为空，则接收w。上例中M识别0011c1100时，ID的变化过程：(q1,0011c1100,R)(q1,011c1100,BR)(q1,11c1100,BBR)(q1,1c1100,GBBR)(q1,c1100,GGBBR)(q2,1100,GGBBR)(q2,100,GBBR)(q2,00,BBR)(q2,0,BR)(q2,R)(q2,)接收0011c1100。,2)用终止状态接收的语言，记作T(M)：令M=(K,q0,Z0,F),T(M)=w|w*,(q0,w,Z0)*(q,),qF,*

46、即当M读完带上符号串w后，进入终止状态q，而栈内不一定为空，则接收输入符号串w。后面我们将证明这两种接收方式可以互相转换。上面介绍的PDA M中，每个状态转移函数的函数值最多有一个序偶。这相当于是个确定的PDA。下面的例子就不同了。7.【例3-5.2】设计一个PDA M，使之接收语言L如下：L=wwR|w0,1*，例如01011010L。此例与前例不同，前例w与wR之间有一个标志c，而此例的w与wR之间无标志，识别起来就麻烦一些。,解：设计的思想是：PDA M 有两个状态K=q1,q2，有三个栈内符号，即R,B,G。它的动作设想：1开始时，PDA M的状态为q1，栈顶符号为R。2 当读左半边的

47、符号串w时，M是在q1状态，这时如果读0，则向栈内压入符号B；如果读1，则向栈内压入符号G。当读完左半部分符号串w后，状态变成q2,之后，要读右半边的符号串wR，这时如果读0，此时栈顶应该是B，则B退栈；如果读1，此时栈顶应该是G，则G退栈；当带上符号都读完时，栈内应该是符号R。,问题是：如何判断w与wR的分界线。我们注意到w的末尾符号与wR开始符号相同。因此当连续读的两个符号相同时，就有两种可能：一种情况是这两个符号都是w中的符号，此时状态不变；另一种情况是前一个符号是w末尾的符号，而后一个符号是wR的第一个符号，此时就要改变状态。构造PDA M(q1,q2,0,1,R,B,G,q1,

48、R,)M的动作如下：(q1,0,R)=(q1,BR)(q1,1,R)=(q1,GR)(q1,0,B)=(q1,BB),(q2,)(q1,1,B)=(q1,GB)(q1,0,G)=(q1,BG)(q1,1,G)=(q1,GG),(q2,)(q2,0,B)=(q2,)(q2,1,G)=(q2,)(q2,R)=(q2,)(q1,R)=(q2,)(q2,0,R)=(q2,1,R)=(q2,1,B)=(q2,0,G)=,下面看看M识别110011的ID变换过程：注：符号“”表示执行动作得到后面的ID；符号“”表示执行动作得到下面的ID。(q1,110011,R)(q2,110011,)(q1,10011

49、,GR)(q2,0011,R)(q2,0011,)(q1,0011,GGR)(q1,011,BGGR)(q2,11,GGR)(q2,1,GR)(q1,11,BBGGR)(q2,R)(q1,1,GBBGGR)(q2,BBGGR)(q2,)(q1,GGBBGGR),作业题1构造一个PDA M，使得T(M)=w|wa,b*w 中的a,b的个数相等。,3.6 PDA与CFG之间的等价性,这里类似地介绍PDA与CFG之间的等价性。在介绍它们相互转换之前，先介绍PDA的两种接收语言方式可以互相转换。1PDA的两种接收语言方式互相转换定理3-6.1 设一个PDA M用空栈接收语言L，即N(M)=L，当且仅当

50、存在一个PDA M,使得M用终止状态接收L，即T(M)=L。证明：1必要性：设M=(K,q0,Z0,)，用空栈接收语言L，N(M)=L。构造 M=(Kq0,qf,Z0,q0,Z0,qf)，其中q0,qfK，Z0。,假设M接收句子w，即wN(M)，则M必有如下ID变换：M：(q0,w,Z0)*(q,)其中qKM要接收w，必须能够从它的开始ID（q0,w,Z0）进入到M的开始ID（q0,w,Z0），以后M就能够模拟M的所有动作，当达到M的终止时的ID（q,）时，最后进入M的终止状态qf，从而接收w。于是M的动作序列为：M：(q0,w,Z0)(q0,w,Z0Z0)*(q,Z0)(qf,)其中qK于是

展开阅读全文