单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章,上下文无关文法与下推自动机,第四讲下 推 自 动 机,一、有关概念,1,、下推自动机的特点,特点：,下推自动机,PDA(Push Down Automaton),是一种类似于,NFA,的新型计算机模型，它比,NFA,多了一个下推栈下推栈在控制器的有限存储量之外增加了一个附加的存储，从而使得下推自动机能够识别某些非正则语言引例：,前面曾用泵浦定理,(,定理,6,）证明：,L(M)=a,n,b,n,|n1,不是正则集这就表明无法用有限自动机来识别该语言这是因为：,对于任意的正整数,k,，至少必须有一个状态用以记住“,k,个,a”,，则用状态转换图表示这种情况，在对任意大的,n,来说，有如下,无限状态转换图,：,.,.,a,a,a,a,b,b,b,b,b,b,显然，上述无限状态的模型是无法用有限状态自动机来表示的，因此需要扩充机器的能力一、有关概念,1,、下推自动机的特点,引例：,前面曾用泵浦定理,(,定理,6,）证明：,L(M)=a,n,b,n,|n1,不是正则集这就表明无法用有限自动机来识别该语言。
这是因为：,对于任意的正整数,k,，至少必须有一个状态用以记住“,k,个,a”,，则用状态转换图表示这种情况，在对任意大的,n,来说，有如下,无限状态转换图,：,.,.,a,a,a,a,b,b,b,b,b,b,显然，上述无限状态的模型是无法用有限状态自动机来表示的，因此需要扩充机器的能力一、有关概念,1,、下推自动机的特点,引例：,前面曾用泵浦定理,(,定理,6,）证明：,L(M)=a,n,b,n,|n1,不是正则集这就表明无法用有限自动机来识别该语言这是因为：,对于任意的正整数,k,，至少必须有一个状态用以记住“,k,个,a”,，则用状态转换图表示这种情况，在对任意大的,n,来说，有如下,无限状态转换图,：,.,.,a,a,a,a,b,b,b,b,b,b,显然，上述无限状态的模型是无法用有限状态自动机来表示的，因此需要扩充机器的能力下推自动机拥有一个容量不受限制的下推“栈”，所以它可以解决许多实际问题例如：对于非正则语言,L(M)=a,n,b,n,|n1,，,由于,PDA,能够利用栈容量的无界性保存大量的信息，可以动态跟踪保存,a,的个数，从而,PDA,能够识别这个语言,一、有关概念,1,、下推自动机的特点,组成：,下推自动机,(PDA),是由一条输入带、一个有限控制器和一个下推栈组成的。
其示意图如下：,a,b,b,b,c,c,a,.,输入带,有限控制器,A,B,C,Z,0,.,.,下推栈,栈顶元素,栈底元素,一、有关概念,1,、下推自动机的特点,注意,1,：,下推自动机,(PDA),在能力上与上下文无关文法等价只不过上下文无关文法是以产生语言的方式而存在的；而下推自动机是以识别语言的方式而存在的这个等价性对于后面许多定理的证明来说提供了很多方便注意,2,：,有些语言用生成器（文法）描述较为容易，而另一些语言又可能用识别器（下推自动机）描述更容易一些注意,3,：,下推自动机,(PDA),与有限自动机类似，亦分为确定的下推自动机,(DPDA),和不确定的下推自动机,(NPDA),一、有关概念,2,、不确定的下推自动机,定义：,下推自动机,M,是一个七元组：,M=(Q,T,q,0,Z,0,F),，其中,状态转换图：,Q:,有限控制器的状态集合；,T:,有限的输入字母表；,:,有限的下推栈字母表；,q,0,:,初始状态，,q,0,Q,；,Z,0,:,下推栈的起始符号，,Z,0,；,F:,终止状态集合，,F,Q,；,:,转换函数，是从,Q(T,),到,Q,*,的映射当有转换函数,(q,a,Z)=(p,)(q,p,Q,a,T,Z,*,),时,表示在状态,q,输入字符,a,且下推栈的栈顶字符为,Z,时，进入状态,p,，下推栈的,栈顶字符,Z,由字符串,替代,，同时读头右移一位。
这个过程的状态转换图如右图所示：,q,p,a,Z/,约定,：当,|,|1,时，,的最左位放在栈的最高位；当,=,时，表示栈顶符号,Z,被弹出当,a=,时，称为,转换，这时不考虑输入字符，读头不移动，但状态发生改变，且栈顶元素被,替换注意：,Z,0,是栈底元素，在初始化时设定，可作为识别句子过程的结束标志一、有关概念,2,、不确定的下推自动机,格局及其应用：,重要回顾：原始的有限自动机中格局的定义：,定义,2,设有限自动机,M=(Q,T,q,0,F),对偶或称二元组,(q,w,),QT*,称为,M,的,格局,，并称,(q,0,w,),为,初始格局,；对于,q,F,称,(q,),为,终止格局,或,接受格局,若当前状态为,q,，当前读入字符为,a,，,若有状态转换函数,(q,a)=q,1,则,状态变换后的后继状态为,q,1,，此时,可用,格局变化,形式描述这一变换过程：,(q,a,w,)(q,1,w,),一、有关概念,2,、不确定的下推自动机,格局及其应用：,接受语言的两种方式：,格局,是一个三元组：,(q,w,),其中：,q,是当前状态,(q,Q,),；,w,是待输入的字符串,(,w,T,*,当,w,=,时，表示输入字符均已读完,),；,是栈中内容,(,*,当,=,时表示下推栈已弹空,),。
格局描述,下推自动机的瞬时工作状况：,当转换函数,(q,a,Z)=(p,),时，可用格局表示为：,(q,a,w,Z,)(p,w,),用,字符串替换栈顶,Z,，,a,为当前输入字符,终止状态方式接受：,当,PDA,以终止状态接受语言,L(M),时，有：,空栈方式接受：,当,PDA,以空栈接受语言,L,(M),时，有：,L(M)=,w,|(q,0,w,Z,0,)(q,),且,q,F,*,*,注意：,表示此时,w,恰好被读完，,q,F,表示此时也恰好进入终止状态L,(M)=,w,|(q,0,w,Z,0,)(q,),且,q,是,Q,中的任意状态,*,注意：这里第一个,表示此时,w,恰好被读完；第二个,表示此时栈恰好为空这里,q,是任意状态，说明空栈接受时对终止状态没有要求，因此可以认为终止状态集,F,为空集,一、有关概念,2,、不确定的下推自动机,实例：,构造一个,PDA M,，能够接受语言,L(M)=a,n,b,n,|n1,设,PDA M=,（,Q,T,q,0,Z,0,F),，其中：,Q=q,0,q,1,q,2,T=a,b,=Z,0,a,F=q,0,，,定义如下：,(q,0,a,Z,0,)=(q,1,aZ,0,),(q,1,a,a)=(q,1,aa),(q,1,b,a)=(q,2,),(q,2,b,a)=(q,2,),(q,2,Z,0,)=(q,0,),。
采用终止状态接收方式,一、有关概念,2,、不确定的下推自动机,实例：,构造一个,PDA M,，能够接受语言,L(M)=a,n,b,n,|n1,设,PDA M=,（,Q,T,q,0,Z,0,F),，其中：,Q=q,0,q,1,q,2,T=a,b,=Z,0,a,F=q,0,，,定义如下：,(q,0,a,Z,0,)=(q,1,aZ,0,),(q,1,a,a)=(q,1,aa),(q,1,b,a)=(q,2,),(q,2,b,a)=(q,2,),(q,2,Z,0,)=(q,0,),在,q,1,状态下，读入字符,a,时，用,aa,替代栈顶元素,a,，状态保持不变,(,即在状态,q,1,下，用栈来记录,a,的个数，将所有的,a,压入栈中,),一、有关概念,2,、不确定的下推自动机,实例：,构造一个,PDA M,，能够接受语言,L(M)=a,n,b,n,|n1,设,PDA M=,（,Q,T,q,0,Z,0,F),，其中：,Q=q,0,q,1,q,2,T=a,b,=Z,0,a,F=q,0,，,定义如下：,(q,0,a,Z,0,)=(q,1,aZ,0,),(q,1,a,a)=(q,1,aa),(q,1,b,a)=(q,2,),(q,2,b,a)=(q,2,),(q,2,Z,0,)=(q,0,),。
此处,表示弹出栈顶元素,a,即以空元素替代栈顶元素,a,（也既输入的第一个字符,b,应与栈顶的,a,相匹配，故弹出该字符,a,，同时进入状态,q,2,）,一、有关概念,2,、不确定的下推自动机,实例：,构造一个,PDA M,，能够接受语言,L(M)=a,n,b,n,|n1,设,PDA M=,（,Q,T,q,0,Z,0,F),，其中：,Q=q,0,q,1,q,2,T=a,b,=Z,0,a,F=q,0,，,定义如下：,(q,0,a,Z,0,)=(q,1,aZ,0,),(q,1,a,a)=(q,1,aa),(q,1,b,a)=(q,2,),(q,2,b,a)=(q,2,),(q,2,Z,0,)=(q,0,),一旦进入,q,2,状态后，就只接受字符,b,且每读入一个,b,字符都应与栈顶的一个,a,字符相匹配，故从栈中弹出该字符,a,一、有关概念,2,、不确定的下推自动机,实例：,构造一个,PDA M,，能够接受语言,L(M)=a,n,b,n,|n1,设,PDA M=,（,Q,T,q,0,Z,0,F),，其中：,Q=q,0,q,1,q,2,T=a,b,=Z,0,a,F=q,0,，,定义如下：,(q,0,a,Z,0,)=(q,1,aZ,0,),(q,1,a,a)=(q,1,aa),(q,1,b,a)=(q,2,),(q,2,b,a)=(q,2,),(q,2,Z,0,)=(q,0,),。
在,q,2,状态下，一旦遇见栈底元素,Z,0,，且此时剩余输入串恰好为空串，则弹出,Z,0,使栈为空，同时进入终止状态,q,0,从而以终止状态接受输入字符串一、有关概念,2,、不确定的下推自动机,实例：,构造一个,PDA M,，能够接受语言,L(M)=a,n,b,n,|n1,设,PDA M=,（,Q,T,q,0,Z,0,F),，其中：,Q=q,0,q,1,q,2,T=a,b,=Z,0,a,F=q,0,，,定义如下：,(q,0,a,Z,0,)=(q,1,aZ,0,),(q,1,a,a)=(q,1,aa),(q,1,b,a)=(q,2,),(q,2,b,a)=(q,2,),(q,2,Z,0,)=(q,0,),PDA M,的状态转换图如右：,q,0,q,1,q,2,a,Z,0,/aZ,0,Z,0,/,b,a/,b,a/,a,a/,aa,当输入字符串,aaabbb,时，,M,的工作过程是：,(q,0,aaabbb,Z,0,)(q,1,aabbb,aZ,0,)(q,1,abbb,aaZ,0,),(q,1,bbb,aaaZ,0,)(q,2,bb,aaZ,0,)(q,2,b,aZ,0,),(q,2,Z,0,),(q,0,),注意：在本例中，对于每一个格局的下一步（即后继格局）都只有一种选择，这样的,PDA,称为确定的下推自动机,(DPDA),一、有关概念,2,、不确定的下推自动机,确定的下推自动机之定义：,下推自动机,M=(Q,T,q,0,Z,0,F),，如果是确定的，必须满足以下两个条件之一：,对任意的,q,Q,，,Z,和,a,T,，有：,(q,a,Z),只含一个元素，且,(q,Z)=,(,即函数值无定义,),;,(q,a,Z)=,(,函数值无定义,),且,(q,Z),只含一个元素。
注意,1,：,上述定义中，,“,只含一个元素,”,保证了,函数的,“,确定性,”,同时,避免了在同样的状态、同样的栈顶元素下，在,读入一个符号时发生状态转移和在不读入字符时发生状态转移之间作选择的可能性也即,在任何一个,格局状态下只有唯一的一个后继格局,注意,2,：,不满足条件的,PDA,即为不确定的,PDA,与有限自动机不同，不确定的,PDA,的描述能力强于确定的,PDA,的描述能力也即,某些确定的,PDA,不能描述的语言可以用不确定的,PDA,来描述,即只有一个函。