第七章下推自动机课件.ppt

1、1形式语言与自动机2主要内容主要内容qPDA描述描述CFL，所以它应该与，所以它应该与CFG等价。等价。qPDA应该包含应该包含FA的各个元素，或者包含那些可以取代的各个元素，或者包含那些可以取代FA的各个元素的功能的元素。的各个元素的功能的元素。q主要内容主要内容PDA的基本概念。的基本概念。PDA的构造举例。的构造举例。用终态接受语言和用空栈接受语言的等价性。用终态接受语言和用空栈接受语言的等价性。PDA是是CFL的接受器。的接受器。37.1基本定义基本定义qL(M)=anbn|n0不是正则语言。不是正则语言。aaaabbbbbbq这导致有限状态控制器中必须有无限状态。这导致有限状态控制器

2、中必须有无限状态。q需要扩充机器的能力。引入一个下推栈。需要扩充机器的能力。引入一个下推栈。4PDA的物理模型qPDA应该含有三个基本结构应该含有三个基本结构存放输入符号串的输入带存放输入符号串的输入带存放文法符号的栈存放文法符号的栈有穷状态控制器。有穷状态控制器。a1a2a3aj ZnZ0FSC栈顶栈顶下下堆堆栈栈5PDA的物理模型qPDA的动作的动作在有穷状态控制器的控制下根据它的当前状态、栈顶符号、在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作，在有的时候，不需要考虑输以及输入符号作出相应的动作，在有的时候，不需要考虑输入符号。入符号。a1a2a3aj Z

3、nZ0FSC栈顶栈顶下下堆堆栈栈6PDA 的定义下推自动机下推自动机(pushdownautomaton，PDA)M=(Q,q0,Z0,F)Q状状态态的的非非空空有有穷穷集集合合。qQ，q 称称为为M 的的一一个个状状态态(state)；输输入入字字母母表表(inputalphabet)。要要求求M的的输输入入字字符符串串都都是是上的字符串；上的字符串；栈符号表栈符号表(stackalphabet)。A，叫做一个栈符号；，叫做一个栈符号；Z0Z0叫叫做做开开始始符符号号(startsymbol)，是是M启启动动时时候候栈栈内内惟惟一的一个符号。所以，习惯地称其为一的一个符号。所以，习惯地称其为

4、栈底符号栈底符号；q0q0Q，是是M的的开开始始状状态态(initialstate)，也也可可叫叫做做初初始始状状态或者启动状态；态或者启动状态；FF Q，是，是M的的终止状态终止状态(finalstate)集合，简称为终态集。集合，简称为终态集。qF，q 称为称为M的终止状态，也可称为接受状态的终止状态，也可称为接受状态(acceptstate)，简称为，简称为终态终态。7PDA的定义q状态转移函数(transitionfunction)，有时候又叫做，有时候又叫做状态转换函数或者或者移动函数。:Q()(q,a,Z)=(p1,1),(p2,2),(pm,m)表示表示M在状态在状态q，栈顶符号

5、为，栈顶符号为Z时，读入字符时，读入字符a，对于，对于i=1,2,m，可以选择地将状态变成，可以选择地将状态变成pi，并，并将栈顶符号将栈顶符号Z弹弹出，将出，将i 中的符号从右到左依次压入栈中的符号从右到左依次压入栈，然后将读头向右，然后将读头向右移动一个带方格而指向输入字符串的下一个字符。移动一个带方格而指向输入字符串的下一个字符。(q,Z)=(p1,1),(p2,2),(pm,m)表示表示M进行一次进行一次-移动移动(空移动空移动)，即，即M在状态在状态q，栈顶符，栈顶符号为号为Z时，无论输入符号是什么，对于时，无论输入符号是什么，对于i=1,2,m，可以，可以选择地将状态变成选择地将状

