语言及计算理论导引.docVIP

语言与计算理论导引 John C. Martin 前言 什么是语言？为什么要研究语言？狭义地讲，语言是人类内心世界的外在符号，是交流的工具，广义地讲，动物等事物都具有语言，比如狗的不同叫声和摇尾表达不同的情感，汽车不同的闪灯表示不同的意义。汽车的语言是人赋予的，是一种人工语言。但无论什么语言，它最重要的用途是不同事物间交流意思。既然世界上存在如此众多的语言，那么他们有些什么区别哪？显然人的语言比狗或车复杂多了，一个自然的推论就是能够处理越复杂语言的物体，则它越“聪明”，具备的能力越强大。 计算机已经从最初单纯的辅助计算工具逐渐演化成人脑的模拟器，但只有当计算机处理的语言同人脑处理的语言一样复杂，它才可能真正完成人脑能够完成的所有工作。因此，自然要问：如何准确地刻画一个语言的复杂度？很多年前，我们知道上海比北京暖和，现在科学的进步让我们能够精确地显示两地温度的差异。我们能够找到（或发明）刻画语言复杂度的“摄氏温度计”吗？ 一个了不起的观点是：一个语言是一个集合。研究语言不是仅仅关心其中的一两个句子，要研究组成语言的所有句子的共性，发现处理组成语言的所有句子的通用方法。我们认为自然界的语言确实是有共性的句子组成的，即他们是有规律的。因此人工语言也应当是依照一定规律设计。 既然语言有规律，那么刻画一个语言除了罗列这个语言的所有句子，另一个方法就是描述这个语言的规律。语言规律的表现形式往往是规则。描述语言规律的一个简单方法是罗列规则，因此一个语言可以是句子集，也可以表示为一个规则集。规则集在形式上往往比句子集要简洁很多，因此我们希望用规则集的复杂度来表示语言的复杂度。 那么问题变成什么是刻画语言的规则和规则集？什么是规则的复杂度？显然刻画规则也需要一种语言，存不存在一个语言，它描述的规则能够刻画所有的语言（甚至包括它自身）？只有用相同语言描述的规则才能比较它们的关系和复杂度。当然我们可以用某种自然语言，比如英语等，但自然语言的缺陷是显而易见的，它只能被人使用，而英语一般只能被英语国家的人使用。既然我们希望计算机理解这些语言的差异，因此我们最好使用某种计算机理解的语言。Chomsky找到（或发明、发现）的这种语言称为文法语言，它描述的规则称为文法，形如(((。因此有了文法，就可以定义规则和语言的复杂度了。 但Chomsky文法仍有缺点，比如刻画语言的能力和粒度不够细，它可以刻画0型、1型、2型和3型语言，但还有许多语言无法刻画，其中包括很重要的人类自然语言。尽管如此，它是目前我们找到的较好方法，为包括高级程序语言的人工语言的设计和发展给出了指导性方针。这些人工语言在形式上由于有精确的定义，往往又称为形式语言。 本书仅仅研究形式语言，我们希望这些研究有助于更深刻地理解自然语言，为最终发现具有自然语言同样能力的形式语言作出贡献，而那一天就是计算机真正具备人脑能力的一天，当然目前而言，这不是一个可实现的梦想，我们期待在追逐这个梦想的过程中，得到人类精神生活中的一些收获，或一些较低目标的物质的副产品。 本书是面向本科生的有关计算理论的导引性书籍，内容重点是形式语言、自动机、计算的抽象模型和可计算性，也包括计算复杂性和NP-完全性的一些导引知识。 研究这些问题具有这样一些意义：学生接触了比较深奥、但不会很快过时的计算理论。许多不同领域的技术都对计算机科学做出了贡献，然而学生将认识到计算理论是计算机科学的核心领域之一。学生将逐步精通数学工具和形式化方法，并看到这些技术的威力和在计算上的适用性。 第二版尽力保留了第一版的一个优点（我相信）：逐步且温和地引入必要的数学知识。我们既希望利用数学语言的简洁和精确，又通过例子和讨论使得初学者也能理解这种语言。本书的编写特别考虑了那些没有离散数学背景的学生，当然具备良好离散数学基础的学生也适于阅读本书。 本书进行了实质性重写，更正了许多错误，and no more new ones introduced than absolutely necessary。我尽力修改了第一版中不是很正确的地方，几个证明和解释变得更清楚易懂了，增加了一些例子，修改了一些例子，更换了一些例子。重新组织全文，各章变得更紧凑和自成体系。比如，第一版中的有些两章或三章合并成一章，总章数从24变成了15，一些章节被搬动，另一些不重要的章节被省略或以练习题的方式出现。 第二版提供了更多、更好的练习题，提供了记号索引，增加了许多主题索引。第2章增加了结构归纳法小节，第7章增加了回文（palindromes）语言不能被确定型下推自动机接受的一个简单证明，第8章增加了Ogden引理的讨论，第12章增加了Rice定理和另外一些关于Turing机有效计算的材料，提供了上下文无关文法无解结果（？unsolvability result）的另一种方法。最