教材《形式语言与自动机》朱保平 李千目编著 清华大学出版社

 

说明：本文尽可能避免使用繁琐的数学表达，和只求信不求达雅的文字定义。无法避免时用注释方式给出

 

一、形式语言和自动机的关系

形式语言和自动机这两个概念看起来风马牛不相及，前者是语言学上的概念，而后者更像计算机科学的概念。这两者又是通过什么联系起来了呢？

在自动机这一部分知识的最后，介绍了图灵机的概念。图灵机是一种计算机的模型，可以依据既定的策略（程序）在一条有内容的带（可以看做内存）前后移动，改变上面的内容，简单的图灵机可以进行字符串的处理，复杂的图灵机可以进行逻辑分支判断和加法运算，到这里就出现了计算机的雏形。

图灵是著名的计算机科学家，他帮助盟军破译德军密码机器enigma的故事家喻户晓。在计算机科学还处于萌芽乃至种子状态的二战时期，破译密码更多的是语言学家的事。实际上，图灵作为一个“计算机科学家”在那时是不受“密码专家”语言学家待见的。在图灵为英国政府工作的时期，他和语言学家共事了相当长的时间。

因此，抛开各种各样的形式语言和各种各样的自动机不谈，我们看到，在历史上，计算机科学还远没有得到充分发展的时期，语言和计算机有一个神奇的交集。这实际上暗示了，形式语言和自动机有着某种基本的、本质的联系，这我下面还会再总结。

二、形式语言

从字面意义上看，“形式语言”是某种语言，我认为，把“形式语言”理解成“语言形式”更加直接，即“形式语言”的本质不是语言，而是形式。如果抛开“形式语言”这样一个拗口的术语，简单地看“语言形式”，待解决的问题清晰地出现在我们面前：语言有什么形式？怎样表述语言的不同形式？语言的不同形式怎样影响他们的性质？

首先要解决的问题是怎样表述语言的不同形式？一个合格的语言形式应该能做到两点：第一，从该形式演绎出的任何句子都是可以被会这种语言的人理解（用集合论的话说，属于该语言）的；第二，会这种语言的人表达的任何句子（属于该语言的句子）都可以被这种形式所归纳。语言学家Chomsky用“文法”来定义某种语言的形式。

/* 文法的定义是四元组 G=(V,T,P,S)，T是不可以再分的语义单元，如英语中的单词，V是可以再分的语义单元，如短语（注意短语中可以包含短语），S是V中的一部分，是句子的开头，P是任何短语、单词及其组合之间的递归转换关系，如动词短语可以转换为一个动词和一个名词。单个单词是不可再被转换的 */

文法是元素（单词）和规则（类似于语法）的集合，是一种足够强大的描述语言形式的工具，理论上可以用来描述语法规则非常复杂的变态语言（另一方面，没有语法规则的语言最变态，所以说是“描述语法规则十分简单的变态语言”也能说通）。实际上，由于这种工具太过强大，必须对其加以限制才能较好描述常见的语言。不加以任何限制的文法描述0型的语言，通过逐级加入各种限制，不同类型的文法可以描述1型、2型和3型语言。其中1型又称上下文有关语言，2型加入了含有单词的语义单元不可再被转换的限制，大大减弱了句子之间各个成分的联系，成为上下文无关语言，3型语言限制最多性质最好，又称正则（regular）语言。

如此，我们利用文法定义了若干种语言。其中最常见于计算机科学的明显是上下文无关语言和正则语言。上下文无关语言根据其转换规则可以表达成类似于树的形式，因而也可以使用图论的方法进行搜索。同时在某种上下文无关语言的等价范围内可以对其的文法进行化简和优化表达，如Chomsky范式。正则语言具有上下文无关语言的所有性质，但具有更强的局部性，可以通过鸽巢原理和泵引理对两者进行区分。

三、自动机

自动机是一种机器的模型，是非常广义的概念，人也可以是自动机。具体地，可以首先考虑自动机的一种，有穷状态自动机。有穷状态自动机的数学描述是一个集合，简单来说，它可以说是针对某种特定输入的一系列有限的规则，对不同的输入的元素，自动机依据自身的状态会做出不同的响应，即调整自己的状态，最后以自己的状态达到某种特定的输出。有穷状态自动机有许多的形式，有的允许面对一定的输入做出不同的选择，有的允许没有输入也可以改变自身的状态，但本质上它们都是等价的，可以相互转化。

进一步地，由于自动机的状态是有限的，它无法做到对已经处理过的无限数据的记忆，如果为自动机分配内存（一个或者两个下推栈），那么就得到了下推自动机。下推自动机对不同的输入元素，依据自身的状态做出响应时，不仅会调整自己的状态，还会改变内存的状态，进而达到记录已经处理过的数据的目的，完成更加复杂的功能。

到此，语言的形式和自动机之间的关系可以得到建立了。简单的有穷自动机，可以处理简单（语法限制更多性质更好）的正则语言，下推自动机可以处理上下文无关语言。所谓处理，是可以判断语言是否合法，而判断的方式，就是这种语言的句子能否被自动机的程序所归纳，这说明了语言的形式和自动机之间的等价关系。由于高级计算机语言大量属于上下文无关语言，因此在编译（对这种语言进行分析和处理时）必然就要用到下推自动机这一工具。