6、态变成pi，并将栈顶符号并将栈顶符号Z弹出，将弹出，将i 中的符中的符号从右到左依次压入栈号从右到左依次压入栈，读头不移动。，读头不移动。qpa,Z/8符号使用约定q英文字母表较为前面的小写字母，如英文字母表较为前面的小写字母，如a,b,c,表示输入表示输入符号；符号；q英文字母表较为后面的小写字母，如英文字母表较为后面的小写字母，如x,y,z,表示输入表示输入字符串；字符串；q英文字母表的大写字母，表示栈符号；英文字母表的大写字母，表示栈符号；q希腊字母希腊字母,表示栈符号串。表示栈符号串。9即时描述q即时描述即时描述(instantaneousdescription，ID)(q,w,)(Q

7、,*,*)称为称为M 的一个的一个即时描述即时描述。它表示它表示M处于状态处于状态q，w是当前还未处理的输入字符串，是当前还未处理的输入字符串，而且而且M正注视着正注视着w 的首字符，栈中的符号串为的首字符，栈中的符号串为，的最左的最左符号为栈顶符号，最右符号为栈底的符号符号为栈顶符号，最右符号为栈底的符号，较左的符号在，较左的符号在栈的较上面，较右的符号在栈的较下面。栈的较上面，较右的符号在栈的较下面。10即时描述q如如果果(p,)(q,a,Z)，a，且且M 在在状状态态q、栈栈顶顶为为Z、读读入入a时，选择进入状态时，选择进入状态p，用，用替换栈顶替换栈顶Z，记为，记为(q,aw,Z)M(

8、p,w,)表示表示M 做一次非空移动，做一次非空移动，ID从从(q,aw,Z)变成变成(p,w,)。q如果如果(p,)(q,Z)，则记为，则记为(q,w,Z)M(p,w,)表示表示M 做一次空移动，做一次空移动，ID从从(q,w,Z)变成变成ID(p,w,)。qMn是是M的的n 次幂：次幂：(q1,w1,1)Mn(qn,wn,n)存在存在ID序列，并满足序列，并满足(q1,w1,1)M(q2,w2,2)MM(qn,wn,n)qM*是是M的克林闭包：的克林闭包：(q,w,)M*(p,x,)qM+是是M的正闭包：的正闭包：(q,w,)M+(p,x,)11M 接受的语言qM用用终态接受终态接受的语言

9、的语言L(M)=w|(q0,w,Z0)*(p,)且且pFqM 用用空栈接受空栈接受的语言的语言N(M)=w|(q0,w,Z0)*(p,)12例题构造构造PDAM，能够接受语言，能够接受语言L(M)=anbn|n0。设设PDAM=(Q,q0,Z0,F)其中：其中：Q=q0,q1,q2，=a,b，=Z0,A，F=q0定义如下：定义如下：(q0,a,Z0)=(q1,AZ0)(q1,a,A)=(q1,AA)(q1,b,A)=(q2,)(q2,b,A)=(q2,)(q2,Z0)=(q0,)q0q1a,Z0/AZ0q2,Z0/b,A/b,A/a,A/AAq当输入字符串是当输入字符串是ab 时，时，M 的工

10、作过程是：的工作过程是：(q0,ab,Z0)(q1,b,AZ0)(q2,Z0)(q0,)q当输入字符串是当输入字符串是aaabbb 时，时，M 的工作过程是：的工作过程是：(q0,aaabbb,Z0)(q1,aabbb,AZ0)(q1,abbb,AAZ0)(q1,bbb,AAAZ0)(q2,bb,AAZ0)(q2,b,AZ0)(q2,Z0)(q0,)13例7-1考虑接受语言考虑接受语言L=w2wT|w0,1*的的PDA的设计。的设计。解法解法1：利用利用GNF先设计产生先设计产生L的的CFGG1：G1：S2|0S0|1S1再将此文法转化成再将此文法转化成GNF：G2：S2|0SA|1SBA0B

