形式语言与自动机理论课件.ppt

《形式语言与自动机理论课件.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