FormalLanguagesandAutomataTheory--第六章--课件.ppt

,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）的转移函数。 一个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 current state 表示 i)状态由qi换为qi ii)处理字符a,输入带向前移动 iii）栈顶A退栈 iv）B进栈。,6.1 下推自动机(3),一个下推自动也可由状态转换图表示，弧上的符号表示输入符号和栈操作。转换函 qj,B （ qi，a，A) 表示如下： a A/B qi 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可表示为一个三元组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：PDA M接受语言 c R| a,b* M: Q=q0, q1 =a,b,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：PDA M接受语言 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)=(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,存在一个NPDA M使得L=L(M).,已知文法SaSbb|a,构造NPDA. 首先修改文法转换为格里巴克范式: SaSA|a AbB Bb,2.下推自动机相应的上下文无关文法 使用文法模拟PDA的转移,这也就是说使句型中的变量部分反映栈的内容, 而已处理的输入作为句型的仅含终结符前缀. 为了简单,我们将假定问题中的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 ) 线性语言的泵作用引理是说，在正规集合中，每个足够长的字符串都包 含一个短的字串，随便将这个子串在原处重复插入多少次，所得的新字串 还是在原正规集中。 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-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是一个大于泵作用引理中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上下文无