形式语言与自动机

1、形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称为字母表，用表示。又用*表示中字母组成的所有符号串的集合。*的每个子集都是上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林

2、在研究神经细跑中，建立了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：若某一语言能用图灵机来识别，则它就能用 O型文法生成，反之亦然；若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALG

3、OL60修改报告。在这两个报告中，第一次使用一种称为 BNF范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计

4、算机学科里重要的分支。19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,形成了开关网络理论。为了对能行性、机械过程或算法进行精确的数学描述，图灵于提出的图灵机描述计算过程的数学模型。它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器，并可执行如下操作:读写头在存储带上向左移动一格;读写头在存储带上向右移动一格;在存储的某一格内写下或清除一符号;条件转移。图灵机在理论上能模拟现代数字计算机的一切运算，认为是现代数字计算机的数学模型。实际上，一切"可计算"函数都等价于图灵机可

5、计算函数，而图灵机可计算函数又等价于于一般递归函数类。诺伊曼在1948年提出建立自动机的一般逻辑理论，对各种人造自动机和天然自动机进行比较性研究，探索其共同规律。他还研究了自动机的自繁殖和自恢复问题。诺伊曼被认为是自动机论的创立者。自动机理论发展过程中产生许多类别的自动机，包括有限自动机，无限自动机，概率自动机，细胞自动机等。有限自动机的理论得到广泛深入和系统的研究，成为自动理论当中最成熟的领域，并在许多工程上得到应用。确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质，许多为其他自动机不能判定的问题，在有限状态自动机的情形下，都可以得到判定，并且存在有效的

6、算法。无限自动机论主要研究对象为算法和理想计算机这种存储量不受限制的自动机。研究的问题包括探索计算机和计算过程的数学模型，以及各种模型之间的关系。在计算时间、存储空间和机器规模等资源受限制的情况下，自动机所计算的函数类和识别集的类的刻划、包含关系和代数性质。下推自动机作为一个形式系统最早出现在欧廷格的论文中。它与上下文无关文法的等价性是由乔姆斯基于1962年发现的。自动机论与形式语言理论关系密切。一方面自动机作为形式语言的一种主要描述方法，另一方面形式文法也可作为自动机识别集的一种描述方法。自动机论与计算复杂性理论的一些领域交叉重叠，例如组合复杂性和计算复杂性。自动机论是计算机科学的基础理论中

7、较早形成的部分。这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。英国A.M.图灵提出一种理想计算机，后人称之为图灵机。1944年，W.S.麦克卡洛和W.匹茨用数理逻辑方法研究神经网络。40年代中期出现电子计算机以后，美籍匈牙利数学家J. 受计算机的影响，50年代初，开关网络的研究重点转移到一般的逻辑网络，特别是门电路类型开关网络。1954年前后形成了时序机（即有限自动机）这一重要数学概念。同时，从数字计算机的一种理想的数学模型的角度，开始对图灵机深入研究。1956年自动机研究论文集的出版，标志着自动机论已形成为一门独立的学科。50年代以来

8、，自动机论有了很大的发展。 无限自动机的理论主要是处理计算过程，对图灵机理论的研究一直在持续进行，对更自然的计算机数学模型的探索和在资源限制下自动机的功能的研究也有了较大的进展。概率自动机主要是概率有限自动机的理论，在1963年后有了较大发展。60年代后期以来，细胞自动机主要是在生物学和大规模集成电路技术的基础上成为自动机论中一个活跃的领域。同时，在抽象自动机方面，也开展了研究。学科内容自动机论可分为五个次级学科。包括开关网络理论，主要研究对象为继电器接点电路、数字电路、理想神经网络这类存储量有限的自动机。主要的研究问题是综合和分析问题。一种典型的问题提法是：研究由某种数学语言陈述的功能出发，

9、设计出满足要求的有限自动机和实现它的逻辑网络的系统方法。这涉及到功能描述数学语言、状态化简、状态赋值、布尔函数化简、多值逻辑、组合复杂性和分解等问题的研究。另一个重要方向是1959年开始研究的可逆性问题，主要研究判别、求逆和结构问题。自动机作为转换器将输入序列变换为输出序列，没有输入的自动机可作为序列产生器，没有输出的自动机可作为序列识别器。有限自动机作为序列产生器是50年代中期开始深入研究的一个方向，代数方法得到了很好的应用。有限自动机作为序列识别器的研究方向，较早地建立了比较完善的理论。60年代初开始的一个重要研究问题是， 另一个从50年代末开始活跃的领域是，将自动机识别集作为形式语言的一

10、种刻划方法，对各种限制类型自动机的功能的研究。概率自动机论主要研究对象是在环境或内部具有随机因素的(有限或无限)自动机。概率有限自动机（即随机时序机）是1948年仙农提出的，作为噪声信道的一种模型。60年代后开始系统地发展，主要是推广确定自动机的结果，研究实现、化简、识别和稳定性等问题。在自恢复自动机方面，50年代初诺依曼研究的由不可靠元件构造可靠系统的方向，到70年代发展为容错计算这一活跃的研究领域。另一个方向是对各种概率自动机所识别的语言的研究。细胞自动机论主要研究对象是由许多互相连接的小自动机并行运算形成的大自动机。这项研究始于诺依曼对自繁殖自动机的研究。从他提出的细胞空间概念发展出许多

11、研究方向。与计算机有关的一个方向是具有细胞类型的并行计算机模型的研究，这些研究已应用到一些并行计算机的体系设计中。70年代活跃起来的另一个方向面向大规模集成电路技术，研究具有一致结构的各种细胞自动机的分析、综合和容错等问题。在发育生物学方面，1968年荷兰生物学家A.林顿梅伊尔推广了诺依曼的细胞空间概念，提出了一种动态细胞自动机的数学结构，通常称之为L系统，用以描述多细胞组织的发育过程。1974年以来，L-系统的理论是一个十分活跃的研究领域。抽象自动机论将自动机作为一种数学系统，研究它的一般数学性质。一个重要的研究方向为自动机的半群理论，它为有限自动机的分解问题提供了工具。另一个方向是研究范畴

12、上自动机，目标是建立一个关于有限自动机、线性控制系统、树自动机、概率自动机和拓扑自动机等的统一理论。与其他学科的关系和应用自动机论是古老的数学学科的一个新兴分支。在它的形成和发展过程中，其他数学分支特别是数理逻辑起了很大的作用。自动机论和数理逻辑的一些领域交叉重叠，例如可计算性理论和无限自动机的功能理论都以算法为主要研究对象，但它们的侧重点不同。自动机论又是控制论的一部分。自动机，包括有限自动机、图灵机和理想神经网络，是控制论系统的一种模型。自适应、自学习、自恢复和自繁殖自动机的研究，是典型的控制论问题。自动机论与控制论的其他部分关系也很密切。例如，自动机论与控制理论中的许多结果是类似的，这种类似性成为抽象自动机研究的一个出发点。自动机论的形成受自动控制、计算机和数字通信技术的推动，它的成果又应用于这些技术学科中。自动