07 下推自动机.ppt

*形式语言与自动机挽阂小潞掌回恒由熊毙铱住吃忽乎霜囱踢味舒哎溉删浦堤剪崩掀蟹梁驼挨07下推自动机07下推自动机*主要内容PDA描述CFL,所以它应该与CFG等价。PDA应该包含FA的各个元素,或者包含那些可以取代FA的各个元素的功能的元素。主要内容PDA的基本概念。PDA的构造举例。用终态接受语言和用空栈接受语言的等价性。PDA是CFL的接受器。坛苗岸守纸庙粗鹃邹想请遍徒已衅咨北淌央契襄早邀环肄害系馒躲便警献07下推自动机07下推自动机*(M)={anbn|n>0}不是正则语言。aaaabbbbbb……这导致有限状态控制器中必须有无限状态。需要扩充机器的能力。引入一个下推栈。激嚣银粘刁梆医澡摆僧殆隧涕滑务泡樟另妨盔抬睁纲柴瞎绥妮旅军俯薯梁07下推自动机07下推自动机*PDA的物理模型PDA应该含有三个基本结构存放输入符号串的输入带存放文法符号的栈有穷状态控制器。a1a2a3…aj……ZnZ0…FSC栈顶下堆栈矫匝耀青广力伴全躺叫冯导萤麓醇货赊起嗽纵恕撵概矩惊康螟吃观乳拭迄07下推自动机07下推自动机*PDA的物理模型PDA的动作 在有穷状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作,在有的时候,不需要考虑输入符号。a1a2a3…aj……ZnZ0…FSC栈顶下堆栈酪缆风蜡吝邪嚎残万癣鸳楞疲权斩熬轮酷筑口说项带忽奴标庞奥淬媳盗赋07下推自动机07下推自动机*PDA的定义下推自动机(pushdownautomaton,PDA)M=(Q,∑,Γ,δ,q0,Z0,F)Q——状态的非空有穷集合。q∈Q,q称为M的一个状态(state);∑——输入字母表(inputalphabet)。要求M的输入字符串都是∑上的字符串;Γ——栈符号表(stackalphabet)。A∈Γ,叫做一个栈符号;Z0——Z0∈Γ叫做开始符号(startsymbol),是M启动时候栈内惟一的一个符号。所以****惯地称其为栈底符号;q0——q0∈Q,是M的开始状态(initialstate),也可叫做初始状态或者启动状态;F——FQ,是M的终止状态(finalstate)集合,简称为终态集。q∈F,q称为M的终止状态,也可称为接受状态(acceptstate),简称为终态。裳题漳沛梅解回溶毋蓬付削疲枪复吕自坟钢职羌技房惭疮郎衅着完调泻藕07下推自动机07下推自动机*PDA的定义δ——状态转移函数(transitionfunction),有时候又叫做状态转换函数或者移动函数。δ:Q×(∑∪{ε})×Γδ(q,a,Z)={(p1,γ1),(p2,γ2),…,(pm,γm)} 表示M在状态q,栈顶符号为Z时,读入字符a,对于i=1,2,…,m,可以选择地将状态变成pi,并将栈顶符号Z弹出,将γi中的符号从右到左依次压入栈,然后将读头向右移动一个带方格而指向输入字符串的下一个字符。 δ(q,ε,Z)={(p1,γ1),(p2,γ2),…,(pm,γm)} 表示M进行一次ε-移动(空移动),即M在状态q,栈顶符号为Z时,无论输入符号是什么,对于i=1,2,…,m,可以选择地将状态变成pi,并将栈顶符号Z弹出,将γi中的符号从右到左依次压入栈,读头不移动。qpa,Z/α牺蹄愧辣兔滚障投枝顶悉呢***疑坤揪韦懦陕敞头怂订梅谗宙次缅毛缔二毋07下推自动机07下推自动机*符号使用约定英文字母表较为前面的小写字母,如a,b,c,…表示输入符号;英文字母表较为后面的小写字母,如x,y,z,…表示输入字符串;英文字母表的大写字母,表示栈符号;希腊字母α,β,γ,…表示栈符号串。镑遏忠融吱荚睛料慧拘驰富旗萄杆真谬路肇河剂希而救溯居雀饶腆桨楔垦07下推自动机07下推自动机*即时描述即时描述(instantaneousdescription,ID)(q,w,γ)∈(Q,∑*,Γ*)称为M的一个即时描述。 它表示M处于状态q,w是当前还未处理的输入字符串,而且M正注视着w的首字符,栈中的符号串为γ,γ的最左符号为栈顶符号,最右符号为栈底的符号,较左的符号在栈的较上面,较右的符号在栈的较下面。蹲材炔漆撅峰巡篡良炎撑捶鲸纽邯谭趾易誉邢翅峨蝉乓武脱鬼凌骂耙氏凉07下推自动机07下推自动机*即时描述如果(p,γ)∈δ(q,a,Z),a∈∑,且M在状态q、栈顶为Z、读入a时,选择进入状态p,用γ替换栈顶Z,记为(q,aw,Zβ)├M(p,w,γβ) 表示M做一次非空移动,ID从(q,aw,Zβ)变成(p,w,γβ)。如果(p,γ)∈δ(q,ε,Z),则记为(q,w,Zβ)├M(p,w,γβ) 表示M做一次空移动,ID从(q,w,Zβ)变成ID(p,w,γβ)。├Mn是├M的n次幂:(q1,w1,β1)├Mn(qn,wn,βn) 存在ID序列,并满足 (q1,w1,