大学精品课件：模式识别pattern recognition c-7.ppt

1、 句法模式识别句法模式识别 第七章第七章遥感信息工程学院1 7.1、形式语言基础和文法 7.2、一维及高维文法 7.3、基元提取和文法推断 7.4、句法分析 7.5、自动机识别 第七章第七章 句法模式识别句法模式识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院2n概述：概述：结构模式识别：结构模式识别：从模式的结构关系入手对模式进行分析是一个十分重要的方法，统计模式识别方法是不能完成这一任务的，因为它注重的只是模式的数值特征，孤立地分析每一个模式，仅仅对其量的特征进行辨别。能够进行结构分析的是句法模式识别方法，它是由模仿语言学中句法的层次结构而产生的一种方法。基本思想：基本思想：对

2、模式内部具有的结构特征进行分析和表示，并且将这些结构特征和已知类别中的结构特征进行比较，就可以分辨给定的模式从结构类似的意义上应该属于哪个类别。具体而言：将复杂模式分解为若干较简单的子模式的组合，而子模式又分为可以由更简单的子模式来描述，最简单的子模式称为模式基元。通过对模式基元的识别，进而识别子模式，最终识别该复杂模式。第七章第七章 句法模式识别句法模式识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院3n因此，有必要对模式内部具有的结构特征进行分析和表示，并且将这些结构特征和已知类别中的结构特征进行比较，就可以分辨给定的模式从结构类似的意义上应该属于哪个类别。这就是结构模式识别的

3、基本思想。怎么来表达模式的结构呢？下面我们会看到，结构的分析方式和自然语言的分析方式类似，因此也将结构模式识别称为句法模式识别。句法模式识别句法模式识别 第七章第七章遥感信息工程学院4 模式描述语言：模式描述语言：描述模式结构的语言。包括模式基元和对基元的合成操作规则。模式文法：模式文法：对基元作合成操作以构成模式的规则。多级树描述结构：多级树描述结构：地板地板M M墙壁墙壁N NL LT TB BD DE EX XZ ZY Y景物景物:A 景物景物A A物体物体B B背景背景C C三角体三角体D D长方体长方体E E三角形三角形T T面面L L面面Y Y地板地板M M墙壁墙壁N N面面Z Z

4、面面X X第七章第七章 句法模式识别句法模式识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院5结构模式识别系统框图结构模式识别系统框图：图像图像输入输入预处理预处理分割分割描述描述基元基元提取提取句法句法分析分析分类决策分类决策模式表示模式表示识别识别分析分析训练样本训练样本基元选择基元选择句法句法推断推断句法句法分析分析改进改进句法句法规则规则第七章第七章 句法模式识别句法模式识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院6n 所谓形式语言是一种抽象语言，它是从人类的自然语言，计算机使用的各种语言，数学中的公式语言等等中抽象概括出来的。形式语言的理论是句法模式识别的

5、基础。7.1、形式语言基础和文法一、基本概念一、基本概念1、字母表、字母表：与所研究的问题有关的符号集合。例：V1=A,B,C,D,V2=a,b,c,d2、句子句子(链链)：由字母表中的符号所组成的有限长度的符号串。3、句子、句子(链链)的长度的长度：所包含的符号数目。例:|a3b3c3|=94、语言语言：由字母表中的符号组成的句子集合，用L表示。例：字母表V=a,bL1=ab,aab,abab 有限语言 L2=anbm|n,m=0,1,2.无限语言5、文法、文法：在一种语言中，构成句子所必须遵循的规则的集合，用G表示。L(G)表示由文法G构成的语言。句法模式识别句法模式识别 第七章第七章遥感

6、信息工程学院76、V*:由字母表V中的符号组成的所有句子的集合，包括空句子在内。例：V*,01,0017、V:不包括空句子在内的句子集合，即VV*()8、VT:终止符，不能再分割的最简基元的集合，用小写字母 表示。VT=a,b,c9、VN:非终止符，由基元组成的子模式和句子的集合。用大 写字母表示。VN=A,B,C VT，VN的关系：VTVN=(空集)VT VN=V（全部字母表）10、产生式、产生式(再写规则再写规则)P：存在于终止符和非终止符间的关系式。例：，VN，VN,VT.11、文法的数学定义文法的数学定义：它是一个四元式，由四个参数构成。G=VN,VT,P,S 7.1、形式语言基础和文