11、114例7-1考察句子考察句子0102010的最左派生和我们希望相应的的最左派生和我们希望相应的PDAM的动作：的动作：派生派生M应该完成的动作应该完成的动作S0SA从从q0启动，读入启动，读入0，将，将S弹出栈，将弹出栈，将SA压入栈，状态不变压入栈，状态不变01SBA在状态在状态q0，读入，读入1，将，将S弹出栈，将弹出栈，将SB压入栈，状态不变压入栈，状态不变010SABA在状态在状态q0，读入，读入0，将，将S弹出栈，将弹出栈，将SA压入栈，状态不变压入栈，状态不变0102ABA在状态在状态q0，读入，读入2，将，将S弹出栈，将弹出栈，将压入栈，状态不变压入栈，状态不变01020BA在

12、状态在状态q0，读入，读入0，将，将A弹出栈，将弹出栈，将压入栈，状态不变压入栈，状态不变010201A在状态在状态q0，读入，读入1，将，将B弹出栈，将弹出栈，将压入栈，状态不变压入栈，状态不变0102010在状态在状态q0，读入，读入0，将，将A弹出栈，将弹出栈，将压入栈，状态不变压入栈，状态不变S2|0SA|1SBA0B115例7-1根据分析，可得如下根据分析，可得如下PDA：M1=(q0,0,1,2,S,A,B,1,q0,S,)。1(q0,0,S)=(q0,SA)1(q0,1,S)=(q0,SB)1(q0,2,S)=(q0,)1(q0,0,A)=(q0,)1(q0,1,B)=(q0,)

13、此时有：此时有：N(M1)=L。考虑用终态接受时，考虑用终态接受时，M2=(q0,q1,0,1,2,S,A,B,Z0,Z,2,q0,Z0,q1)2(q0,0,Z0)=(q0,SAZ)2(q0,1,Z0)=(q0,SBZ)2(q0,2,Z0)=(q1,)2(q0,0,S)=(q0,SA)2(q0,1,S)=(q0,SB)2(q0,2,S)=(q0,)2(q0,0,A)=(q0,)2(q0,1,B)=(q0,)2(q0,Z)=(q1,)此时有：此时有：N(M2)=L(M2)=L。演示：演示：011020110，看栈的变化情况。，看栈的变化情况。S2|0SA|1SBA0B116例7-1解法解法2：根

14、据根据2，将前后分为，将前后分为“记载记载”和和“匹配匹配”两个阶段两个阶段注意到注意到L=w2wT|w0,1*，所以，所以PDAM3的工作可以分成两大阶段：的工作可以分成两大阶段：(1)在在读到字符读到字符2之前之前，为，为“记载记载”阶段阶段：每读到一个符号就在栈中做一次相：每读到一个符号就在栈中做一次相应的记载。应的记载。例如，读到例如，读到0，就在栈中压入一个栈符号，就在栈中压入一个栈符号A；读到；读到1，在栈中压入符号，在栈中压入符号B。(2)在在读到读到2以后以后，再读到字符时，就应该，再读到字符时，就应该进入进入“匹配匹配”阶段阶段：由于栈的：由于栈的“先先进后出进后出”特性正好

15、与特性正好与wT相对应，所以，用栈顶符号逐一地与输入字符匹相对应，所以，用栈顶符号逐一地与输入字符匹配。配。在当前栈顶符号为在当前栈顶符号为A时，如果读到的字符为时，如果读到的字符为0，表示匹配成功；如果读，表示匹配成功；如果读到的字符为到的字符为1时，表示匹配失败，此时便得知输入的字符串不是句子。时，表示匹配失败，此时便得知输入的字符串不是句子。在当前栈顶符号为在当前栈顶符号为B时，如果读到的字符为时，如果读到的字符为1，表示匹配成功；如果读到，表示匹配成功；如果读到的字符为的字符为0时，表示匹配失败，此时便得知输入的字符串不是句子。时，表示匹配失败，此时便得知输入的字符串不是句子。当发现输

