下推自动机与上下文无关文法的对应关系课件.ppt

1、6.1 句法模式识别概述句法模式识别概述6.2 形式语言的基本概念形式语言的基本概念6.3 模式的描述方法模式的描述方法6.4 文法推断文法推断6.5 句法分析句法分析6.6 句法结构的自动机识别句法结构的自动机识别第第6章章 句法模式识别句法模式识别6.1 句法模式识别概述句法模式识别概述模式用句子形式描述，结构信息十分重要。模式子模式基元句子词组单词组合关系自然语言的文法 句法模式识别用小而简单的基元与语法规则描述和识别大而复杂的模式，通过对基元的识别，进而识别子模式，最终识别复杂模式。符合某个文法的所有句子的集合一个模式类（b）墙壁 f地板 gEDBbadce（c）图6.1 景物结构描述

2、与英文句子句法描述的对比句法模式识别系统的组成：句法模式识别的理论基础：形式语言 20世纪50年代中期乔姆斯基（Chomsky）。*基元选择尚无通用的方法；*文法推断理论远不及统计学习发展得成熟。句法模式识别存在的主要问题：6.2 形式语言的基本概念形式语言的基本概念6.2.1 基本定义基本定义1字母表与问题有关的符号的有限集合，用V或表示。2句子 由字母表中符号组成的有限长度的符号串，又称链。空句用表示。组成：英文小写字母、数字。例：由 中元素可组成句子：,cbaV,1ZCBAV2,1,03V例：abc，aacc，重写次数句子的长度：句子包含符号的数目，用|表示。9|333cba3语言由字母

3、表中的符号根据某种文法组成的句子的集合。V*：V中符号组成的所有句子的集合，包括空句；V+：不包含空句的句子集合。*VV,*aabbccabV,aabbccabV例：4文法构成一种语言的句子所必须遵守的规则。),(SPVVGTNVN：非终止符的有限集，子模式的集合，大写字母表示。VT：终止符有限集，基元的集合，字母表起始部分的小写 字母表示。终止符和非终止符组成的混合字符串：用英文字母表尾部的小写字母x，y，v，w等表示。终止符组成的字符串：用希腊字母，等表示。性质：VVVTNTNVV（字母表）（空集）P：生成式的有限集。用文法产生句子时的重写规则。：P字符串 字符串 替换 S：起始符，代表模

4、式本身，特殊的非终止符。用生成式构成句子时，必须由左边是S的生成式开始。一种语言有一种文法，由文法G构成的语言用L(G)表示：,|)(*xSVxxGLGT且文法G构成的句子由终止符组成VT中字符组成的所有句子的集合 文法G的推导关系 aabccaaBccaaAccaAcS 利用文法构成句子时，除第一个生成式必须利用左边为起始符 S 的生成式外，其余生成式使用的先后次序及重复使用的次数都不受限制。是说明：解：6.2.2 文法分类文法分类四种类型：0型文法、1型文法、2型文法和3型文法。10型文法：型文法：无约束文法。P：其中，。V*V21型文法：型文法：上下文有关文法。含意：32型文法：型文法：

5、上下文无关文法。解：每个生成式的左边都是单变量，右边是非空字符串，故G是上下文无关文法。属于L(G)的句子：结果不唯一。43型文法：型文法：正则文法、有限态文法。是 后一种文法的限制比前一种文法的限制严格；限制愈多的文法愈容易推断；句法模式识别中多采用上下文无关文法和正则文法。6.3 模式的描述方法模式的描述方法6.3.1 基元的确定基元的确定根据结构特征对模式进行描述。结构描述法，又称句法表示法。模式的表示：链表示法、树表示法、图表示法。对应的文法：链文法（串文法）、树文法、图文法。还有网文法、阵列文法等。目前关于基元的确定没有一个通用的解决办法。基元的选择遵循两个基本原则。1基元应是模式的

6、基本单元，能够通过一定的结构关系对数 据进行紧凑、方便地描述。2基元应该容易用现有的非句法方法进行提取或识别。例如：语音识别中 音素；识别手写文字 笔划。6.3.2 模式的链表示法模式的链表示法1链码法链码法链码：用不同斜率的直线段或曲线段为基元表示图形模式。弗利曼链码：以八个基本方向的有向线段为基元，用07八个数字符号表示。用字符表示基元后，被描述的图形表示成的字符串。弗利曼链码基元 数字“2”的折线化和量化结果编码：矩形网格覆盖；折线化和量化；形成链码(有序结构)。例：“2”的链码表示为1075456000 x2图形描述语言法图形描述语言法简称PDL（Picture Description

7、 Language，PDL）。基本基元：有向线段(直线段、弧线段)。由“头(箭头端)”和“尾”构成。关系基元：表示基元之间连接关系的算子。头尾相接 头头相接 尾尾相接 头头 且尾尾相接头尾颠倒（）组合关系(配合使用)例：用PDL法表示大写英文字母A。(a+b)(a+b)*c)(a+b)*c)+b)(a+(a+b)*c)+b)链表示法：只能从左边或右边与其它符号相连，一维连接方式。6.3.3 模式的树表示法模式的树表示法高维表示法。1树的定义树的定义树T是一个或一个以上结点的有限集合，并且满足：1）存在一个唯一的指定为根的结点；2）其余结点分为m个不相交的集合T1，T2，Tm，其中 每一个集合本

