思维科学探索-第44章

按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！


，还有的文法是对所用的产生式的次序加以限
制，如程序文法（罗申克瑞兹。另外在自然语言和程
序语言方面都进行了大量的工作。
有一个
乔姆斯基针对过去语言研究中的归纳方法，建立起一个
演绎性的形式语言系统。根据他的理论，某种语言
的有限个符号的集合，如英语的
中的符号从左往右排构成长
表示链中所包含的符号
中的符号所
第　302　页
优秀的
学生
〈动词〉〈副词
能够成的所有链用表示，所研究的语言是的一个子
集。中还包含着空链，空链包括语言单位之间的间隔，如
时，起着重要的作用。表示。
一段话语与另一段话语之间的停顿。空链在描写句子的结构
中除去空链所成的集合用
这些符号在以后将会遇到。
是一个动词短
下面简单的谈谈短语结构语言，虽然它的概念来源于分
析英文句子。为方便起见，我们用一个中文句子“优秀的学
生学习努力”为例加以说明，然后再转到讨论文法。这里
“优秀的学生”是一个名词短语作为主语，它包括着形容词
“优秀的”和名词“学生”，“学习努力
语，它包括动词“学习”和副词“努力”。这个句子可以由
下面的步骤形成。
〈句子〉
、〈名词短语〉〈动词短语〉
、〈形容词〉〈名词〉〈动词短语〉
、优秀的〈名词〉〈动词短语〉
、优秀的学生〈动词短语〉
、优秀的学生〈动词〉〈副词〉
、优秀的学生学习〈努力〉
、优秀的学生学习努力
〈句子〉
上述这些步骤可以依次按下列产生规则：
〈名词短语〉〈动词短语
〈名词短语〉〈形容词〉〈名词〉
〈动词短语〉
形容词〉
〈名词〉
第　303　页
是产生式的左部，　是产生式的右部。
学习
努力
表示“可以再写成”。
这样一个句子的产生还可以用树形图表示如下：通过
上面的分析我们来定义产生短语结构语言的短语结构文
法，一个短语结构文法是形如
四元式，其中和
量）。在上面例子中
）　的
是非终止符和终止符字母表（　或变
＝｛〈句子〉，〈名词短语〉，〈动词
短语〉，〈形容词〉，〈名词〉，〈动词〉，〈副词〉
＝｛优秀的，学生，学习，努力｝
和的总和构成的总字母表，且
写，　是产生式（或再规则）有限集产生式形式表示成
其中都是中的变量组成的链，且中至少包括一个
非终止符，　是
子
中一个特殊的符号，称为起始符，对应于上面例中的〈句
。把句子的生成与图象的生成加以比较，也可以用短语结
构文法来产生或描述图象。例如，用下列短语结构文法生成：
次中性染色体〉）
〈动词〉
〈副词〉
上式中的
第　304　页
〈臂对〉
〈臂对〉
〈臂对〉
〈臂对〉
：〈次中性染色体〉
〈边〉〈臂对〉
〈臂对〉〈边〉
〈臂〉〈右部〉
〈左部〉〈臂
〈臂对〉
臂部〉〈臂〉（接下页）
〈臂对〉
右部〉，〈臂〉，〈边〉
，　｛　〈次中性染色体〉，　〈臂对〉，　〈左部
第　305　页
型（没有限制）的文法，即产生
可以
来
型文法到
〈臂〉
（　接上页）
〈右部〉
〈边〉
边〉
〈臂〉
〈臂〉
〈边〉
〈边〉
〈边〉
〈边〉
〈臂〉
〈臂〉
〈臂〉
乔姆斯基根据产生式的不同形式把短语结构文法
分成种类型。第一种称为
式的箭头两端的链可以是任意的。这样的文法过于广泛
而没有什么用处，一般说来不能确定一条由终止符组成的链
是否由型文法产生。由型文法产生的语言称为
型文法，
型语言。第
二种称为型文法的产生式的形式是有限制的，形式
为：　其中且
的情况下，
由型文法叫做上下文敏感文法。上下文
（　零链）。这意味着在上下文分别为
来加以代换，所以
型文
，其中
敏感文法产生的语言称为上下文敏感语言。第三种称为
法或上下文无关文法，产生式的形式为：
可以用，
代换而这种代换与型文法或有
），这意味着非终止符
的上下文无关。第四种称为
或其中
都是单个符号。从
限状态文法，产生式的形式为：
，这里
型文法，对于产生式的限制是逐步增加的。因此它们之间
便有这样的关系：
第　306　页
要研究高维图象文法。克尔希（
型型型型
很明显它们所产生的语言之间也有这种关系。
我们可以用不同的观点来看待语言，文法是从生成的观
点来看，另一种是从接受的观点来看，那就是识别（自动
机）的观点。短语结构文法中的每一种文法与
，上下文
种类型的自
动机对应，即该种文法产生的语言恰好能够由对应的自动机
接受。文法和自动机是密切联系而不可分的。有限状态文法
与有限状态自动机（
无关文法与非确定下推自动机（
机（
，上下文敏感文法与线性有界自动
型文法与图灵机
）相对应。
短语结构文法所产生的语言是字母表中的符号组成的
链。这种链是通过产生式规则生成的。对于描述某些一维的
模式，如声音、波形等是有效的。上面谈到的染色体是把外
形转换成一维的表示，对于描述图象及高维模式满足不了要
求，所以就需要研究高维模式文法。
三、图象文法　　　　　　符号链是一维的，符号之间只有左右
连接关系，而图象模式是二维的，连接关系就不仅仅是左右
连接。用产生符号链的链文法来产生二维的图象需要首先把
象转换成一维的链，这样很不方便，效率也低，很自然就
）可能是第一
条产生式，产生式
个给出一个完整的图象文法的人。他构造了一个能够产生任
意等边直角三角形的文法。文法中包括
以图形方式给出。以具有九个方格的方块表示：
第　307　页
中的一个。所描绘的直角三角形以表示直角顶点，　、
和斜边由
和、
组成，另一条边由组成，三角形的内点为字母
可、中的一个，
其他两个顶点分别为组成，一条底边由
在上述产生式中，符号可以是
是中的一个，　可以是以
及空白中的一个。在产生式（　）　中，
条开始，以
在
不同的位置可以代表不同的字母。在使用产生式时，箭头两
端希腊字母代表同样的符号。这些产生式从第
任何方式进行直至没有规则可用而构成一个等边直角三角形
方块中可以是空白，或者是英文字母
第　308　页
为止。所产生的三角形如图所示，从这些产生式的形式
可以看出来，要求在一定条件下进行代换所以这一文法是上
下文敏感的文法。
接起来用一个向量表示，然后定义种连接运算关系：
把每个图象元素规定头（　）和尾（　，并且把头尾连
另外还提出过一种图象描述语言
图
第　309　页
）描述房子。其树状表示如下：
描述英文字母链（　）　）
于是上述文法产生的链（（　）
三角形（
房子（　）　）　（　三角形）
房子，　（三角形）　）
以及产生式集
，　，
形＝
，其中＝　房子，三角
用下面的文法可以产生英文字母和房子
如果以种线段作为基本元素
此外，运算表示把头尾例置
第　310　页
，丛状文法（　，其中
先后曾经提出过一些图象文法如网状文法（　与
第　311　页
产生的链表
表示的模
，使得由文法
分析”。除了回答
所示：
树状文法因为能有效地进行句法分析，所以比较广泛的采
用。下面的例子给出用树状表示描绘一个简单的电感电容线
路，如图
个模式类，可以分
四、句法分析　　如果构造了一个文法来产生一种语言，
这种语言恰好能描述我们所研究的模式。识别模式就变成识
别语言了。下一步就是设计一个识别程序来识别由文法所产
生的语言，并且要求根据某个特定的文法所设计的识别程序
只能识别这个文法产生的语言。例如有
个文法
类中的模式。那么对于一个未知的、用链
别构造
示第
式，模式识别问题基本上成为这样的问题：　属于个文法
代表的模式属于或不属于
中哪一个文法产生的语言？求解这一问题的过程称为“句法
产生的语言
之外，句法分析的过程还提供这个模式的结构信息。
如果是有限状态文法，那么就可以根据有限状态文法
与有限状态自动机之间的对应关系，设计一个有限状态自动
～
第　312　页
机来产生的语言。如果文法
相一致，那么
是上下文无关文法
一般说来要求设计一个非确定的自动机，我们可以用下述方
式来了解句法分析：给定一个句子
号表示的一条链）以及一个文法
是用字母表中的符
。如果能做到构造一个三
角形，三角形的内部由文法
就属于
产生的树状表示填满，而底边
的符号正好与产生的语言，否则
就不属于产生的语言。举个简单的例子，考虑
产生链的树状表示式如下：
第　313　页
号开始，是否能把终止符用非终止符代替，逐步自下往上，
法称为“自上而下”的句法分析。另一种是从输入链的符
是否能产生与输入链的符号相一致的终止符链。这种作
上即从树形的根向下的方式进行。根据文法规则考虑最终
如何把三角形填满，在则上并不重要，我们可以从顶
第　314　页
最后是否能与起始符相吻合。这种作法称为“自下上”的
句法分析。
扬格一凯萨密算法
进行句法分析不能乱凑，要研究算法用机器来进行分
析。对于上下文无关文法已经提出不少有效的算法，如厄利
算法是一种自下而上的有效算法，凯克
是一种自上而下的有效算法。至于上下文敏感的文法句法非
常繁复，句法分析的算法未得到好的解决。
用一个摄象机或者用一
五、噪声和畸变模式的识别　　　　　　用机器来识别图象模
式，首先就要通过扫描装置把胶片上或者纸上的图象经个
过光电转换变成数字信号。扫描可
飞点扫描装置，免不了会有噪声使图象发生某种畸变，具
体应用模式识别技术的过程中也不可避免的会遇到一些不确
定的因素，如在通信，存储、信息检索、测量和处理具体模
式时都会遇到噪声和干扰。所以应该把识别程序设计得在有
干扰的情况下也能正确地进行识别。
用语言来描述噪声和畸变模式时就会遇到所谓的“含
混”问题，即几个不同的文法都可产生同一条链，换句话
说可能发生模式类之间有一部分重叠的现象。解决这类问题
的一种自然的办法是把短语结构语言推广到随机短语结构语
言，分别把文法、识别程序中的状态转移加以随机化建立随
机文法以及随机句法分析算法。用随机语言来描述有噪声和
和畸变的模式，就可以用概率信息来解决含混问题。另一种
办法是在句法方法中用统计模式识别中模板匹配的作法，定
义两条链之间的距离度量，用一条链称为标准模式链来描述
模板。由于噪声干扰的影响，标准模式链可能畸变成为另一
条链。考虑可能有种误差①代换误差，链中的一个符号
第　315　页
换除链中的一个符被掉；　插入
插入：　删除：　。
另一符号；　删
误差，在链的两个相连符号之间插入一个新的符号。于是用这
三种误差的数目，或者这三种误差加