前面介绍的所有思想都属于统计模式识别，然而统计模式识别存在2个问题：

1.有的模式结构很复杂，不能用一个矢量来表示。

2.有的模式识别任务中，我们更关心如何描述它的结构特征。

因此需要另外一种模式识别：结构模式识别。

这其中，句法模式识别主要使用形式语言来描述模式结构，在理论上完备，表1是句法模式识别与统计模式识别的对应关系，下面做介绍。

表1

串文法就是一种机器能识别的语法，所以先讲讲语法。

字母表V

字母a,b,c的有限集合。              

句子x,y,z

V中的符号形成的有限长度的字符串。

这其中是V的闭包，包含了字母表能组成所有句子的集合。

而是V的正闭包，就是把闭包里面的那1个空串去掉就好了。

这种区别就像是正数与非负数的关系，非负数去掉0就是非负数了。

文法G = 

一个文法或者说语法，有4部分组成就好了。

这4个部分依次代表：非终止符、终止符、生成规则、起始符。

这其中有

举个例子：The boy runs.如图1所示。

图1

非终止符就是那些还要继续寻找对应关系的元素，比如说Noun，它与我们想表达的Theboy runs.这个句子相比要进一步寻找对应关系，Noun并不是最终出现在句子里的部分，因此倒了Noun并没有终止，Noun继续链接到boy才OK。所以像Noun这样的元素就叫非终止符。

终止符刚刚介绍了，就是最终要出现在句子里的部分。像The、boy、runs这些都是。

起始符在这个例子中是Sentence，就是句子开始的标志。

P（生成规则）比较复杂，生成规则就是符号的变换规则表。就像是法律一样，在相应的语法环境下，必须按照这个规则来生成句子。

符号习惯

非终止符：大写字母

终止符：小写字母

仅由终止符构成的字符串：用后面小写字母构成的x,y,z

由终止符和非终止符混合构成：用希腊字母

 表示一些列地调用P中的规则。

语言L(G)

语言是字符串的集合。由文法G产生。特点是

1.所有的字符串由终止符构成

2.每个字符串都是从S出发调用P中的规则而产生。

串文法的分类

第0类：无限制文法

这种对文法不加限制，基本没用。

第1类：上下文有关文法

这种规则就是说，仅当上下文是时，中间的非终止符A才能替换成为混串。这就是其名字的由来。

第2类：上下文无关文法

这种文法是说，不论上下文如何A都可以用 来替换。

第3类：正规文法

正规文法是最常用的一种文法。

四种文法的关系

如图2.

图2

举个例子:染色体分析

现在要识别2类染色体:中央着丝染色体和顶端着丝染色体。如图3.

图3

作为句法的5种基元a,b,c,d,e分别是5种最简单的形状，如图4.

图4

这些基元能构成6种子模式（就是非终止符）：

S——臂对，B――底， C——边，  D——单个臂，  E——右臂，  F——左臂。

于是这个染色体语法就可以表示出来了：

这个P生成规则太多了实在是，而且比如A究竟要用到哪条规则是无法事先知道的，要试试。只要最后试出来一条能走完的路径就认为是符合语法的。否则只有当所有可能的路径都不能从S出发，才可以认为该句子是不符合语法的。

最后按照该文法可以得到2种染色体对应的字符串分别为：

1. abcbabdbabcbabdb

2. ebabcbab

如图5.

图5