模式识别讲义第二章.ppt

具有格雷巴赫范式的文法如果文法的每个产生式都是A→aα形式的，其中A是非终结符，a是终结符，α是在N*中，那么这个文法是格雷巴赫（Greibach）范式的令重写某一特定非终结符A的产生式的整个集合是{A→γ1，A→γ2，…，A→γn}；那么，G1中的形式为B→σAθ的任何产生式可以用产生式集{B→σγ1θ，B→σγ2θ，…，B→σγnθ}代替第29页,共44页，星期六，2024年，5月如果一种文法，其中至少存在一个非终结符A，对于(N∪∑)*中的γ，能使成立，那么称这个文法为右递归的。相似的，如果有一种文法，其中存在一个非终结符A，对(N∪∑)*中β的，能使成立，那么称这种文法为左递归的递归定义A=γA+A=Aβ+第30页,共44页，星期六，2024年，5月消除左递归把重写非终结符A的产生式集分为两个子集。第一个子集产生式的右面是以A本身开始的，如{A→Aγ1,A→Aγ2,…,A→Aγn}；第二个子集是那些右面不是从A开始的，如{A→α1,A→α2,…,A→αm}。从这些产生式导出的句形是在集合{α1,…,αm}{γ1,…,γn}*中（i）A→α1,A→α2,…,A→αm（ii）A→α1A’,A→α2A’,…,A→αmA’，其中A’是新的非终结符。（iii）A’→γ1，A’→γ2，…，A’→γn（iv）A’→γ1A’，A’→γ2A’，…，A’→γnA’第31页,共44页，星期六，2024年，5月格雷巴赫范式变换假设G1已经是乔姆斯基范式非终结符集记作{A1，A2，…，Am}，其中下标是任意分配的。调整产生式，以保证如果有Ai→Ajθ，则ji。我们按i=1，2，…，m增加的次序进行调整。每个产生式都是Ak+1→aα形式，或者Ak+1→A1α形式，其中a在∑中，α在N*中，以及l≥k+1对每个Ak+1→Ak+1α这样的产生式删除左递归第32页,共44页，星期六，2024年，5月习题假设文法G2=({S，A，B}，{a，b}，P，S)具有产生式{S→BA，A→a，A→abABa，B→b}。将其产生式转换格雷巴赫为范式，求其等价文法G2。第33页,共44页，星期六，2024年，5月下推自动机PDA下推自动机它可形式地定义为7元组：M=（∑,Q,Γ,δ,q0,Z0,F），其中Q、∑、q0及F和有限自动机中的定义相同。Γ是有穷下推字母表，δ是从Q×(∑U{λ})×Γ到Q×Γ*的有穷子集的映射，Z0在Γ中，是下推表的初始符。第34页,共44页，星期六，2024年，5月下推自动机的一般表示（带运动方向）输入带只读头有穷状态集Q下推自动机的一般表示读写头下推表机器开始运行时状态是q0堆栈上只有Z0输入带上包含来自∑+的串x，从左到右逐个地扫描串x的每个符号。δ映射规定下一个状态，以及规定Γ*中哪个串能代替堆栈顶上的单字符。如果机器从q0和堆栈顶上Z0开始，扫描全部x后停在F的一个状态上，则称串x被PDA接受了。第35页,共44页，星期六，2024年，5月下推自动机识别的语言L(M)={x|x在Σ+中，从状态q0及堆栈顶的Z0开始，扫描全部x后M停在F的一个状态上}。Lλ(M)={x|x在Σ+中，M从q0及Z0开始，扫描全部x后M停在空栈上}。第36页,共44页，星期六，2024年，5月下推自动机举例用空堆栈接受这些句子的PDA是个不确定的自动机M=（{a,b,c,d}，{q0}，{S,A,B,C,D},δ,q0,S,Φ），其中δ映射定义如下：δ(q0,c,S)={(q0,DAB),(q0,C)}，δ(q0,d,C)={(q0,λ)}δ(q0,a,D)={(q0,λ)}δ(q0,b,B)={(q0,λ)}δ(q0,a,A)={(q0,DAB),(q0,C)}识别的语言:{x|x=candbn，n≥0}第37页,共44页，星期六，2024年，5月上下文无关文法→下推自动机G=(N,Σ,P,S)是一个上下文无关文法。构造使L(G)=L(Ap)的下推自动机。我们定义M=({q0},Σ,N∪Σ,δ,q0,S,Φ)，按下述方式从产生式得到δ映射： （1）如果A→α在P中，则δ（q0,λ,A）包含(q0,α)；（2）对每个在Σ中的终结符a，有δ（q0,a,a）={(q0,λ)}第38页,共44页，星期六，2024年，5月习题G=({S,A}，{a,b,c,d}，P，S)，其中产生式为： {S→cA,A→aAb,A→d}。 请给出下推自