7、法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院8 二二.短语结构文法短语结构文法 1.0型文法（无限制）型文法（无限制）设文法G=(VN,VT,P,S)VN：非终止符，用大写字母表示 VT：终止符，用小写字符表示 P：产生式 S：起始符产生式P：，其中V+，V*，无任何限制 (V+不包括空符号串,V*包括空符号串)例：0型文法 G=(VN,VT,P,S)VN=S,A,B VP=a,b,cP:SaAbc AbbA AcBbcc bBBb aBaaA aB(空符号串)7.1、形式语言基础和文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院9SAabcabAcabBbccaBb

8、bcc bbcc 此文法可以产生：X=anbn+2cn+2 n0 X|n=0=bbcc由0型文法产生的语言称为0型语言。2.1型文法（上下文有关文法）型文法（上下文有关文法）设文法G=(VN,VT,P,S)产生式P：1A212 其中AVN，V+,1,2V*|1A2|12|,或|A|B|由上下文有关文法构成的语言称为上下文有关语言，用L(G1)表示，G1：上下文有关文法 7.1、形式语言基础和文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院10例：G=(VN,VT,P,S)VN=S,B,C VT=a,b,cP:SaSBC CBBC SabC bBbb bCbc cCcc1S21aSB

9、C2,bBbb对于SaSBC 1=,2=,A=S,B=aSBC,并且|S|0 解：G=(VN,VT,P,S)VT=(0,1)P:S0B B0B B1S B0 VN=(S,B)7.1、形式语言基础和文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院16四种文法的关系四种文法的关系:3型2型1型0型包含关系：限制不严格的文法必然包含限制严格的文法。7.1、形式语言基础和文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院17一一、串文法、串文法 1、定义：以字符串来描述模式，这样的文法常称为串文法。串文法是一种一维文法，也称为链文法。串文法被定义为四元组：G=(VN,VT,P,S

10、)VN：非终止符，用大写字母表示 VT：终止符，用小写字符表示 P：产生式(产生式P：)S：起始符2、应用实例：1964年Ledley等在自动处理染色体分类过程中提出的描述终端着丝点染色体和亚中央着丝点染色体的上下文无关文法。7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院18 顺时针跟踪染色体的边界，得到由基元连结而成的串，如亚中央着丝点染色体可以描述为babcbabdacadbabcbabdacad。染色体文法是 ，其中 SPVVGTN,AASbCCSSeBSSPedcbaVFEDCBASSSVTN12121,:,DcFBbBCDEbBBaDFDADbDDEA

11、bDDACAdCCAAbCBASCbC,2(1)染色体文法基元(2)亚中央着丝点染色体(3)终端着丝点染色体 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院19 区分不同的染色体，首先对它们进行轮廓扫描，自动形成由模式基元 所构成的不同的串。然后用上述文法G来检验，若某一个字符串可以由从第一个生成式 开始的推导得到，则该字符串表示亚中央着丝点染色体。若是由 开始推导得到的句子，则表示终端着丝点染色体。描述终端着丝点染色体的句子的最左推导如下：edcba,1SS 2SS ebabcbabebabcbDbebabcbDebabcDebabEebDbEebDEebAB

12、bABASS2 7.2、一维及高维文法 DcFBbBCDEbBBaDFDADbDDEAbDDACAdCCAAbCBASCbCAASbCCSSeBSSP,:2121 句法模式识别句法模式识别 第七章第七章遥感信息工程学院20二二、图象描述语言图象描述语言PDL（Picture Description LanguagePicture Description Language）串文法中字符串的连结只能表示基元的单向连结，不能表示基元同时在几个方向与其它基元的连结，也就是说，它只能表示一维连结方式，不能满足描述复杂图形的要求。为此，需要有高维文法。PDL语言就具有这种功能。1970年，Show提出图像

13、描述语言，任何图象都可用头尾来表示。PDL的基元是由两点（称为“头”和“尾”）构成的矢量，它可组成任意一个n维结构的图形。这是一种用于模式识别比较成功的语言。ht基元 a,b头头尾尾 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院21 连接规则：定义了四种二元连接算子1.a+b2.a x b3.a b4.a*ba头与b尾相连a尾与b尾相连,形成两个头a头与b头相连，形成一头二尾a头连b头,a尾连b尾，形成一头一尾一元算子htahta 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院22例：文法G=(VN,VT,P,S)VT=,(),