8、身都是一个树，称为T的子树。同一层上各子树交换位置构成的树不同。树的有序性：一个结点具有子树的个数，结点a的秩记为 r(a)。叶结点的秩为零。秩：长方体 基元 树结构描述 结点a的秩可能是2，l或0。0,1,2)(ar例：结点a可能有2，1或0个分枝树文法定义为四元式),(SPrVGt2树文法树文法字母表 以字母表中字母为根结点的树的秩 起始树的有限集 VTS 生成式的有限集由树文法Gt产生的语言L(Gt)是一些树的集合即模式集：,|)(*STTTTTTGLitGiTt所有结点都是终止符的树的集合树T由S中的起始树Ti开始，用文法Gt的生成式逐步导出图6.7 模式的树状表示解：生成式 中右边的

9、树分别用T1，T2，T3表示。有 TTTTSAtGAtGStG321)(tGLT 试判断图6.7所示的树是否属于L(Gt)的一个句子。3扩展树文法扩展树文法其中，P中生成式 形式：),(SPrVGt一个树文法有一个对应的扩展树文法。例6.6 构成例6.5中树文法对应的扩展树文法。6.4 文法推断文法推断6.4.1 基本概念基本概念文法推断：用已知类别的模式样本集训练类别文法的过程。统计模式识别训练判别函数 句法模式识别训练类别文法 目的：构造出能正确描述某类模式的文法，其中主要是求 生成式集合P。*选择文法形式（链文法、树文法、图文法）。*根据样本进行推断文法。基本步骤：1语言语言L(G)的正

10、样本集和负样本集的正样本集和负样本集2文法推断的基本思路文法推断的基本思路根据样本集RR+，R-推导出文法G，简化时只有R+。*给定一个R+型的训练样本集，共n个句子，陆续送入 一个“文法推断机”。*输入一个句子，由此初步推断出一个能导生出该句子 的文法G1。*输入第二个句子，补充或修改G1，从而推断出能导生 出这两个句子的文法G2。*推断出文法Gn。*将Gn中各条文做合并处理。*先推断出几种不同的文法，然后再选择一种。简化文法的方法：6.4.2 余码文法的推断余码文法的推断1余码的定义余码的定义2余码文法的推断余码文法的推断余码文法又称形式微商文法。6.4.3 扩展树文法的推断扩展树文法的推

11、断BA 第三步：合并等价非终止符，删除被合并的非终止符的所有后代生成式。例6.8 设某类句法模式树描述的样本集中含有树T1和T2：解：第一步：分别写出产生树T1和T2的生成式。产生树T1的生成式：增加一个，得到产生树T2的生成式：6.5 句法分析句法分析6.5.1 参考链匹配法参考链匹配法利用文法对未知类别的句法模式进行识别或分类的过程。句法分析：*对每一类模式给出一组样本链(参考链)。设有M类模式。*将输入链x与每一类的参考链进行比较，并规定一个比较容 限。x被识别为与其匹配“最好”的参考链所属的模式类。6.5.2 填充树图法填充树图法用于上下文无关文法的分析。若已知某语言的文法Gi，给定某

12、待识别的链x，建立一个以x为底，以起始符S为顶的三角形，如图6.8所示。用文法Gi的生成式填充这个三角形，使之成为一个分析树。若填充成功，表示x可以由文法Gi导出，图6.8 待填充的三角形 填充三角形的方法：顶下法 底上法)(GLx解：填充三角形成功，图6.9 用文法G的生成式填充的三角形6.5.3 CYK分析法分析法库克(Cocke)-杨格(Younger)-卡塞米(Kasami)分析法用于上下文无关文法的分析1乔姆斯基范式乔姆斯基范式 要求：生成式必须表示为乔姆斯基范式。BCA aA 或其中A，B，C为非终止符，a为终止符。例如，乔姆斯基范式为2CYK分析法分析法输入：乔姆斯基范式的上下文

13、无关文法G、输入链x；输出：关于链x的分析表。关键：构造x的分析表 方法：步骤：第五步：停机，填表结束。6.5.4 厄利分析法厄利分析法一种有效的上下文无关文法的分析算法。圆点：分割开经分析后符合的部分和尚未考虑的部分。思路：步骤：反复执行2和3，到没有新项目加入I0为止。反复执行5和6，到没有项目加到Ij中为止。解：6.6 句法结构的自动机识别句法结构的自动机识别自动机：句法模式识别器。识别输入链是否符合与该机相对应的文法。0型文法图灵机1型文法线性有界自动机2型文法下推自动机3型文法有限态自动机每类文法对应一类自动机：链文法：树文法树自动机。其他：1有限态自动机有限态自动机6.6.1 有限

14、态自动机与正则文法有限态自动机与正则文法),(0FqQA输入字母表 内部状态有限集状态转换规则 初始状态 Qq 0终止状态集 QF 自动机每次从一个状态只能转换到另一个指定的状态。确定的有限态自动机：非确定的有限态自动机：自动机每次从一个状态可以转换到一个指定状态集中的任意一状态。如：,),(321qqaq2有限态自动机接受语言的方式有限态自动机接受语言的方式有限态自动机接受的语言：指有限态自动机接受的链x的集合，记为L(A)。),(|)(0中在FxqxAL结构：*x中的字符从左到右依次记录在输入带上。工作方式：*只读头从输入带的最左边一个单元开始依次读取输入字符。*每读取一个字符，状态控制器

15、搜寻原存入的状态转换规则，接受/拒绝这个字符。*如果自动机连续地接受输入链的每个字符，最后停在一个终 止状态上，则称输入链属于该自动机能接受的那种语言，即)(ALx解：将链x输入自动机A，状态转换过程为22010qqqqqaabbFqbbaaq20),()(ALx状态转换图：状态 终止态 进入箭头 状态变化状态变化方向22010qqqqqaabb3有限态自动机与正则文法的对应状态有限态自动机与正则文法的对应状态1）按正则文法构造有限态自动机A和G的对应关系：正则文法的生成式 jiaAA bAi*由正则文法G构成对应的有限态自动机A；应用：若将非终止符Ai，Aj分别命名为qi，qj：,cbaVT

16、,FBASFVQNSq 0A接受链x的过程为：FAAASbaac2）按有限态自动机确定正则文法对应关系：若将qi，qj分别命名为Ai，Aj：6.6.2 下推自动机与上下文无关文法下推自动机与上下文无关文法1下推自动机下推自动机有限态自动机的限制：下推自动机(PDA)：有限态自动机+下推存储器只能接受正则文法产生的语言，不能接受上下文无关文法产生的语言。可识别上下文无关文法产生的句子。结构：*初始状态q0：栈顶为最初的非终止符；*只读头读取输入带字符：输入链中的终止符和栈顶的非终止 符共同决定自动机状态的转换；*状态转换同时，栈顶内容发生变化。*自动机内部状态处于终止态或堆栈变空时，称输入链被自

17、动 机接受（识别）了。下推自动机定义：),(00FZqQAp有限态自动机加Z0和下推符号有限集最初处于栈顶的非终止符Z 0内部状态转换和栈顶内容改变的规则 规则：),(,),(),(),(2211mmqqqZaq讨论：i*为单个非终止符。*为非终止符串。有下推动作，最左边的符号处于栈顶；i*为空串。栈顶Z被弹出，处于Z下面的非终止符处于栈顶。2下推自动机接受语言的方式下推自动机接受语言的方式1）终止态方式2）空堆栈方式自动机接受的语言为：),(),(:|)(00QqqZqxxALpAp 下推自动机接受的语言为：,),(),(:|)(*00FqqZqxxALpAp两种语言等价。3下推自动机与上下文无关文法的对应关系下推自动机与上下文无关文法的对应关系构成方法：依据一个上下文无关文法对应一个下推自动机。上下文无关文法的乔姆斯基范式上下文无关文法的格雷巴赫（Greibach）范式1）格雷巴赫范式生成式aA 2）由上下文无关文法构成下推自动机为：结束结束