16、入字符串不是句子时，可以让当发现输入字符串不是句子时，可以让PDA停机停机不再有下一个动作，不再有下一个动作，也可以让它进入一个也可以让它进入一个“陷阱陷阱”状态。状态。17例7-1M3=(q0,q1,q2,qf,qt,0,1,2,A,B,Z0,3,q0,Z0,qf)q0为开始状态，为开始状态，q1为记录状态，为记录状态，q2为匹配状态，为匹配状态，qf为终止状态，为终止状态，qt陷阱状态陷阱状态3(q0,0,Z0)=(q1,AZ0)3(q0,1,Z0)=(q1,BZ0)3(q0,2,Z0)=(qf,)3(q1,0,A)=(q1,AA)3(q1,1,A)=(q1,BA)3(q1,0,B)=(q

17、1,AB)3(q1,1,B)=(q1,BB)3(q1,2,A)=(q2,A)3(q1,2,B)=(q2,B)3(q2,0,A)=(q2,)3(q2,0,B)=(qt,)3(q2,1,B)=(q2,)3(q2,1,A)=(qt,)3(q2,Z0)=(qf,)此时有：此时有：N(M3)=L(M3)=L。18例7-1q如果不追求让如果不追求让PDA同时用终止状态和空栈接受同样的语同时用终止状态和空栈接受同样的语言，还可以言，还可以删除状态删除状态qf。这样我们可以得到。这样我们可以得到PDAM4。qM4=(q0,q1,q2,0,1,2,A,B,Z0,4,q0,Z0,)4(q0,0,Z0)=(q1,A

18、Z0)4(q0,1,Z0)=(q1,BZ0)4(q0,2,Z0)=(q2,)4(q1,0,A)=(q1,AA)4(q1,1,A)=(q1,BA)4(q1,0,B)=(q1,AB)4(q1,1,B)=(q1,BB)4(q1,2,A)=(q2,A)4(q1,2,B)=(q2,B)4(q2,0,A)=(q2,)4(q2,1,B)=(q2,)q是否可以构造是否可以构造PDA，用于识别，用于识别w2w|w0,1*？原因：原因：无法将一个栈的内容在该栈中实现倒序操作无法将一个栈的内容在该栈中实现倒序操作。19例7-2 构造接受L=wwT|w0,1*的 PDAM=(q0,q1,qf,0,1,A,B,Z0,q

19、0,Z0,qf)q0处理句子的处理句子的w 部分，部分，q1处理句子的处理句子的wT 部分，部分，qf终止状态终止状态(q0,0,Z0)=(q0,AZ0)记下最开始读到的待匹配的记下最开始读到的待匹配的0(q0,1,Z0)=(q0,BZ0)记下最开始读到的待匹配的记下最开始读到的待匹配的1(q0,0,B)=(q0,AB)记下读到的待匹配的记下读到的待匹配的0(q0,1,A)=(q0,BA)记下读到的待匹配的记下读到的待匹配的1(q0,0,A)=(q0,AA),记下读到的待匹配的记下读到的待匹配的0(q1,)遇到遇到wT的首字符的首字符0，并开始匹配，并开始匹配(q0,1,B)=(q0,BB),

20、记下读到的待匹配的记下读到的待匹配的1(q1,)遇到遇到wT的首字符的首字符1，并开始匹配，并开始匹配(q1,0,A)=(q1,)0和和A匹配匹配(q1,1,B)=(q1,)1和和B匹配匹配(q1,Z0)=(qf,)将栈清空，并进入终止状态将栈清空，并进入终止状态(q0,Z0)=(qf,)接受接受差异差异(q0,0,A)=(q0,AA),(q1,)0是是w 中的中的0或者是或者是wT的首字符的首字符0；(q0,1,B)=(q0,BB),(q1,)1是是w 中的中的1或者是或者是wT的首字符的首字符1。207.2PDA与与CFG等价等价 q对于任意对于任意PDAM1，存在，存在PDAM2，使得，

