第6章向法模式识别
第6章句法模式识别6.1句法模式识别概述6.2形式语言的基本概念6.37模式的描述方法6.4文法推断6.5句法分析6.6句法结构的自动机识别
6.1 句法模式识别概述 6.2 形式语言的基本概念 6.3 模式的描述方法 6.4 文法推断 6.5 句法分析 6.6 句法结构的自动机识别 第6章 句法模式识别
6.1句法模式识别概述模式用句子形式描述，结构信息十分重要一句子模式词组子模式基元单词组合关系自然语言的文法句法模式识别用小而简单的基元与语法规则描述和识别大而复杂的模式，通过对基元的识别，进而识别子模式，最终识别复杂模式。个模式类符合某个文法的所有句子的集合
6.1 句法模式识别概述 模式用句子形式描述，结构信息十分重要。 模式 子模式 基元 句子 词组 单词 组合关系 自然语言的文法 句法模式识别用小而简单的基元与语法规则描述和识别 大而复杂的模式，通过对基元的识别，进而识别子模式，最终 识别复杂模式。 符合某个文法的所有句子的集合 一个模式类
句子B墙壁fC名词短语动词短语bedD冠词名词动词副词E地板gThegirlhardstudies(b)景物A(a)子模式背景C物体B墙地板8长方体E三棱柱D基元壁f三面面面基面角元dace福形图6.1景物结构描述与英文句子句法描述的对比b(c)
（a） 句子 名词短语 冠词 动词短语 名词 动词 副词 The girl studies hard （b） 墙壁 f 地板 g E D B b a d c e 景物 A 物体 B 背景 C 三棱柱 D 长方体 E 面 a 三 角 形 b 面 c 面 d 面 e 地 板 g 墙 壁 f 子 模 式 基 元 基 元 （c） 图6.1 景物结构描述 与英文句子句法描述的对比
句法模式识别系统的组成：图象分割模式句法预处理或分解描述分析输入图象分类结果（模式）和描述识别学习文法基元和训练样本推断关系选择句法模式识别存在的主要问题：*基元选择尚无通用的方法：文法推断理论远不及统计学习发展得成熟句法模式识别的理论基础：形式语言20世纪50年代中期乔姆斯基（Chomsky）
句法模式识别系统的组成： 输入图象 （模式） 分类结果 和描述 模式 描述 基元和 关系选择 图象 预处理 分割 或分解 句法 分析 识别 学习 文法 推断 训练样本 句法模式识别的理论基础：形式语言 20世纪50年代中期乔姆斯基（Chomsky）。 * 基元选择尚无通用的方法； * 文法推断理论远不及统计学习发展得成熟。 句法模式识别存在的主要问题：
6.2形式语言的基本概念6.2.1基本定义1.字母表与问题有关的符号的有限集合，用V或又表示例: V =(A, B,C,.., Z) V, =(0, 1,2)2.句子由字母表中符号组成的有限长度的符号串，又称链。空句用入表示。组成：英文小写字母、数字。句子的长度：句子包含符号的数目，用表示，例：由V=a,b,c中元素可组成句子：重写次数lab3c3=9abc,aacc
6.2 形式语言的基本概念 6.2.1 基本定义 1．字母表 与问题有关的符号的有限集合，用V或∑表示。 2．句子 由字母表中符号组成的有限长度的符号串，又称链。空句 用λ表示。 组成：英文小写字母、数字。 例：由 V = {a, b, c} 中元素可组成句子： { , , , , } V1 = A B C Z {0, 1, 2} 例： V3 = abc，aacc，. 重写次数 句子的长度：句子包含符号的数目，用|•|表示。 | | 9 3 3 3 a b c =
3.语言由字母表中的符号根据某种文法组成的句子的集合V*：V中符号组成的所有句子的集合，包括空句：V+：不包含空句的句子集合。V+ =V*-{a)例：V*={a,ab,aabbcc,..Vt -fab, aabbcc,...4.文法构成一种语言的句子所必须遵守的规则G=(Vn,Vr, P, S)V：非终止符的有限集，子模式的集合，大写字母表示VT：终止符有限集，基元的集合，字母表起始部分的小写字母表示
3．语言 由字母表中的符号根据某种文法组成的句子的集合。 V * ：V中符号组成的所有句子的集合，包括空句； V +：不包含空句的句子集合。 { } * = − + V V { , , , } V * = ab aabbcc V = {ab, aabbcc, } 例： + 4．文法 构成一种语言的句子所必须遵守的规则。 G (V ,V , P, S ) = N T VN ：非终止符的有限集，子模式的集合，大写字母表示。 VT ：终止符有限集，基元的集合，字母表起始部分的小写 字母表示
终止符组成的字符串：用英文字母表尾部的小写字母x，y，V，w等表示，终止符和非终止符组成的混合字符串：用希腊字母α，β，等表示性质：VUV,=V（字母表）n=（空集）P：生成式的有限集。用文法产生句子时的重写规则P:α→βN替换字符串字符串S：起始符，代表模式本身，特殊的非终止符用生成式构成句子时，必须由左边是S的生成式开始
终止符和非终止符组成的混合字符串： 用英文字母表尾部的小写字母x，y，v，w等表示。 终止符组成的字符串： 用希腊字母α，β，γ等表示。 性质： VN VT =V （字母表） VN VT = （空集） P：生成式的有限集。用文法产生句子时的重写规则。 P： → 字符串 替换 字符串 S：起始符，代表模式本身，特殊的非终止符。 用生成式构成句子时，必须由左边是S的生成式开始
一种语言有一种文法，由文法G构成的语言用L（G）表示：L(G)=(x/xeV，且S=x福文法G的文法G构成的句子V-中字符组成的由终止符组成所有句子的集合推导关系"：零次或多次地应用推导关系=GS=x：句子x从起始符S开始利用文法G的生成式G经逐步推导得到
一种语言有一种文法，由文法G构成的语言用L(G)表示： ( ) { | , } * L G x x V S x G T = 且 文法G构成的句子 由终止符组成 VT中字符组成的 所有句子的集合 文法G的 推导关系 “ G ” ：零次或多次地应用推导关系 G “ S x G ”：句子 x 从起始符 S 开始利用文法 G 的生成式， 经逐步推导得到
例6.1 给定文法G=(V,VT,P,S)，其中V=A,B,S)V=a,b,cf，P的各生成式为S→aAc,②A→aAc,③A→B④BbB，?B-b判断x=aabcc是否属于语言L（G）？12解：是S三aAc三aaAccaaBcc三aabcc说明：利用文法构成句子时，除第一个生成式必须利用左边为起始符S的生成式外，其余生成式使用的先后次序及重复使用的次数都不受限制
例 6.1 给定文法 G (V ,V , P, S ) = N T ，其中 V {A, B, S} N = ， V {a, b, c} T = ，P 的各生成式为 ①S →aAc，② A→aAc，③ A → B ④ B →bB ，⑤ B →b 判断 x = aabcc 是否属于语言 L(G ) ？ S aAcaaAccaaBcc aabcc ① ② ③ ⑤ 利用文法构成句子时，除第一个生成式必须利用左边 为起始符 S 的生成式外，其余生成式使用的先后次序及重 复使用的次数都不受限制。 是 说明： 解：