资源描述:
《形式语言与自动机理论课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第6章下推自动机西北工业大学计算机学院康慕宁基本定义FA是处理RL的装置,类似的,人们希望能有一种处理CFL的装置。因为RL是CFL的一个子类,所以处理CFL的装置也应能够处理RL。因此,这种装置应该是FA的一种扩展,而FA是这种装置的一个特例。FA只能处理RL,无法处理CFL的原因在于RG的产生式都可化为A→aB的形式,其生成无穷语言的原理在于A→wA,所以不需要记录w,只要产生式个数有穷,就可以用FA来处理。CFG的产生式只能化为A→aBα的形式,其生成无穷语言的原理在于A→wAα,需要记录w和α之间
2、的对应关系,无法用有穷个状态来表示;因此,为FA扩充一个无限大的栈,这样用栈的状态和FA的状态合起来就可以表示无穷个状态。这种装置就是下推自动机。下推自动机的物理模型PDA接受的语言PDA举例接受语言L={wwT
3、w∈{0,1}*}的PDAM=({q0,q1,q2},{0,1},{A,B,Z0},δ,q0,Z0,{q2})δ(q0,0,Z0)={(q0,0Z0)}记下待匹配的0δ(q0,1,Z0)={(q0,1Z0)}记下待匹配的1δ(q0,0,0)={(q0,00),记下待匹配的0(q1,ε)}待匹配字
4、符为0,读到0,开始匹配过程δ(q0,0,1)={(q0,01)}记下待匹配的0δ(q0,1,0)={(q0,10)}记下待匹配的1δ(q0,1,1)={(q0,11),记下待匹配的1(q1,ε)}待匹配字符为1,读到1,开始匹配过程δ(q1,0,0)={(q1,ε)}待匹配字符为0,读到0,匹配δ(q1,1,1)={(q1,ε)}待匹配字符为1,读到1,匹配δ(q0,ε,Z0)={(q1,Z0)}接受εδ(q1,ε,Z0)={(q2,Z0)}遇到栈底标志,转终态PDA的图形表示δ(q0,0,Z0)={(
5、q0,0Z0)}δ(q0,1,Z0)={(q0,1Z0)}δ(q0,0,0)={(q0,00),(q1,ε)}δ(q0,0,1)={(q0,01)}δ(q0,1,0)={(q0,10)}δ(q0,1,1)={(q0,11),(q1,ε)}δ(q1,0,0)={(q1,ε)}δ(q1,1,1)={(q1,ε)}δ(q0,ε,Z0)={(q1,Z0)}δ(q1,ε,Z0)={(q2,Z0)}由CFG构造PDA的方法注意,对于GNF文法,构造PDA比前页的方法可更有效。例:根据GNF构造PDA构造与具有如下产生
6、式集合的GNFG等价的PDA。S→aT
7、a,T→aT
8、bT
9、a
10、b接受L(G)的PDA为M=({q},{a,b},{S,T},δ,q,S,φ),移动函数为:δ(q,a,S)={(q,T),(q,ε)}δ(q,a,T)={(q,T),(q,ε)}δ(q,b,T)={(q,T),(q,ε)}DeterministicPDA’sAPDAP=(Q,Σ,Γ,δ,q0,Z0,F)isdeterministiciff1.δ(q,a,X)isalwaysemptyorasingleton.2.Ifδ(q,a,X)isnon
11、empty,thenδ(q,,X)mustbeempty.Theorem6.17:IfLisregular,thenL=L(P)forsomeDPDAP.Proof:SinceLisregularthereisaDFAAs.t.L=L(A).LetA=(Q,Σ,δA,q0,F).WedefinetheDPDAP=(Q,Σ,{Z0},δP,q0,Z0,F),whereδP(q,a,Z0)={(δA(q,a),Z0)},forallp,q∈Q,anda∈Σ.Aneasyinduction(doit!)on
12、
13、w
14、gives(q0,w,Z0)
15、-*(p,,Z0)⇔A(q0,w)=pThetheoremthenfollows(why?)空栈接受的DPDAWhataboutDPDA’sthatacceptbynullstack?TheycanrecognizeonlyCFL’swiththeprefixproperty.AlanguageLhastheprefixpropertyiftherearenotwodistinctstringsinL,suchthatoneisaprefixoftheother.Exampl
16、e:Lwcwrhastheprefixproperty.Example:{0}∗doesnothavetheprefixproperty.Theorem6.19:LisN(P)forsomeDPDAPifandonlyifLhastheprefixpropertyandLisL(P’)forsomeDPDAP’.N(P)表示空栈接受PDAL(P’)为终态接受的PDADPDA与二义性文法•WehaveseenthatRegular⊆L