5 模式识别原理课件-第6章句法模式识别.ppt

6.4.3 扩展树文法的推断 第三步：合并等价非终止符，删除被合并的非终止符的所有 后代生成式。 例6.8 设某类句法模式树描述的样本集中含有树T1和T2： 解：第一步：分别写出产生树T1和T2的生成式。 产生树T1的生成式： 增加一个，得到产生树T2的生成式： 6.5 句法分析 6.5.1 参考链匹配法 利用文法对未知类别的句法模式进行识别或分类的过程。 句法分析： * 对每一类模式给出一组样本链(参考链)。 设有M类模式。 * 将输入链x与每一类的参考链进行比较，并规定一个比较容 限。 x被识别为与其匹配“最好”的参考链所属的模式类。 6.5.2 填充树图法 用于上下文无关文法的分析。 若已知某语言的文法Gi，给定某待识别的链x，建立一个以x 为底，以起始符S为顶的三角形，如图6.8所示。 用文法Gi的生成式填充这个三角形，使之成为一个分析树。 若填充成功，表示x可以由文法Gi导出， 图6.8 待填充的三角形 填充三角形的方法： 顶下法 底上法 解：填充三角形成功， 图6.9 用文法G的生成式填充的三角形 6.5.3 CYK分析法 库克(Cocke) -杨格(Younger) -卡塞米(Kasami)分析法 用于上下文无关文法的分析 1．乔姆斯基范式 要求：生成式必须表示为乔姆斯基范式。 或 其中A，B，C为非终止符，a为终止符。 例如， 乔姆斯基范式为 2．CYK分析法 输入：乔姆斯基范式的上下文无关文法G、输入链x； 输出：关于链x的分析表。 关键：构造x的分析表 方法： 步骤： 第五步：停机，填表结束。 6.5.4 厄利分析法 一种有效的上下文无关文法的分析算法。 圆点：分割开经分析后符合的部分和尚未考虑的部分。 思路： 步骤： 反复执行2和3，到没有新项目加入I0为止。 反复执行5和6，到没有项目加到Ij中为止。 解： 6.6 句法结构的自动机识别 自动机：句法模式识别器。 识别输入链是否符合与该机相对应的文法。 0型文法 图灵机 1型文法 线性有界自动机 2型文法 下推自动机 3型文法 有限态自动机 每类文法对应一类自动机： 链文法： 树文法 树自动机。 其他： 1．有限态自动机 6.6.1 有限态自动机与正则文法 输入字母表 内部状态 有限集 状态转换规则 初始状态 终止状态集 自动机每次从一个状态只能转换到另一个指定的状态。 确定的有限态自动机： 非确定的有限态自动机： 自动机每次从一个状态可以转换到一个指定状态集中 的任意一状态。如： * * 6.1 句法模式识别概述 6.2 形式语言的基本概念 6.3 模式的描述方法 6.4 文法推断 6.5 句法分析 6.6 句法结构的自动机识别 第6章 句法模式识别 6.1 句法模式识别概述 模式用句子形式描述，结构信息十分重要。 模式 子模式 基元 句子 词组 单词 组合关系 自然语言的文法 句法模式识别用小而简单的基元与语法规则描述和识别 大而复杂的模式，通过对基元的识别，进而识别子模式，最终识别复杂模式。 符合某个文法的所有句子的集合 一个模式类 （b） 墙壁 f 地板 g E D B b a d c e （c） 图6.1 景物结构描述 与英文句子句法描述的对比 句法模式识别系统的组成： 句法模式识别的理论基础：形式语言 20世纪50年代中期乔姆斯基（Chomsky）。 * 基元选择尚无通用的方法； * 文法推断理论远不及统计学习发展得成熟。 句法模式识别存在的主要问题： 6.2 形式语言的基本概念 6.2.1 基本定义 1．字母表 与问题有关的符号的有限集合，用V或∑表示。 2．句子 由字母表中符号组成的有限长度的符号串，又称链。空句 用λ表示。 组成：英文小写字母、数字。 例：由 中元素可组成句子： 例： abc，aacc，… 重写次数 句子的长度：句子包含符号的数目，用|?|表示。 3．语言 由字母表中的符号根据某种文法组成的句子的集合。 V *：V中符号组成的所有句子的集合，包括空句； V +：不包含空句的句子集合。 例： 4．文法 构成一种语言的句子所必须遵守的规则。 VN ：非终止符的有限集，子模式的集合，大写字母表示。 VT ：终止符有限集，基元的集合，字母表起始部分的小写 字母表示 。 终止符和非终止符组成的混合字符串： 用英文字母表尾部的小写字母x，y，v，w等表示。 终止符组成的字符串： 用希腊字母α，β，γ等表示。 性