形式语言与自动机的发展和在计算理论中的作用

2015060104020王桢

形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能用 O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为 BNF范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为

理论计算机科学的一个重要分支。

形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。

19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,形成了开关网络理论。为了对能行性、机械过程或算法进行精确的数学描述，图灵于提出的图灵机描述计算过程的数学模型。它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器，并可执行如下操作:读写头在存储带上向左移动一格;读写头在存储带上向右移动一格;在存储的某一格内写下或清除一符号;条件转移。图灵机在理论上能模拟现代数字计算机的一切运算，认为是现代数字计算机的数学模型。实际上，一切\可计算\函数都等价于图灵机可计算函数，而图灵机可计算函数又等价于于一般递归函数类。诺伊曼在1948年提出建立自动机的一般逻辑理论，对各种人造自动机和天然自动机进行比较性研究，探索其共同规律。他还研究了自动机的自繁殖和自恢复问题。诺伊曼被认为是自动机论的创立者。自动机理论发展过程中产生许多类别的自动机，包括有限自动机，无限自动机，概率自动机，细胞自动机等。

有限自动机的理论得到广泛深入和系统的研究，成为自动理论当中最成熟的领域，并在许多工程上得到应用。确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质，许多为其他自动机不能判

定的问题，在有限状态自动机的情形下，都可以得到判定，并且存在有效的算法。无限自动机论主要研究对象为算法和理想计算机这种存储量不受限制的自动机。研究的问题包括探索计算机和计算过程的数学模型，以及各种模型之间的关系。在计算时间、存储空间和机器规模等资源受限制的情况下，自动机所计算的函数类和识别集的类的刻划、包含关系和代数性质。下推自动机作为一个形式系统最早出现在欧廷格的论文中。它与上下文无关文法的等价性是由乔姆斯基于1962年发现的。

自动机论与形式语言理论关系密切。一方面自动机作为形式语言的一种主要描述方法，另一方面形式文法也可作为自动机识别集的一种描述方法。自动机论与计算复杂性理论的一些领域交叉重叠，例如组合复杂性和计算复杂性。自动机论是计算机科学的基础理论中较早形成的部分。这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。