资源描述
,FormalLanguagesandAutomataTheory,6上下文无关文法与下推自动机,语言aibi|i0是不能被有穷自动机所接受的。要接受这个语言，机器需要记录某一a的有限次数，有限状态机的约束不允许自动机“记住”输入串中a的个数。因此我们需要定义一个新型自动机，它由一个下推栈加上一个有限自动机组成，称为下推自动机（PDA）。,6.1下推自动机(1),定义：下推自动机（pushdownautomation)是一个七元组（Q，q0，z,F）,其中Q是一有穷状态集，为一有穷字母表，为一有一有穷下推集，q0为开始状态，z为下推字符,FQ是终止状态集，是从Q（）（P）到Q（P）的转移函数。一个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)newstatecurrentstacktopnewstacktopcurrentinputsymbolcurrentstate表示i)状态由qi换为qiii)处理字符a,输入带向前移动iii）栈顶A退栈iv）B进栈。,6.1下推自动机(3),一个下推自动也可由状态转换图表示，弧上的符号表示输入符号和栈操作。转换函qj,B（qi，a，A)表示如下：aA/Bqiqj符号/表示B代替A可以出现在输入字符和栈顶位置，分别三种转换函数。（1）qi,（qi，A)（输入位置是）A/A出栈qi,6.1下推自动机(4),（2）qi,A（qi，)（输入位置是）/A（A压栈，不改变输入状态）qi（3）qj,（qi，a，)a/(等价于有限自动机，转换由状态和输入符号决定）qiqj一个PDA可表示为一个三元组qi,，qi是机器状态，为未处理的输入串,为栈顶。qi,qj,v,表示qj,v,由qi,经一步转换而得。,6.1下推自动机(5),例1：构造一个PDA接受语言aibi|i=0M:Q=q0,q1a/AbA/bA/=a,b=AF=q0,q1(q0,a,)=q0,A(q0,b,A)=q1,(q1,b,A)=q1,q0,aabb,q0,abb,Aq0,bb,AAq0,b,Aq0,q0q1,6.1下推自动机(6),定义：设M（Q，q0，F）为一PDA，字符串被PDA接受，如果q0,*qi,qiF（终态的集合）例2：PDAM接受语言cR|a,b*M:Q=q0,q1=a,b,c=A,BF=q1(q0,a,)=q0,Ab/BbB/(q0,b,)=q0,Ba/AaA/(q0,c,)=q1,q0c/q1(q1,a,A)=q1,(q1,b,B)=q1,6.1下推自动机(7),例3：PDAM接受语言ai|i=0aibi|i=0a/AbA/q0bA/q1/q2A/,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)=(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下推自动机与上下文无关文法,一个上下文无关语言都存在一个NPDA能够授受它;反之亦然.1.上下文无关语言相应的下推自动机对于每一个上下文无关文法语言都存在一个NPDA可以接受它.它的基本思想是构造一个NPDA能够以某种方式对于该语言中任何符号串产生一个最左推导.为了对命题稍做简化,我们可以假定上下文无关语言是由格里巴克范式生成的.定理:对于任何的上下文无关文法语言L,存在一个NPDAM使得L=L(M).,已知文法SaSbb|a,构造NPDA.首先修改文法转换为格里巴克范式:SaSA|aAbBBb,2.下推自动机相应的上下文无关文法使用文法模拟PDA的转移,这也就是说使句型中的变量部分反映栈的内容,而已处理的输入作为句型的仅含终结符前缀.为了简单,我们将假定问题中的NPDA满足如下条件:(1)它只有一个终态qf,且当且仅当栈空是才进入终态.(2)所有转移函数的形式应该是(qi,a,A)=c1,c2,cn,其中C=(qj,)或C=(qj,BC)定理:对于任何一个NPDAM,如果L=L(M),则L是上下文无关语言.,6.3上下文无关语言的性质(泵引理）(1),定理：(2型语言的泵作用引理)设L是上下文无关语言，存在常数p，如果L，且p,则可以写为uvwxy，其中i)vx，ii)vwxpiii)uviwxiyL(i0)线性语言的泵作用引理是说，在正规集合中，每个足够长的字符串都包含一个短的字串，随便将这个子串在原处重复插入多少次，所得的新字串还是在原正规集中。2型语言的泵引理是说，有两个靠得很近的子串，它们可以重复任意多次（但二者重复的次数相同），所得的新串依然属于该2型语言。,6.3上下文无关语言的性质(泵引理）(2),证明Lanbncn|n1不是2型语言.证：假设L是2型语言。取常数p，apbpcp,3pp将写成uvwxy其中vx1且vwxp考虑vwx在中所处的位置：如果v含有a，x含有c，apbpcp则有vwx最小为abpcp+2p不满足泵作用引理的条件。如果v,x都含有a，（b或c）apbpcp可写成aiap-2-i-jajbpcpvwx将v、x重复2次，将有=a2iap-2-i-ja2jbpcpL(a的个数大于b和c的个数)与2型语言的假设矛盾,6.3上下文无关语言的性质(泵引理）(3),若v、x分别包含a和b（b和c）当取w=aaap-2bbp-1cp时uvwxy将v、x重复2次，将有=aa2ap-2b2bp-1cpLvwx（其中a、b个数将大于c的个数）与2型语言假设矛盾。综上，L不是2型语言。,6.3上下文无关语言的性质(泵引理）(4),证明：La*|的长度为质数不是上下文无关文法。证明：设L是上下文无关文法，n是一个大于泵作用引理中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不是上下文无关文法。证明语言anbjanbj|i,j=0不是上下文无关语言。,6.3上下文无关语言的性质(封闭性）,（1）设有2型语言L1、L2，则L1L2，L1L2，L1*为2型语言。（2）2型语言对交不封闭反证：取反例L1anbncmm,n12型L2ambncnm,n12型L1L2anbncnn1不是2型（3）2型语言对补运算不封闭L1L2=L1L2若对补封闭，则对交封闭。已知对交不封闭，对补不封闭,
展开阅读全文