模式识别--句法模式识别(2)

2019-04-14 20:42发布

句法模式识别理论支持

1.形式语言

  • 诞生
形式语言的研究开始于上个世纪五十年代,动机:描述人类语言,基于Chomsky提出文法的数学模型。

  • 发展成果
1. 计算机语言的描述
2. 图像结构模式的描述
3. 机器翻译

  • 相关概念
Grammar /Grammars:语法/文法;
Syntax/Syntactic:句法;

  • 实例分析
  • 文法相关概念
导出树:该句子的文法(G)推导过程非终止符号:其它节点终止符号:叶节点起始符号:根节点(特殊的非终止符号)
产生式:导出规则(再写规则

  • 文法G的组成
非终止符集合VN
终止符集合VT
产生式集合P
起始符S

  • 文法四元式
G = (VN, VT, P, S);

  • 字符用法规定

  • 文法分类——Chomsky文法模型
0型——无约束文法
1型——上下文有关文法
2型——上下文无关文法
3型——正则文法
3型(正则)文法是2型文法的特例
2型(上下文无关)文法是1型文法的特例
1型(上下文有关)文法是0型文法的特例

  • 产生式形式
正则(3型)文法:
A→aB 或A→a
上下文无关(2型)文法
A→α;α串非空
上下文有关(1型)文法
α→β;α、β串非空,|α|≤ |β|
无约束(0型)文法
α→β;