14、+,-,x,*,VN=S,A,B,C P:SA SB A(b+(C+c)B(d+(a+(d)*C),C(b+c)*a)ab cd 一个基元的头或尾可以与另一基元的头或尾相连而成为模式串，并可设置一些较复杂的联结关系和进行各种运算。7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院23L(G)=(b+(b+c)*a)+c);(d+(a+(d)*(b+c)*a)bcaaddbbccaCBSdb+导出过程da+c*aSAb+c+Cb+c*a 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院24 求表达式的规则：n 脱括号由内往外的次序进行，无

15、括号由左向右进行n 对于连接基元组成基元结构，必须符合规定的连接 点头，尾数目例：给出一个PDL文法G=(S,A,B,C,D,E,a ,b ,d,(,),+,*,P,S)P:S(A+(B)B(C)+D D b E(a+b)A d C E*c D (d)A ac 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院25可以导出手写大写字符“A”的四种表达式 S(A+(B)(a+(B)(a+(C)+D)(a+(E*c)+D)(a+(a+b)*c)+D)(a+(a+b)*c)+(d)(d+(a+b)*c)+b),(a+(a+b)*c)+b),(d+(a+b)*c)+(d)a

16、dbbaabbbaddcdaabc 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院26标准形式文法标准形式文法*在句法分析和自动机的一些算法中，有时要求标准化文法，下面介绍二种标准文法。1.乔姆斯基(Chomsky)范式,一种上下文无关文法如果它的每个 产生式P都符合二种形式：ABC(A,B,CVN)或Aa(AVN,aVT)该文法称Chomsky范式 已知上下文无关文法 G=(VN,VT,P,S)用以下步骤产生Chomsky范式的等价文法 G=(VN,VT,S)若中已经是ABC，Aa形式放入 中中其它的产生式形式为A 12.n 其中iVN或 iVTPP 句法模式

17、识别句法模式识别 第七章第七章遥感信息工程学院27用下面的产生式集合代替：AY1Y2.n Y2.nY2Y3.n Yn-1.nYn,n-1 YiVN若i VN,则令Yi=i；若i VT,再引入Yii 句法模式识别句法模式识别 第七章第七章遥感信息工程学院28例：把文法G=(VN,VT,P,S)变成Chomsky范式 VN=S,A,B VP=a,bP:SAB，Aa,AabABa，Bb 把SAB，Aa,Bb放入 中AabABa，A12345，其中1=5=a,2=b,3=A,4=BAY1Y2345,Y2345Y2Y345,Y345Y3Y45,Y45Y4Y5,3,4VN Y345AY45,Y45BY5,

18、125VT引入新的产生式，Y1a,Y2b,Y5a P 句法模式识别句法模式识别 第七章第七章遥感信息工程学院29符合chomsky范式文法，文法G2=(VN,VT,S)VN=Y1Y2345,Y2Y345,Y45,Y5,S,A,B AY1Y2345,Y1a,Y2345Y2Y345,Y2b,Y345AY45,Y45BY5,Y5a,SBA,Aa,Bb若x=bababa用G1导出：SBAbAbabABabababa,用G2导出：SBAb Y1Y2345.baY2345 baY2Y345 babY345 babAY45 babaY5 bababY5 bababa用原文法G1 只用四步可以导出bababa

19、而用标准文法G2则用九步才导出P 句法模式识别句法模式识别 第七章第七章遥感信息工程学院302.格雷巴赫范式格雷巴赫范式(Greibach)若一个上下文无关文法具有P形式：Aa,AVN,aVT,VN*(带空格)则此文法称为Greibach范式。例：上下文无关文法 G=(VN,VT,P,S)VN=S,C,VT=a,b,cP形式：SaCbb,CaCbb Cc变成Greibach范式：Cc即Cc符合Greibach范式，不变SaCbb,用SaCBB,Bb代替CaCbb,用CaCBB,Bb代替符合Greibach范式：P:SaCBB,CaCBB,Cc,Bb,句法模式识别句法模式识别 第七章第七章遥感信

20、息工程学院31三三、树文法、树文法 树文法也是一种高维文法，它是以树的杆、枝、根、叶结构形式来直观地描述基元的多向性联系和结构，表现多维结构特点的文法。1.1.树文法的定义：树文法的定义：定义：四元组 Gt=(v,r,P,S)其中V=VNVT，r:秩(一个节点的直接分支数)P形式：TiTj Ti,Tj都是树由Gt产生的语言叫树语言。L(Gt)=T|TT,TiT TiS,T是带有VT中结点的树集合Gt 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院32 扩展树文法扩展树文法：全部产生式形式Xxx1,x2 xn其中x1,x2.xnVN,xVT，nr(x)具有上面产生

21、式形式的树文法称扩展的树文法。2.2.应用举例：应用举例：例1：Gt=(v,r,P,S)V=VNVT（S,A,B,K,a,b）VT(,),r(a)=(2,0),r(b)=(2,0),r(k)=2ab 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院33 P:SK Aa Bb Aa Bb SK ABABABABababkABSKabABABabk导出树导出图bbaa 7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院34例2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用 树文法来描述。树文法Gt=(v,r,P,S)，VN（S,A,B）

22、，VT(a,b)基本定义：ab(凸弧)(凹弧)S a|S S a A BS a A BBA S a A BBA A BA a|AA a B a|BB a P:7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院35r(a)=(0,1,2,4,6),r(b)=(0,1)射线导出树：S a a a a a a a a a a a a a a a a a a a bbbbb bbbb bbbbaab射线图：7.2、一维及高维文法 句法模式识别句法模式识别 第七章第七章遥感信息工程学院36一、基元提取、基元提取 基元是句法模式识别的基础。它对应于文法中的终止符，是构成句子的最

23、基本单位。1 1、基元的选择：、基元的选择：基元的选择需要根据识别对象的具体情况、模式的性质以及实现识别系统所具备的技术等因素而定。建议：1）所选取的基元应是精简的，以易于语法描述与分析。2）能用非语言学的方法方便地抽取。例如：语音识别音素 文字识别笔划 图形基元的选择有两个途径，一是基于图形边界（或轮廓线）或骨架的分析，二是基于组成图形的基本组成区域。7.3、基元提取和文法推断 句法模式识别句法模式识别 第七章第七章遥感信息工程学院37 基于图形边界或骨架，是将各类图形的边界线或脊线分解成直线段或弧线段。比如染色体。按图形的区域提取基元的方法，是将图形近似地（因为许多图形的边界不一定是直线）

24、，看成一个大的多边形，这个大多边形可以分割成许多小的凸多边形，那么我们将凸多边形作为基元。2 2、基元提取：、基元提取：1）骨架法 2）边界提取法 3）区域分割法 7.3、基元提取和文法推断 句法模式识别句法模式识别 第七章第七章遥感信息工程学院38二、文法推断二、文法推断 基元是句法模式识别的基础。它对应于文法中的终止符，是构成句子的最基本单位。在确定了基元之后，需要将已知的各类样本集作为学习的基础，分析、归纳出各类模式的文法，根据各类模式的文法进行分类。这就是所谓的文法推断。7.3、基元提取和文法推断 假定已知某类模式的文法G，则生成的语言为 ，即由这一文法G所产生的句子一定是终止符所组成

25、的所 有 字 符 串 的 一 部 分，而 不 是 全 部。比如 ，其中TVGL)(SPVVGTN,BASVN,baVT,bBbBBaBAaASP,:句法模式识别句法模式识别 第七章第七章遥感信息工程学院39文法推断就是根据样本集 推导出文法G。这就如同统计模式识别中提供样本集以作训练时，每一类的样本不一定绝对纯一样。,3,2,1;,3,2,1;,)(nmVbabaGLTnm,aaabbaaabbaVTTV)()(GLVGLT)(;,2,1)(;,2,1GLxljxRGLxkixRjjiiRRR则：而：将 中不属于L（G）的字符串子集定义为：如果提供学习用的字符串集是R，它可能包括两部分，即 但

26、有时为了简化，令 为空集，仅用正样本集 去推导文法G，使 。RR RGL)(句法模式识别句法模式识别 第七章第七章遥感信息工程学院40文法推断有几种方法，现以一种启发式的归纳推断方法为例推导文法。设 为具有共同句法结构的模式样本集，借助基元和符号串中典型的谓词结构（即子串结构，如对于字符串abc,ab是它的一个子串，ab结构称为一个谓词结构），逐步推导出适合该样本集的文法。其步骤是：nxxx,21ixi）对于每个样本 ，按基元找出谓词结构，每一谓词结构相当于一个新的子模式，写出相应的生成式。按一定的规律描述出一个个子模式，直到不能形成新的谓词为止。ii）写出形成模式的全部可能的生成式，然后检查

27、哪些生成式所描述的子模式的组成部分包括了样本集的所有基元，保留这些生成式，抛弃不属于这个生成式集合的生成式。7.3、基元提取和文法推断 句法模式识别句法模式识别 第七章第七章遥感信息工程学院41iii）按上述方式逐个作出对 进行描述的 ，即描述串 ，取全部 组成G：iv）将G进行简化，合并重复的生成式和非终止符，构成最 简化的文法。ixiG2211,GxGx用描述用iGiniGUG1例：例：样本集cbaVcbbbbcabbbabcaabbbaabcaaabRT,这里典型的谓词结构就是基元字符的简单连接。据此写出 中每一句子的文法。其生成式分别如下：RabCaCBaBAcASPGcaaabx,:

28、,111的生成式文法对 7.3、基元提取和文法推断 句法模式识别句法模式识别 第七章第七章遥感信息工程学院42cbSPGcbxbbbSPGbbbxabIcISPGcabxabHbbHSPGbbabxabGaGFcFSPGcaabxabEaEDbbDSPGbbaabx:,:,:,:,:,:,777666555444333222的生成式文法对的生成式文法对的生成式文法对的生成式文法对的生成式文法对的生成式文法对 7.3、基元提取和文法推断 句法模式识别句法模式识别 第七章第七章遥感信息工程学院43合并全部生成式，去掉重复式，分以下几步进行：1）将非终止符C、E、G、H、I合并为C，得：cbSbbb

29、SaCFbbCScCScFSaCDbbDSabCaCBaBAcAS,2）再将B、D、F合并成B，得：cbSbbbSbbCScCScBSbbBSabCaCBaBAcAS,3）引入 生成式，以与其它生成式配合代替 ，即：bB cbSbbbScCS和,bBcBScbSbBbbBSbbbSbBaBAcAScCS,7.3、基元提取和文法推断 句法模式识别句法模式识别 第七章第七章遥感信息工程学院444）进一步将具有相同作用的生成式和非终止符合并或取代，生成 的规则为：bBbbCScBSbbBSabCaCBaBAcAS,RbAaAAbbAAcAS,代入原生成式，去掉重复式，得：7.3、基元提取和文法推断

30、句法模式识别句法模式识别 第七章第七章遥感信息工程学院45n各类模式的文法产生之后，就可以进行识别分类。对任一待识别的模式x，逐一用各类模式的文法 来进行识别，如果某一文法Gi可以生成x，则 ，它就应属于 。根据文法进行句法模式识别一般有两种方法，一种称为句法分析句法分析，一种采用自动机自动机作为识别器。7-4 句法分析mGGG,21)(iGLxi一，句法分析：设给定训练样本为M类即：1,2,M 每类有N个样本，如1的训练样本为：S=(X1,X2,XN)T由这些样本可以推断出1类的文法G1,同样方法可推断出2类的文法G2,.M类的文法GM.对待识别句子X进行句法分析，若X属于由文法Gi构成的语

31、言L(Gi)，则xi 类。框图如下：句法模式识别句法模式识别 第七章第七章遥感信息工程学院46XLG1 G1XLG2 G2XLGM GMx判决Xi句法分析过程识别结果待识别句子7-4 句法分析 句法模式识别句法模式识别 第七章第七章遥感信息工程学院47句法分析的主要方法：句法分析的主要方法：1，参考匹配法：2，状态图法：适用于有限状态文法 例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B,C）P:S1A,S0B,S1C,A0A,A0 B0,C0C,C0,C1BX样本链码X1 XLG2 xX样本链码X2 X样本链码XN 判决XiXXi7-4 句法分析 句法模式识别句法模式识别 第

32、七章第七章遥感信息工程学院48SCBAT1100010由状态图可以知道此文法可以识别的句子X1=10n+1,X2=00,X3=10n10,X4=10n+1未知句子：由状态图可知x1=10010(可以识别)x2=10110(不可以识别)00状态图7-4 句法分析 句法模式识别句法模式识别 第七章第七章遥感信息工程学院493，填充树图法(适用于上下文无关文法)：当给定某待识别链X及相应的文法G时，我们建立一个以X为底，S为顶的三角形，按文法G的产生式来填充此三角形，使之成为一个分折树。若填充成功表明 否则填充树有二种方法由顶向底剖析由底向顶剖析填充树图法在填充三角形时应遵守三条原则：首位考察：首先

33、考虑选用某个产生式后能导出X的第一个字符用某产生式后，不能出现X中不包含的终止符用某产生式后，不能导致符号串变长(变短)(GLX)(GLX SX7-4 句法分析 句法模式识别句法模式识别 第七章第七章遥感信息工程学院50由顶向底(由上而下)剖析例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B）P:S1 SB1 SB B1A BB1A A0A A0设：X=1000，用由上而下剖析方法判断X是否属于L(G)BB10AASBS1ASA00 X=1000L(G)7-4 句法分析 句法模式识别句法模式识别 第七章第七章遥感信息工程学院51由底向顶(由下而上)剖析例：G=(VN,VT,P,

34、S)VT=（a,b,c,f,g）VN=（S,T,I）P:ST Ia STfs Ib TIgT Ic TI 设：X=afbgc用Ia 用TI用Ib用Ic用TIa f b g cIa f b g cITa f b g cITIa f b g cITIIa f b g cITIIT7-4 句法分析 句法模式识别句法模式识别 第七章第七章遥感信息工程学院52a f b g cITIITTa f b g cITIITT Sa f b g cITIITTS用TIgT用ST用STfSS X=afbgc L(G)7-4 句法分析 句法模式识别句法模式识别 第七章第七章遥感信息工程学院53三、杨格(Younge

35、r)法*Younger法是个较前述各方法更系统的方法，适用于任何相应于2型文法类别的识别。下面结合一例说明此方法。设有一代表类别的文法G=(VN,VT,P,S)其中 VT=（0,1,2）VN=（S,B）P:SSBS BBB BBS S2 B0 B1现在要用Younger法来识别X=202102是否G.首先将上述文法化为Chomsky标准形式。此形式文法的代换式只有两种形式，即 非终止符非终止符非终止符（双非终止符形式）非终止符终止符（终止符形式）句法模式识别句法模式识别 第七章第七章遥感信息工程学院54将式上所示文法中第1条改为SSA，ABS两条（A为人为增加的非终止符），使整个文法成为：SS

36、A ABS BBB BBS S2 B0 B1 而令VT=（0,1,2）VN=（S,A,B）便完成了Chomsky形式的转化。Younger法将对Chomsky形式文法进行分析。待识别符号串的任一“子串”都可用i,j两个整数来指明：所谓子串即把一符号串任一截取一段，这段符号串（包括单个符号）就叫原来符号的子串。譬如符号串202102的子串就有2，0，2，1，0，2（个数为1的子串）；20，02，21，10，02（个数为2的子串）；202，021，210，102（个数为3的子串）；2021，0210，2102（个数为4的子串）；20210，02102（个数为5的子串）和202102（个数为6的子串

37、即原符号串）。句法模式识别句法模式识别 第七章第七章遥感信息工程学院55这21个符号串都可由正整数i,j表示。i代表子串中符号的个数（即子串长度），而j表示这子串的首位在原符号串中占第几位。如上面所举的第1子串“2”，即为i=1、j=1的子串，第13个子串021即是i=3、j=2的子串。可见，任一子串都可用i,j二数来指明。识别表的建立，关键问题是根据给出的待识别串X,建立一识别表。对于202102,根据所给出的文法算得的识别表如下：句法模式识别句法模式识别 第七章第七章遥感信息工程学院56 i 1 2 3 j 1 2 3 4 5 6 1 2 3 4 5 1 2 3 4 所有子串所有子串 2

38、0 2 1 0 2 20 02 21 10 02 202 021 210 102 所所有有VN S A B 4 5 6 1 2 3 1 2 1 2021 0210 2102 20210 02102 202102 句法模式识别句法模式识别 第七章第七章遥感信息工程学院57表中每一位置由三个符号表示。头二个即i和j，而第三个是非终止符(现为S,A,B,见表中第一列).。i1栏中第2列(j=2)与B行相交的位置即为(1,2,B),余类推。表中(1,2,B)位置上有，代表对于所给文法，B可导出i=1,j=2的子串，即“0”。反之，若这位置上为，则说明B不能导生子串“0”。再举一例，第2栏中第2列、A行

39、位置应该用（2,2,A）表示，此位置上有，代表对于所给文法，B可导出I=2,j=2的子串，即“02”（见表）。（）经分析可知，能容易地根据给出的符号串(202102),在i=1栏的各位置上打 或，又根据此栏结果，由一递推公式将i=2栏各位置打上 或。如此递推下去便可将表填满，识别表也就建成。在识别时只需检查最后一栏(现为i=6栏)第一列第S行位置即(6,1,S)上是 还是。若是，表示S可导生子串202102，故判202102符合给出的文法。反之，即判不符合此文法。020SBSA 句法模式识别句法模式识别 第七章第七章遥感信息工程学院58 建立识别表的递推规则递推规则：将要决定 或 的位置表为(

40、i,j,k)通用形式。K代表非终止符。又将r(i,j,K)称为(i,j,k)位置的识别值。此值为0或1，分别表示(i,j,k)位置上是 或。计算r(i,j,K)(也即决定 或)的步骤是：(i)算出其中K1,K2代表KK1K2.例如：ABS,K=A,K1=B,K2=S.),1,1(),1(),2,2(),2(),1,1(),1(212121KijrKjirKjirKjrKjirKjr（1）句法模式识别句法模式识别 第七章第七章遥感信息工程学院59(ii)如果(i,j,k)左侧是K的代换式不只一个，譬如K是B时，即有BBB、BBS两个。这时则把B、B叫做K1、K2，根据它计算式(1)中各值；此外，

41、还需将B、S叫做K1、K2，再按下面式算出：对于所有i,j,k（包括题中各个非终止符），算出式(2)中的各值。只要其中之一值为1，便在相应当位置上打，否则打。如此便可填满整个识别表若左侧为K的代换式有三个，可按上述原则，再增加计算将(1)式中K1、K2改为K1、K2后的各值，余类推。),1,1(),1(),2,2(),2(),1,1(),1(212121KijrKjirKjirKjrKjirKjr 句法模式识别句法模式识别 第七章第七章遥感信息工程学院60现作为例子用递推规则考察(2,2,A)中的 或。由于左侧为A的代换式只有ABS一个，故此时对于(1)式只需计算r(1,2,B)r(1,3,S

42、)=1 1=1,即(2,2,A)应打。此结果与前面分析得到的相符。根据上述递推规则和给定的文法，容易编制计算机程序。当待识别串X进入时，按此算出识别表，并检查表中最后一列S位置上是 还是；若为，便判属于给定文法相应的类别，否则判为不属于此类别。句法模式识别句法模式识别 第七章第七章遥感信息工程学院61四四.CYK(Cocke-Younger-KasamiCYK(Cocke-Younger-Kasami)剖析剖析(列表法列表法)*条件：适用上下文无关文法 产生式应符合Chomsky范式已知输入串X=a1a2.an构造三角形剖析表步骤如下：令j=1,按从i=1到i=n次序，求ti1.把X分解为长度

43、为1的子串，对子串ai,若p中有Aai,把A填入ti1中令j=2,按从i=1到i=n-1次序，求ti2，即第二行。把X分解为长度为2的子串，对子串aiai+1,若p中有ABC,且有Bai,Cai+1则把A填入ti2中对于j2,1in,已求出tij-1,现求tij对于1kj中的任一k,当P中有ABC且B在tik中.C在ti+k,j-k中时，把A填入tij中重复直至完成此表，或整行都是空(拒识)当且仅当S在tin中，XL(G)，即由G可导出X分析一个长度为n的串，所用的存储量正比于n2,运算次数正比于n3。1 2 3 4 5 i54321tij剖析表j 句法模式识别句法模式识别 第七章第七章遥感信

44、息工程学院62例：G=(VN,VT,P,S)VT=（a,b）VN=（S,A,B,C）P:SAB SAC Aa Bb CSB 输入串：X=aabb=a1a2a3a4 所有产生式符合Chomsky范式令j=1,计算ti1，1i4i=1,a1=a,P中有Aa 有t11=(A)i=2,a2=a,P中有Aa 有t21=(A)i=3,a3=b,P中有Bb 有t31=(B)i=4,a4=b,P中有Bb 有t41=(B)第一次迭代，令j=2,计算ti2，1i3对于a1a2=aa,不能产生aa 有t21=对于a2a3=ab,SAB,Aa,Bb 有t22=(s)对于a3a4=bb,P中产生式不能产生bb 有t32

45、=()1 2 3 4 ij4321AABB S 句法模式识别句法模式识别 第七章第七章遥感信息工程学院63 第二次迭代，令j=3,计算ti3，1i2对于a1a2a3=aab,不能产生aab 有t13=对于a2a3a4=abb,CSB,Sab,Bb 有t23=(C)第三次迭代，令j=4,计算ti4，对于a1a2a3a4=aabb,SAC,Aa,Cabb 有t14=(S)t14=S X=aabb在L(G)中，此串被识别。4321AABB S1 2 3 4 iSC剖析表a a b bA A B BSSC导出树+此算法实际上是一个由底向顶剖析算法。句法模式识别句法模式识别 第七章第七章遥感信息工程学院

46、64引言：x当给出某类文法后，可根据它设计一种相应的称为自动机的硬件模型。它由控制装置、输入带和某些类型的存储器组成，这种硬件模型是一种识别器称自动机。不同的自动机可以识别不同的文法形成的语言。0型文法：图灵机识别上下文有关型：线性约束自动机上下文无关型：下推自动机有限状态型：有限状态自动机识别器XLG G7-5 自动机识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院65一、有限状态自动机有限状态自动机 可以识别由有限状态文法所构成的语言1、基本定义：五元式M系统 M=(,Q,q0,F)其中：输入符号的有限集合Q：状态的有限集合：状态转换函数是Q到Q的一种映射q0：初始状态 q0

47、Q F：终止状态集合2、有限自动机的结构 转换函数：(q,a)=p表示有限控制器处于q状态，而输入头读入符号a，则有限控制器转换到下一状态p。QF 输入带0110输入头有限状态控制器Qq0 q1.F7-5 自动机识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院663、自动机识别输入字符串的方式L(M)=x|(q0,x)在F中(q,x)拒识，停机4、自动机的状态转换图:表示自动机识别过程例：M=(,Q,q0,F)Q q0,q1,q2,q30,1F=q0(q0,0)=q2,(q0,1)=q1,(q1,0)=q3,(q1,1)=q0,(q2,0)=q0,(q2,1)=q3,(q3,0)=

48、q1,(q3,1)=q2q0q1q2q3111100007-5 自动机识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院67输入：x=110101q0 q1 q0 q2 q3 q1 q0F X可以识别(q0,110101)=q0 例：已知自动机状态转换图如下 x1=aab 可以识别 x2=abb 不可以识别110110abbaabq0qAqBq a,b可以识别的语言：L(G)=anbqB状态，只有出没有进，为不可到达状态 q状态，只有进没有出，为陷阱7-5 自动机识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院684、不确定的有限状态自动机即：(q,a)=q1,q2,qk

49、当输入a时，下一个状态可 能为多个状态之一。例：M=(,Q,q0,F)Q q0,q1,q2,q3,q40,1F=q2，q4(q0,0)=q0,q3,(q0,1)=q0,q1(q1,0)=(在q1不会输入0)(q1,1)=q2(q2,0)=q2,(q2,1)=q2,(q3,0)=q4,(q3,1)=(q4,0)=q4,(q4,1)=q47-5 自动机识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院69输入字串：010110 q0q3q1000，10，1110，1q4q2010110 输入字符串X=010110可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。状态转换图q0q

50、0q0q0q0q3q1q1q3q2Fq2F7-5 自动机识别 句法模式识别句法模式识别 第七章第七章遥感信息工程学院705、构造一个有限自动机定理1：设 G=(VN,VT,P,S)为有限状态文法，一定存在一个有限状态自动机M=(,Q,S,F)使L(G)=L(M).已知有限状态文法G=(VN,VT,P,S)由有限状态文法构造有限自动机的步骤：VT Q VNT q0=S 若P中有S，则F=(S,T),否则F=T 若P中有Ba，则(B,a)=T,BVN,aVT 若P中有BaC，则(B,a)=(C),B,CVN,aVT 对VT中所有的终止符a，都有(T,a)=,aVT 7-5 自动机识别 句法模式识别