《FormalLanguagesandAutomataTheory-第六章-课件.ppt》由会员分享，可在线阅读，更多相关《FormalLanguagesandAutomataTheory-第六章-课件.ppt（20页珍藏版）》请在三一办公上搜索。
1、,Formal Languages and Automata Theory,6上下文无关文法与下推自动机,语言ai bi|i0是不能被有穷自动机所接受的。要接受这个语言，机器需要记录某一a的有限次数，有限状态机的约束不允许自动机“记住”输入串中a的个数。因此我们需要定义一个新型自动机，它由一个下推栈加上一个有限自动机组成，称为下推自动机（PDA）。,6.1 下推自动机(1),定义：下推自动机（pushdown automation)是一个七元组（Q，q0，z,F）,其中Q是一有穷状态集，为一有穷字母表，为一有一有穷下推集，q0为开始状态，z为下推字符,FQ是终止状态集，是从Q（）（P）到Q（P
2、）的转移函数。一个PDA有两个字符集：输入字符串它由输入字符串组成，有一个栈字符集P，它的元素存在栈中。A 表示以A为栈顶元素的栈，空栈被表示为。PDA的计算开始于状态q0，输入在输入带上且栈为空。PDA的当前状态、输入符号和栈顶符号决定自动机的转换。转换函数列出所有给定状态、符号和栈顶元素的所有可能的转换。（qi，a,A)=qj,B,qk,C表示当前状态为qi，输入符号为a，栈顶符号为A时的两种可能的转换。,6.1 下推自动机(2),qj,B（qi，a，A)new state current stack top new stack top current input symbol curre
3、nt state 表示 i)状态由qi换为qi ii)处理字符a,输入带向前移动iii）栈顶A退栈iv）B进栈。,6.1 下推自动机(3),一个下推自动也可由状态转换图表示，弧上的符号表示输入符号和栈操作。转换函qj,B（qi，a，A)表示如下：a A/Bqi qj 符号/表示B代替A 可以出现在输入字符和栈顶位置，分别三种转换函数。（1）qi,（qi，A)（输入位置是）A/A出栈 qi,6.1 下推自动机(4),（2）qi,A（qi，)（输入位置是）/A（A压栈，不改变输入状态）qi（3）qj,（qi，a，)a/(等价于有限自动机，转换由状态和输入符号决定）qi qj一个PDA可表示为一个三
4、元组qi,，qi是机器状态，为未处理的输入串,为栈顶。qi,qj,v,表示qj,v,由qi,经一步转换而得。,6.1 下推自动机(5),例1：构造一个PDA接受语言ai bi|i=0 M:Q=q0,q1 a/A b A/b A/=a,b=A F=q0,q1(q0,a,)=q0,A(q0,b,A)=q1,(q1,b,A)=q1,q0,aabb,q0,abb,A q0,bb,AA q0,b,A q0,q0 q1,6.1 下推自动机(6),定义：设M（Q，q0，F）为一PDA，字符串被PDA接受，如果q0,*qi,qiF（终态的集合）例2：PDAM接受语言 c R|a,b*M:Q=q0,q1=a,b
5、,c=A,B F=q1(q0,a,)=q0,A b/B b B/(q0,b,)=q0,B a/A a A/(q0,c,)=q1,q0 c/q1(q1,a,A)=q1,(q1,b,B)=q1,6.1 下推自动机(7),例3：PDAM接受语言 ai|i=0 ai bi|i=0 a/A b A/q0 b A/q1/q2 A/,6.1 下推自动机(8),例4:含有相同个数的0和1的所有的0,1串。思想：用栈记录0和1个数的差。当1比0多时，栈中全部为A，且A的个数等于1比0多的个数；当0比1多时，栈中全部为B，且B的个数等于0比1多的个数。M=(q,p,0,1,A,B,Z,q,Z,p)，其中(q,Z)
6、=(p,)接受，读完字符串后栈中没有A或B，转到终止状态(q,1,Z)=(q,A)在前面0和1个数相等的时候又读到1，则在栈中压入1个A(q,0,Z)=(q,B)在前面0和1个数相等的时候又读到0，则在栈中压入1个B(q,1,A)=(q,AA)在前面1比0个数多的时候又读到1，则在栈中再压入1个A(q,0,A)=(q,)在前面1比0个数多的时候又读到0，则从栈中弹出1个A(q,1,B)=(q,)在前面0比1个数多的时候又读到1，则从栈中弹出1个B(q,0,B)=(q,BB)在前面0比1个数多的时候又读到0，则在栈中压入1个B根据文法构造 G：S1S0S|0S1S|,构造语言的 NPDA,6.2
7、 下推自动机与上下文无关文法,一个上下文无关语言都存在一个NPDA能够授受它;反之亦然.1.上下文无关语言相应的下推自动机 对于每一个上下文无关文法语言都存在一个NPDA可以接受它.它的基本思想是构造一个NPDA能够以某种方式对于该语言中任何符号串产生一个最左推导.为了对命题稍做简化,我们可以假定上下文无关语言是由格里巴克范式生成的.定理:对于任何的上下文无关文法语言L,存在一个NPDA M使得L=L(M).,已知文法SaSbb|a,构造NPDA.首先修改文法转换为格里巴克范式:SaSA|a AbB Bb,2.下推自动机相应的上下文无关文法 使用文法模拟PDA的转移,这也就是说使句型中的变量部
8、分反映栈的内容,而已处理的输入作为句型的仅含终结符前缀.为了简单,我们将假定问题中的NPDA满足如下条件:(1)它只有一个终态qf,且当且仅当栈空是才进入终态.(2)所有转移函数的形式应该是(qi,a,A)=c1,c2,cn,其中C=(qj,)或C=(qj,BC)定理:对于任何一个NPDA M,如果L=L(M),则L是上下文无关语言.,6.3 上下文无关语言的性质(泵引理）(1),定理：(2型语言的泵作用引理)设L是上下文无关语言，存在常数p，如果L，且p,则可以写为uvwxy，其中i)vx，ii)vwxp iii)uviwxiyL(i0)线性语言的泵作用引理是说，在正规集合中，每个足够长的字
9、符串都包含一个短的字串，随便将这个子串在原处重复插入多少次，所得的新字串还是在原正规集中。2型语言的泵引理是说，有两个靠得很近的子串，它们可以重复任意多次（但二者重复的次数相同），所得的新串依然属于该2型语言。,6.3上下文无关语言的性质(泵引理）(2),证明 Lan bn cn|n1 不是2型语言.证：假设L是2型语言。取常数p，ap bp cp,3pp 将写成uvwxy 其中vx1 且 vwxp 考虑vwx在中所处的位置：如果v含有a，x含有c，apbpcp 则有vwx最小为a bp c p+2 p 不满足泵作用引理的条件。如果v,x都含有a，（b或c）ap bp cp 可写成ai ap-
10、2-i-j aj bp cp v w x 将v、x重复2次，将有=a2iap-2-i-j a2j bp cp L(a的个数大于b和c的个数)与2型语言的假设矛盾,6.3上下文无关语言的性质(泵引理）(3),若v、x分别包含a和b（b和c）当取w=a a ap-2b bp-1 cp 时 u v w x y 将v、x重复2次，将有=a a2 ap-2b2 bp-1 cp L v w x（其中a、b个数将大于c的个数）与2型语言假设矛盾。综上，L不是2型语言。,6.3上下文无关语言的性质(泵引理）(4),证明：La*|的长度为质数不是上下文无关文法。证明：设L是上下文无关文法，n是一个大于泵作用引理
11、中p的素数.由泵作用引理知：an必须分解为uvwxy满足泵引理的条件令mu|+|w|+|y|,任意串uviwxiy的长度是m+i(n-m).|uvn+1|+|wxn+1|+|y|=m+(n+1)(n-m)=n(n-m+1)故uviwxiy的长度不是质数，所以L不是上下文无关文法。证明语言an bjanbj|i,j=0不是上下文无关语言。,6.3上下文无关语言的性质(封闭性）,（1）设有2型语言L1、L2，则L1L2，L1L2，L1*为2型语言。（2）2型语言对交不封闭 反证：取反例 L1an bncm m,n1 2型 L2 am bncnm,n1 2型 L1L2an bncn n1 不是2型（3）2型语言对补运算不封闭L1L2=L1L2若对补封闭，则对交封闭。已知对交不封闭，对补不封闭,