21、使得L(M2)=N(M1)；q对于任意对于任意PDAM1，存在，存在PDAM2，使得，使得N(M2)=L(M1)。qCFL可以用空栈接受语言的可以用空栈接受语言的PDA接受。接受。qPDA接受语言可以用接受语言可以用CFG描述。描述。21定理 7-1对于任意对于任意PDAM1，存在，存在PDAM2，使得，使得N(M2)=L(M1)。设设PDAM1=(Q,1,q01,Z01,F)取取PDAM2=(Qq02,qe,Z02,2,q02,Z02,F)其中其中Qq02,qe=，Z02=。,Z02/Z01Z02q02,Z/qe,Z/qfa,Z01/aZ01q01M1(1)(2)(3)(4)22定理 7-1

22、,Z02/Z01Z02q02,Z/qe,Z/qfa,Z01/aZ01q01M1(1)(2)(3)(4)(1)在忽略在忽略M2的栈底符号的前提下，让的栈底符号的前提下，让M2启动后立即进入启动后立即进入M1的初始的初始ID。即进入。即进入M1的开始状态，并将的开始状态，并将M1的栈底符的栈底符号压入栈号压入栈2(q02,Z02)=(q01,Z01Z02)23定理 7-1,Z02/Z01Z02q02,Z/qe,Z/qfa,Z01/aZ01q01M1(1)(2)(3)(4)(2)M2完全模完全模拟拟M1的非空移的非空移动动(q,a,Z)Q,2(q,a,Z)=1(q,a,Z)；M2在非终止状态下完全模

23、拟在非终止状态下完全模拟M1的空移动的空移动(q,Z)(Q-F),2(q,Z)=1(q,Z)；24定理 7-1,Z02/Z01Z02q02,Z/qe,Z/qfa,Z01/aZ01q01M1(1)(2)(3)(4)(3)在在M1的的终终止止状状态态下下，M2模模拟拟M1的的“接接受受动动作作”，此此动动作作之后，之后，M1栈可能仍然是不空的栈可能仍然是不空的，故，故M2需要进行清栈状态。需要进行清栈状态。(q,Z)F，2(q,Z)=1(q,Z)(qe,)；M1栈栈已已空空，并并且且已已经经进进入入了了终终止止状状态态，所所以以M2进进入入清清栈栈状态状态qe，准备将栈清空。，准备将栈清空。qF,

24、2(q,Z02)=(qe,)；25定理 7-1,Z02/Z01Z02q02,Z/qe,Z/qfa,Z01/aZ01q01M1(1)(2)(3)(4)(4)M2完成清栈工作完成清栈工作 ZZ02,2(qe,Z)=(qe,)26定理 7-1下面证明下面证明N(M2)=L(M1)。xL(M1)(q01,x,Z01)M1*(q,)且且qF(q01,x,Z01Z02)M1*(q,Z02)且且qF(q01,x,Z01Z02)M2*(q,Z02)且且qFM2*(qe,Z02)M2*(qe,)且且qF(q01,x,Z01Z02)M2*(qe,)注意：注意：(q02,x,Z02)M2(q01,x,Z01Z02)

25、M2*(qe,)(q02,x,Z02)M2*(qe,)xN(M2)27定理7-2 对于任意对于任意PDAM1，存在，存在PDAM2，使得，使得L(M2)=N(M1)。设设PDAM1=(Q,1,q01,Z01,)qf,Z02/Z01Z02q02,Z02/,Z02/a,Z01/aZ01q01M1空栈接受空栈接受(1)(2)(3)取取PDAM2=(Qq02,qf,Z02,q02,Z02,qf)其中其中Qq02,qf=Z02=。M2应知道应知道M1什么时候将栈什么时候将栈弹空？弹空？28定理7-2 qf,Z02/Z01Z02q02,Z02/,Z02/a,Z01/aZ01q01M1空栈接受空栈接受(1)

26、(2)(3)(1)让让M2进入进入M1的开始状态，并将的开始状态，并将M2的栈底符号压入栈。的栈底符号压入栈。2(q02,Z02)=(q01,Z01Z02)29定理7-2 qf,Z02/Z01Z02q02,Z02/,Z02/a,Z01/aZ01q01M1空栈接受空栈接受(1)(2)(3)(2)M2完全模拟完全模拟M1的移动。的移动。对于对于(q,a,Z)Q(),2(q,a,Z)=1(q,a,Z)30定理7-2 qf,Z02/Z01Z02q02,Z02/,Z02/a,Z01/aZ01q01M1空栈接受空栈接受(1)(2)(3)(3)M1的栈已空时，的栈已空时，M2的栈底符号成为栈中的唯一符号。因

