【模式识别与机器学习】——5.2 形式语言理论和句法模式识别

　　在模式识别中，如果大量复杂的模式的集合，能用一组为数不多的简单的模式基元和文法规则来描述，则对每一个模式的识别，就可以按给定的一组文法结构规则来剖析； 如果解析的结果表明，模式基元能为给定的文法规则所接受，则可判别它属于该模式类，否则就不属于该模式类。

5.2.1 形式语言理论中的某些定义

　　形式语言是一种抽象语言，它可以包括人类使用的自然语言、计算机使用的各种语言、数学中的公式语言等。

　　自然语言（英文）：它的基本组成是有限个字母，将字母（组成的单词）按一定的文法规则排列，可以构成句子，而一种语言则是所有句子的集合。

　　人类的自然语言是一个不可数的有穷集 英文：26个字母按一定的文法规则组合，可以表达无数的思想内容。

（1）字母表和符号串

字母表：以某些符号作为元素的非空有穷集，以V或Σ表示。

符号串：由字母表中符号组成的任何有穷序列。

　　V={a,b,c}是一个字母表，符号串可以是a,b,c,ab,aaca,… ∑={0,1}是一个字母表，符号串可以是0,1,00,01,10,110,…

空符号串：不包含任何符号的串，用ε表示。

符号串的长度：符号串x所包含的符号个数，用|x|表示。

　　|a|=1，|aab|=3，|ε|=0

符号串的联接：若x和y都是符号串，则把y符号串写在x符号串之后，就得到联接的符号串xy。

　　例：x=ab，y=bc，则xy=abbc，yx=bcab 对于空符号串的连接有εx=xε=x

例：A={a,b}，B={cd,e}，则AB={acd,ae,bcd,be} 如果A和B只是代表一个符号串，而不是符号串的集合，则乘积AB与符号串的联接结果相同。

例：V={a,b}，则V*={ε,a,b,aa,ab,bb,…}， V+=V*- ε={a,b,aa,ab,bb,…}

（2）文法

　　一种语言中构成句子所必须遵守的规则； 由某种语言的字母表中的字母所组成的串不一定都是该语言的句子； 只有当一个串符合该语言的文法规则时，才能算是该语言的句子，否则就不是该语言的句子。

说明：

　　在生成规则P中，带< >的符号称为语法元，不带< >的符号称为单词； 一个简单句的生成由语法元(<sentence>)开始，反复把生成规则中箭头左边的部分用其右边的部分替换，直到所得的形式中不再出现语法元而只有单词为止。 简单句“The boy runs.”符合给定的文法规则，因为它可以由上述的文法规则产生。

利用文法树可以阐明文法的形式化定义： 文法树的根一定是文法G的起始符S； 树的叶一定是终止符； 树的每一个分支（子树）在沿着根到叶的方向上可以表示成一个直接推导的生成式； 如果利用文法树的逆过程，则可将生成过程重新构造出来。