您好、欢迎来到现金彩票网!
当前位置:老k棋牌 > 栈下推 >

第三章第四讲下推自动机ppt

发布时间:2019-06-27 06:24 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第三章 上下文无关文法与下推自动机 第四讲 下 推 自 动 机 一、有关概念 1、下推自动机的特点 特点:下推自动机PDA(Push Down Automaton)是一种类似于NFA的新型计算机模型,它比NFA多了一个下推栈。下推栈在控制器的有限存储量之外增加了一个附加的存储,从而使得下推自动机能够识别某些非正则语言。 引例:前面曾用泵浦定理(定理6)证明:L(M)={anbnn≥1}不是正则集。这就表明无法用有限自动机来识别该语言。这是因为: 对于任意的正整数k,至少必须有一个状态用以记住“k个a”,则用状态转换图表示这种情况,在对任意大的n来说,有如下无限状态转换图: .......... .......... a a a a b b b b b b 显然,上述无限状态的模型是无法用有限状态自动机来表示的,因此需要扩充机器的能力。 一、有关概念 1、下推自动机的特点 引例:前面曾用泵浦定理(定理6)证明:L(M)={anbnn≥1}不是正则集。这就表明无法用有限自动机来识别该语言。这是因为: 对于任意的正整数k,至少必须有一个状态用以记住“k个a”,则用状态转换图表示这种情况,在对任意大的n来说,有如下无限状态转换图: .......... .......... a a a a b b b b b b 显然,上述无限状态的模型是无法用有限状态自动机来表示的,因此需要扩充机器的能力。 一、有关概念 1、下推自动机的特点 引例:前面曾用泵浦定理(定理6)证明:L(M)={anbnn≥1}不是正则集。这就表明无法用有限自动机来识别该语言。这是因为: 对于任意的正整数k,至少必须有一个状态用以记住“k个a”,则用状态转换图表示这种情况,在对任意大的n来说,有如下无限状态转换图: .......... .......... a a a a b b b b b b 显然,上述无限状态的模型是无法用有限状态自动机来表示的,因此需要扩充机器的能力。 下推自动机拥有一个容量不受限制的下推“栈”,所以它可以解决许多实际问题。例如:对于非正则语言L(M)={anbnn≥1},由于PDA能够利用栈容量的无界性保存大量的信息,可以动态跟踪保存a的个数,从而PDA能够识别这个语言。 一、有关概念 1、下推自动机的特点 组成:下推自动机(PDA)是由一条输入带、一个有限控制器和一个下推栈组成的。其示意图如下: a b b b c c a ...... 输入带 有限控制器 A B C Z0 . . 下推栈 栈顶元素 栈底元素 一、有关概念 1、下推自动机的特点 注意1:下推自动机(PDA)在能力上与上下文无关文法等价。只不过上下文无关文法是以产生语言的方式而存在的;而下推自动机是以识别语言的方式而存在的。这个等价性对于后面许多定理的证明来说提供了很多方便。 注意2:有些语言用生成器(文法)描述较为容易,而另一些语言又可能用识别器(下推自动机)描述更容易一些。 注意3:下推自动机(PDA)与有限自动机类似,亦分为确定的下推自动机(DPDA)和不确定的下推自动机(NPDA)。 一、有关概念 2、不确定的下推自动机 定义:下推自动机M是一个七元组:M=(Q,T,Γ,δ,q0,Z0,F),其中 状态转换图: Q:有限控制器的状态集合; T:有限的输入字母表; Γ:有限的下推栈字母表; q0 :初始状态,q0∈Q; Z0:下推栈的起始符号,Z0∈Γ; 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=ε时,称为ε转换,这时不考虑输入字符,读头不移动,但状态发生改变,且栈顶元素被α替换。 注意:Z0是栈底元素,在初始化时设定,可作为识别句子过程的结束标志。 一、有关概念 2、不确定的下推自动机 格局及其应用: 重要回顾:原始的有限自动机中格局的定义: 定义2 设有限自动机M=(Q,T,δ,q0,F), 对偶或称二元组 (q,w)∈Q×T*称为M的格局,并称(q0,w)为初始格局;对于q∈F,称(q,ε)为终止格局或接受格局。 若当前状态为q,当前读入字符为a,若有状态转换函数δ(q,a)=q1 , 则状态变换后的后继状态为q1,此时可用格局变化形式描述这一变换过程:(q,aw)├─(q1,w) 。 一、有关概念 2、不确定的下推自动机 格局及其应用: 接受语言的两种方式: 格局是一个三元组:(q,w,α),其中:q是当前状态(q∈Q);w是待输入的字符串(w∈T*,当w=ε时,表示输入字符均已读完);α是栈中内容(α∈Γ*,当α=ε时表示下推栈已弹空)。 格局描述下推自动机的瞬时工作状况: 当转换函数δ(q,a,Z)={(p,γ)} 时,可用格局表示为: (q , aw , Zα) (p , w , γα) 用γ字符串替换栈顶Z,a为当前输入字符 终止状态方式接受:当PDA以终止状态接受语言L(M)时,有: 空栈方式接受:当PDA以空栈接受语言Lφ(M)时,有: L(M)={w (q0,w,Z0) (q,ε,α),且 q∈F,α∈Γ*} * 注意:ε表示此时w恰好被读完,q∈F表示此时也恰好进入终止状态。 Lφ(M)={w (q0,w,Z0) (q,ε,ε),且 q是Q中的任意状态} * 注意:这里第一个ε表示此时w恰好被读完;第二个ε表示此时栈恰好为空。 这里q是任意状态,说明空栈接受时对终止状态没有要求,因此可以认为终止状态集F为空集Ф。 一、有关概念 2、不确定的下推自动机 实例: 构造一个PDA M,能够接受语言L(M)={anbnn≥1}。 设 PDA M=(Q , T , Γ,δ, q0 , Z0 , F),其中: Q={q0,q1,q2} , T={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,ε)} 。 采用终止状态接收方式 一、有关概念 2、不确定的下推自动机 实例: 构造一个PDA M,能够接受语言L(M)={anbnn≥1}。 设 PDA M=(Q , T , Γ,δ, q0 , Z0 , F),其中: Q={q0,q1,q2} , T={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,ε)} 。 在q1状态下,读入字符a时,用aa替代栈顶元素a,状态保持不变(即在状态q1下,用栈来记录a的个数,将所有的a压入栈中)。 一、有关概念 2、不确定的下推自动机 实例: 构造一个PDA M,能够接受语言L(M)={anbnn≥1}。 设 PDA M=(Q , T , Γ,δ, q0 , Z0 , F),其中: Q={q0,q1,q2} , T={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,ε)} 。 此处ε表示弹出栈顶元素a,即以空元素替代栈顶元素a(也既输入的第一个字符b应与栈顶的a相匹配,故弹出该字符a,同时进入状态q2) 一、有关概念 2、不确定的下推自动机 实例: 构造一个PDA M,能够接受语言L(M)={anbnn≥1}。 设 PDA M=(Q , T , Γ,δ, q0 , Z0 , F),其中: Q={q0,q1,q2} , T={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,ε)} 。 一旦进入q2状态后,就只接受字符b,且每读入一个b字符都应与栈顶的一个a字符相匹配,故从栈中弹出该字符a 。 一、有关概念 2、不确定的下推自动机 实例: 构造一个PDA M,能够接受语言L(M)={anbnn≥1}。 设 PDA M=(Q , T , Γ,δ, q0 , Z0 , F),其中: Q={q0,q1,q2} , T={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,ε)} 。 在q2状态下,一旦遇见栈底元素Z0,且此时剩余输入串恰好为空串,则弹出Z0使栈为空,同时进入终止状态q0从而以终止状态接受输入字符串。 一、有关概念 2、不确定的下推自动机 实例: 构造一个PDA M,能够接受语言L(M)={anbnn≥1}。 设 PDA M=(Q , T , Γ,δ, q0 , Z0 , F),其中: Q={q0,q1,q2} , T={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,ε)} 。 PDA M的状态转换图如右: q0 q1 q2 a, Z0/aZ0 ε, Z0/ε b,a/ε b,a/ε a,a/aa 当输入字符串aaabbb时,M的工作过程是: (q0,aaabbb,Z0) (q1,aabbb,aZ0) (q1, abbb,aaZ0) (q1, bbb,aaaZ0) (q2, bb,aaZ0) (q2, b,aZ0) (q2,ε,Z0) (q0,ε,ε) 注意:在本例中,对于每一个格局的下一步(即后继格局)都只有一种选择,这样的PDA称为确定的下推自动机(DPDA) 一、有关概念 2、不确定的下推自动机 确定的下推自动机之定义: 下推自动机M=(Q,T,Γ,δ,q0,Z0,F),如果是确定的,必须满足以下两个条件之一: 对任意的q∈Q,Z∈Γ和a∈T,有: ① δ(q,a,Z)只含一个元素,且δ(q,ε,Z) =Ф(即函数值无定义); ② δ(q,a,Z)=Ф(函数值无定义),且δ(q,ε,Z) 只含一个元素。 注意1:上述定义中,“只含一个元素”保证了δ函数的“确定性”,同时①②避免了在同样的状态、同样的栈顶元素下,在读入一个符号时发生状态转移和在不读入字符时发生状态转移之间作选择的可能性。也即在任何一个格局状态下只有唯一的一个后继格局。 注意2:不满足条件①②的PDA 即为不确定的PDA。与有限自动机不同,不确定的PDA的描述能力强于确定的PDA的描述能力。也即某些确定的PDA不能描述的语言可以用不确定的PDA来描述。 即只有一个函数值 一、有关概念 2、不确定的下推自动机 实例: 构造一个DPDA M,能够接受语言L(M)={w c w w∈{a,b}*}。 解题思路: ~ (1) 从状态q0开始接受句子w,将输入保存到栈中,状态不变,直到读到中心标志c时转(2); (2) 当c到达时,将状态改变为q1,栈的内容不变,转(3); (3) 将读入元素与栈顶元素进行匹配运算,若匹配成功则状态q1保持不变,且弹出栈顶元素,直到栈空时将状态改变为qf。 在此例中:输入字符为b时,栈顶字符也为b时匹配成功;输入字符为a时,栈顶字符也为a时匹配成功;其它情况匹配失败。 保存w进栈: δ(q0,a,Z0)={(q0,aZ0)}, δ(q0,b,Z0)={(q0,bZ0)}, δ(q0,a,a)={(q0,aa)}, δ(q0,a,b)={(q0,ab)}, δ(q0,b,a)={(q0,ba)}, δ(q0,b,b)={(q0,bb)}, 遇到c进入q1:δ(q0,c,a)={(q1,a)}, δ(q0,c,b)={(q1,b)}, δ(q0,c,Z0)={(q1,Z0)}, 输入w与栈中w匹配,w退栈:δ(q1,a,a)={(q1,ε)}, δ(q1,b,b)={(q1,ε)}, 遇到栈底元素Z0,结束操作:δ(q1,ε, Z0)={(qf , ε)} 最后若输入字符正好输入完,栈中的字符也正好匹配完,则弹出栈底元素Z0并进入终止状态qf ~ 所求DPDA M=({q0,q1,qf},{a,b,c},{Z0,a,b},δ, q0 , Z0 ,{qf}) 实例: 构造一个DPDA M,能够接受语言L(M)={w c w w∈{a,b}*}。 解题思路: ~ (1) 从状态q0开始接受句子w,将输入保存到栈中,状态不变,直到读到中心标志c时转(2); (2) 当c到达时,将状态改变为q1,栈的内容不变,转(3); (3) 将读入元素与栈顶元素进行匹配运算,若匹配成功则状态q1保持不变,且弹出栈顶元素,直到栈空时将状态改变为qf 。 保存w进栈: δ(q0,a,Z0)={(q0,aZ0)}, δ(q0,b,Z0)={(q0,bZ0)}, δ(q0,a,a)={(q0,aa)}, δ(q0,a,b)={(q0,ab)}, δ(q0,b,a)={(q0,ba)}, δ(q0,b,b)={(q0,bb)}, 遇到c进入q1:δ(q0,c,a)={(q1,a)}, δ(q0,c,b)={(q1,b)}, δ(q0,c,Z0)={(q1,Z0)}, 输入w与栈中w匹配,w退栈:δ(q1,a,a)={(q1,ε)}, δ(q1,b,b)={(q1,ε)}, 遇到栈底元素Z0,结束操作:δ(q1,ε, Z0)={(qf , ε)} ~ 所求DPDA M=({q0,q1,qf},{a,b,c},{Z0,a,b},δ, q0 , Z0 ,{qf}) 实例: 构造一个DPDA M,能够接受语言L(M)={w c w w∈{a,b}*}。 解题思路: ~ (1) 从状态q0开始接受句子w,将输入保存到栈中,状态不变,直到读到中心标志c时转(2); (2) 当c到达时,将状态改变为q1,栈的内容不变,转(3); (3) 将读入元素与栈顶元素进行匹配运算,若匹配成功则状态q1保持不变,且弹出栈顶元素,直到栈空时将状态改变为qf 。 保存w进栈: δ(q0,a,Z0)={(q0,aZ0)}, δ(q0,b,Z0)={(q0,bZ0)}, δ(q0,a,a)={(q0,aa)}, δ(q0,a,b)={(q0,ab)}, δ(q0,b,a)={(q0,ba)}, δ(q0,b,b)={(q0,bb)}, 遇到c进入q1:δ(q0,c,a)={(q1,a)}, δ(q0,c,b)={(q1,b)}, δ(q0,c,Z0)={(q1,Z0)}, 输入w与栈中w匹配,w退栈:δ(q1,a,a)={(q1,ε)}, δ(q1,b,b)={(q1,ε)}, 遇到栈底元素Z0,结束操作:δ(q1,ε, Z0)={(qf , ε)} ~ 所求DPDA M=({q0,q1,qf},{a,b,c},{Z0,a,b},δ, q0 , Z0 ,{qf}) DPDA M的状态转换图如右图所示: 其中:Z= a或b q0 q1 qf a,Z/aZ b,Z/bZ a,a/ε b,b/ε c, Z/Z ε, Z0 /ε 一个不确定的PDA的实例: 构造一个NPDA M,能够接受语言L(M)={w w w∈{a,b}*}。 解题思路: ~ 该语言与上一个例子基本类似,区别在于中间缺少一个“c”。由此可见,把上例状态转换图中的“c,Z/Z”改为“ε,Z/Z”,从而引进了不确定性;同时,因为机器可以在任何时刻进入到q1状态开始进行“匹配”检测,故这样一个NPDA可以接受L(M)。 该NPDA M的工作过程如下图所示: q0 q1 qf a , Z/aZ b , Z/bZ a , a/ε b, b/ε ε, Z/Z ε, Z0 /ε 在q0状态下当栈顶元素为某个字符Z时(Z可以是a或b或Z0):即可以读入字符a或字符b使读头右移一位后进入状态q0,并将字符a或字符b压入栈顶;也可以读头不移动(当读完所有字符的一半内容时)而进入状态q1,且栈顶元素不变。 二、终止状态接受与空栈接受的可互换性 定理16:如果Lf是下推自动机Mf以终止状态方式接受的语言,则必存在一个下推自动机MФ以空栈方式接受的语言LФ,使LФ=Lf。 定理17:如果LФ是下推自动机MФ以空栈方式接受的语言,则必存在一个下推自动机Mf以终止状态方式接受的语言Lf,使Lf=LФ。 (证明略) (证明略) END RETURN

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

http://drpetermitoff.com/zhanxiatui/58.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有