27、此，的栈底符号成为栈中的唯一符号。因此，无论此时处于什么状态，无论此时处于什么状态，M2都应当进入终止状态。都应当进入终止状态。2(q,Z02)=(qf,)证明略31定理7-2(2)证明证明L(M2)=N(M1)。xL(M2)(q02,x,Z02)M2*(qf,)(q02,x,Z02)M2(q01,x,Z01Z02)(q02,x,Z02)M2(q01,x,Z01Z02)M2*(qf,)。(q01,x,Z01Z02)M2*(q,Z02)且且(q,Z02)M2*(qf,)(q01,x,Z01Z02)M1*(q,Z02)(q01,x,Z01)M1*(q,)xN(M1)32给定CFL，构造PDA 定理

28、定理7-3对于任意对于任意CFLL，存在，存在PDAM，使得，使得N(M)=L。先考虑识别先考虑识别L-的的PDA，然后再考虑对，然后再考虑对的处理问题。的处理问题。(1)构造构造PDA。设设GNFG=(V,T,P,S)，使得，使得L(G)=L-。取取PDAM=(q,T,V,q,S,)对于任意的对于任意的AV，aT，(q,a,A)=(q,)|AaP 即即(q,)(q,a,A)的充分必要条件是的充分必要条件是AaP。(2)L，增加，增加(q,S)=(q,)。33定理定理7-3(2)证明构造的正确性：证明构造的正确性：N(M)=L-。施归纳于施归纳于w的长度的长度n，证明，证明(q，w，S)Mn(

29、q，)的充分必要条件为的充分必要条件为Snw。并且在假设结论对并且在假设结论对n=k成立，而证明结论对成立，而证明结论对n=k+1成立时，取成立时，取w=xa，|x|=k，aT。在证明必要性时有如下过程，充分性的证明过程是倒。在证明必要性时有如下过程，充分性的证明过程是倒退回来。退回来。(q,w,S)=(q，xa，S)Mk(q，a，)M(q，)此时必定存在此时必定存在AV，=A1，(q,2)(q,a,A)。(q,a,)=(q,a,A1)M(q,21)=(q，)。由由(q，2)(q，a，A)就可以得到就可以得到Aa2P，再由归纳假设，得到，再由归纳假设，得到SkxA1。合起来就有合起来就有Skx

30、A1xa21。34定理7-3(2)考虑考虑L 的情况。的情况。先按照先按照(1)的构造方法构造出的构造方法构造出PDAM=(q,T,V,q,S,)使得使得N(M)=L-。然后取。然后取M1=(q,q0,T,VZ,1,q0,Z,)其中其中q0q，Z V，令，令1(q0,Z)=(q0,),(q0,S)，对于对于(a,A)TV1(q,a,A)=(q,a,A)35例 7-3构造与如下构造与如下GNF等价的等价的PDA。SaT|aTaT|bT|a|b(q,a,S)=(q,T),(q,)(q,a,T)=(q,T),(q,)(q,b,T)=(q,T),(q,)36给定 CFL，构造 PDA(方法2)对于任意

31、对于任意CFLL，存在，存在PDAM，使得，使得N(M)=L。PDA试图确定是否存在关于输入串试图确定是否存在关于输入串w的推导。的推导。设计设计M，就是要确定是否有一系列使用，就是要确定是否有一系列使用G的产生式的替换，的产生式的替换，使得能够从起始符号导出使得能够从起始符号导出w。(1)把文法起始符号放入栈中。把文法起始符号放入栈中。(2)重复下述步骤：重复下述步骤：如果栈顶是非终结符如果栈顶是非终结符A，则非确定地选择一个关于，则非确定地选择一个关于A的产生的产生式，并且把式，并且把A替换成这条产生式右边的字符串。替换成这条产生式右边的字符串。如果栈顶是终结字符如果栈顶是终结字符a，则读

32、输入中的下一个字符，并且把，则读输入中的下一个字符，并且把它与它与a 进行比较。进行比较。如果匹配，则转向如果匹配，则转向(2)。如果它们不匹配，则这个非确定性分支被拒绝。如果它们不匹配，则这个非确定性分支被拒绝。如果栈空，且此刻输入已经全部读完，则接受这个输入串。如果栈空，且此刻输入已经全部读完，则接受这个输入串。37给定CFL，构造PDA 设设CFLG=(V,T,P,S)构造构造PDAM=(Q,q0,Z0,F)其中其中Q=q，=T，=VT，q0=q，Z0=S，F=定义如下：定义如下：(1)对于每一个变量对于每一个变量A(q,A)=(q,)|A是是G中的一个产生式中的一个产生式(2)对于每一

33、个终结符对于每一个终结符a(q,a,a)=(q,)38给定CFL，构造PDA 例例设计设计PDAM接受接受L(G)，其中，其中G 的产生式如下：的产生式如下：SaTb|bTTa|q,S/aTb,S/b,T/Ta,T/a,a/b,b/由于对栈中非终结符的替换总是在栈顶进行，由于对栈中非终结符的替换总是在栈顶进行，因此，因此，PDA实际上模拟的是文法的最左推导。实际上模拟的是文法的最左推导。解解(q,S)=(q,aTb),(q,b)(q,T)=(q,Ta),(q,)(q,a,a)=(q,)(q,b,b)=(q,)39定理7-4 定理定理7-4对于任意的对于任意的PDAM，存在，存在CFGG使得使得

34、L(G)=N(M)。考虑：考虑：PDA的移动的移动(q1,A1A2An)(q,a,A)的模拟的模拟用产生式用产生式q,Aaq1,A1A2An模拟模拟?用产生式用产生式q,Aaq1,A1q2,A2qn,An模拟模拟?用如下形式的产生式模拟。用如下形式的产生式模拟。qi,Ai,qi+1：qi为当前状态，符号为当前状态，符号Ai 表示相应的栈顶符号，表示相应的栈顶符号，qi+1表示当前的次栈顶表示当前的次栈顶Ai+1变成栈顶时的状态。变成栈顶时的状态。q,A,qn+1aq1,A1,q2q2,A2,q3qn,An,qn+1q2,qn 是分别对应是分别对应PDA恰恰“处理完处理完”A1进而处理进而处理A

35、2,，恰恰“处理完处理完”An-1进而处理进而处理An的状态。的状态。当然就有了恰当然就有了恰“处理完处理完”An而进入的状态而进入的状态qn+1，这个状态，这个状态就是就是“处理完处理完”A后其次栈顶变为栈顶的状态。后其次栈顶变为栈顶的状态。40定理7-4取取CFGG=(V,P,S)，其中：，其中：V=SQQP=Sq0,Z0,q|qQq,A,qn+1aq1,A1,q2q2,A2,q3qn,An,qn+1|(q1,A1A2An)(q,a,A)且且a,q2,q3,qn,qn+1Q且且n1q,A,q1a|(q1,)(q,a,A)仅需证明：仅需证明：q,A,p*x的充分必要条件是的充分必要条件是(q

36、,x,A)(p,)41定理7-4(2)构造的正确性。构造的正确性。先证一个更一般的结论：先证一个更一般的结论：q,A,p*x 的充分必要条件是的充分必要条件是(q,x,A)(p,)，然后根据这个一般的结论得到然后根据这个一般的结论得到q=q0，A=S时的特殊结论时的特殊结论构造的正确性。构造的正确性。q必要性：设必要性：设q,A,pi x，施归纳于，施归纳于i，证明，证明(q,x,A)*(p,)q充分性：设充分性：设(q,x,A)i(p,)成立，成立，施归纳于施归纳于i 证明证明q,A,p*X。42例7-4构造构造CFGG，使得，使得G产生的语言为如下产生的语言为如下PDAM用空栈接受用空栈接

37、受的语言。的语言。M=(q0,0,1,2,Z,A,B,q0,Z,)(q0,0,Z)=(q0,ZA)(q0,1,Z)=(q0,ZB)(q0,2,Z)=(q0,)(q0,0,A)=(q0,)(q0,1,B)=(q0,)43例7-4设设S为开始符号，为开始符号，G的产生式集合的构造过程如下：的产生式集合的构造过程如下：Sq0,Z,q0根据根据(q0,0,Z)=(q0,ZA)可得可得q0,Z,q00q0,Z,q0q0,A,q0根据根据(q0,1,Z)=(q0,ZB)可得可得q0,Z,q01q0,Z,q0q0,B,q0根据根据(q0,2,Z)=(q0,)可得可得q0,Z,q02根据根据(q0,0,A)=

38、(q0,)可得可得q0,A,q00根据根据(q0,1,B)=(q0,)可得可得q0,B,q0144例7-4变量变量q0已经失去了符号之间的区分作用，可将其删除：已经失去了符号之间的区分作用，可将其删除：SZZ0ZA|1ZB|2A0B1化简后可到一个化简后可到一个GNF：S0ZA|1ZB|2Z0ZA|1ZB|2A0B145确定的(Deterministic)PDAq在下推自动机中：在下推自动机中：(q,a,Z)=(p1,1),(p2,2),(pm,m)(q,Z)=(p1,1),(p2,2),(pm,m)q确定的确定的(deterministic)PDA(q,a,Z)Q,|(q,a,Z)|+|(q

39、,Z)|1简单地记为简单地记为DPDAM。q关键关键对于对于(q,Z)Q，M 此时如果有非空移动，就不能有空此时如果有非空移动，就不能有空移动。移动。每一种情况下的移动都是惟一的。每一种情况下的移动都是惟一的。q对于对于DPDA，终态和空栈接受的语言是不等价的。，终态和空栈接受的语言是不等价的。qDPDA以终态接受的语言真包含以终态接受的语言真包含RL，但真包含于，但真包含于CFL。46本章小结 qPDAM是一个七元组：是一个七元组：M=(Q,q0,Z0,F)q它是它是CFL的识别模型，它比的识别模型，它比FA多了栈符号，这些符号和多了栈符号，这些符号和状态一起用来记录相关的语法信息。状态一起

40、用来记录相关的语法信息。q在决定移动时，它将栈顶符号作为考虑的因素之一。在决定移动时，它将栈顶符号作为考虑的因素之一。qPDA可以用终态接受语言，也可以用空栈接受语言。可以用终态接受语言，也可以用空栈接受语言。q与与DFA不同，不同，(q,a,Z)Q，DPDA仅要求仅要求|(q,a,Z)|+|(q,Z)|1q关于关于CFG和和PDA主要有如下结论：主要有如下结论：(1)对于任意对于任意PDAM1，存在，存在PDA M2，使得，使得N(M2)=L(M1);(2)对于任意对于任意PDAM1，存在，存在PDA M2，使得，使得L(M2)=N(M1);(3)对于任意对于任意CFLL，存在，存在PDAM，使得，使得N(M)=L;(4)对于任意的对于任意的PDAM，存在，存在CFGG，使得，使得L(G)=N(M)。47作业q1、8、1148练习q设设L=w|w 中中0和和1的个数不相同的个数不相同，用泵引理证明，用泵引理证明L 不不是正则语言。是正则语言。q构造构造PDAM，接受语言，接受语言L(M)=aibjck|i=j 或或i=k。49练习q构造构造PDAM，接受语言，接受语言L(M)=aibjck|i=j 或或i=k。q3,Z/Zq0a,a/aaa,Z0/aZ0c,Z0/Z0q1b,a/,Z0/q2c,Z0/Z0,Z/Zq6c,a/q4b,Z/Z,Z0/q5c,a/