语言与计算理论导引

《语言与计算理论导引》由会员分享，可在线阅读，更多相关《语言与计算理论导引（4页珍藏版）》请在金锄头文库上搜索。

1、语言与计算理论导引语言与计算理论导引John C. Martin前言什么是语言？为什么要研究语言？狭义地讲，语言是人类内心世界的外在符号，是交流的工具，广义地讲，动物等事物都具有语言，比如狗的不同叫声和摇尾表达不同的情感，汽车不同的闪灯表示不同的意义。汽车的语言是人赋予的，是一种人工语言。但无论什么语言，它最重要的用途是不同事物间交流意思。既然世界上存在如此众多的语言，那么他们有些什么区别哪？显然人的语言比狗或车复杂多了，一个自然的推论就是能够处理越复杂语言的物体，则它越“聪明”，具备的能力越强大。计算机已经从最初单纯的辅助计算工具逐渐演化成人脑的模拟器，但只有当计算机处理的语言同人脑处理的语

2、言一样复杂，它才可能真正完成人脑能够完成的所有工作。因此，自然要问：如何准确地刻画一个语言的复杂度？很多年前，我们知道上海比北京暖和，现在科学的进步让我们能够精确地显示两地温度的差异。我们能够找到（或发明）刻画语言复杂度的“摄氏温度计”吗？一个了不起的观点是：一个语言是一个集合。研究语言不是仅仅关心其中的一两个句子，要研究组成语言的所有句子的共性，发现处理组成语言的所有句子的通用方法。我们认为自然界的语言确实是有共性的句子组成的，即他们是有规律的。因此人工语言也应当是依照一定规律设计。既然语言有规律，那么刻画一个语言除了罗列这个语言的所有句子，另一个方法就是描述这个语言的规律。语言规律的表现形

3、式往往是规则。描述语言规律的一个简单方法是罗列规则，因此一个语言可以是句子集，也可以表示为一个规则集。规则集在形式上往往比句子集要简洁很多，因此我们希望用规则集的复杂度来表示语言的复杂度。那么问题变成什么是刻画语言的规则和规则集？什么是规则的复杂度？显然刻画规则也需要一种语言，存不存在一个语言，它描述的规则能够刻画所有的语言（甚至包括它自身）？只有用相同语言描述的规则才能比较它们的关系和复杂度。当然我们可以用某种自然语言，比如英语等，但自然语言的缺陷是显而易见的，它只能被人使用，而英语一般只能被英语国家的人使用。既然我们希望计算机理解这些语言的差异，因此我们最好使用某种计算机理解的语言。Cho

4、msky找到（或发明、发现）的这种语言称为文法语言，它描述的规则称为文法，形如ab。因此有了文法，就可以定义规则和语言的复杂度了。但Chomsky文法仍有缺点，比如刻画语言的能力和粒度不够细，它可以刻画0型、1型、2型和3型语言，但还有许多语言无法刻画，其中包括很重要的人类自然语言。尽管如此，它是目前我们找到的较好方法，为包括高级程序语言的人工语言的设计和发展给出了指导性方针。这些人工语言在形式上由于有精确的定义，往往又称为形式语言。本书仅仅研究形式语言，我们希望这些研究有助于更深刻地理解自然语言，为最终发现具有自然语言同样能力的形式语言作出贡献，而那一天就是计算机真正具备人脑能力的一天，当然

5、目前而言，这不是一个可实现的梦想，我们期待在追逐这个梦想的过程中，得到人类精神生活中的一些收获，或一些较低目标的物质的副产品。本书是面向本科生的有关计算理论的导引性书籍，内容重点是形式语言、自动机、计算的抽象模型和可计算性，也包括计算复杂性和NP-完全性的一些导引知识。研究这些问题具有这样一些意义：学生接触了比较深奥、但不会很快过时的计算理论。许多不同领域的技术都对计算机科学做出了贡献，然而学生将认识到计算理论是计算机科学的核心领域之一。学生将逐步精通数学工具和形式化方法，并看到这些技术的威力和在计算上的适用性。第二版尽力保留了第一版的一个优点（我相信）：逐步且温和地引入必要的数学知识。我们既

6、希望利用数学语言的简洁和精确，又通过例子和讨论使得初学者也能理解这种语言。本书的编写特别考虑了那些没有离散数学背景的学生，当然具备良好离散数学基础的学生也适于阅读本书。本书进行了实质性重写，更正了许多错误，and no more new ones introduced than absolutely necessary。我尽力修改了第一版中不是很正确的地方，几个证明和解释变得更清楚易懂了，增加了一些例子，修改了一些例子，更换了一些例子。重新组织全文，各章变得更紧凑和自成体系。比如，第一版中的有些两章或三章合并成一章，总章数从24变成了15，一些章节被搬动，另一些不重要的章节被省略或以练习题的方

7、式出现。第二版提供了更多、更好的练习题，提供了记号索引，增加了许多主题索引。第2章增加了结构归纳法小节，第7章增加了回文（palindromes）语言不能被确定型下推自动机接受的一个简单证明，第8章增加了Ogden引理的讨论，第12章增加了Rice定理和另外一些关于Turing机有效计算的材料，提供了上下文无关文法无解结果（？unsolvability result）的另一种方法。最后部分提供了基本复杂类的定义、这些类之间的基本关系和更多的例子。尽管最后部分仍然只是计算复杂性理论的简短介绍，但相比第一版，内容更完备了。无论教学内容是否包括第一部分，我都推荐认真阅读1.5节，本节引入了与语言相关

8、的记号和术语。读者也可以复习数学归纳法、递归定义、结构归纳法和一些与形式语言相关的例子。在North Dakota State University，本书作为计算机科学专业的教材，学时为连续的两学期。课程进度较慢，两个学期都提供了足够丰富的材料。进度较快的一学期课程省略了第一部分的大部分，仅包括正规语言和上下文无关语言，以及Turing机和可解性理论的部分内容。另外，由于第4、5、6部分的大部分内容与前3部分基本独立，因此后三章也可作为Turing机、可计算性和计算复杂性的教材。引言考虑一个简单的计算，比如两个整数相加。为了让计算机处理，你用数字串对两个整数进行编码，并将数字串输入计算机。当处

9、理完毕，计算机输出的也是数字串。从接受输入到输出答案，计算机做了些什么呢？计算机做了“计算”。就是说，计算机遵循一套系统过程，或称算法，它可以用于任何表示整数的字符串输入，并保证经过有限的步骤后得到答案。也许术语“计算”意味着数字，但符号串编码输入的想法的通用性允许了算法同样可以处理非数字数值。至少两个问题很快出现了，它们都与计算理论相关。什么是算法，或系统过程？什么是计算机？感觉上，找到任何一个问题的答案就足够了。如果我们知道什么是算法，这样我们可以说计算机就是执行算法的东西；反之，如果我们知道了什么是计算机，则可以合理地定义算法是计算机能够执行的东西。有时候两种方法都是有用的，但现在我们取

10、第二种方法。至少一般而言，你知道桌上的或实验室里的电脑由那些东西组成，但是很难基于某个理论去详细说明这些物理部件，而且即使可以，针对不同的硬件设备，这个理论需要不同的修改，因此不会太有用。任何情况下，尽管物理学家和电子工程师都要学习半导体和集成电路，但不应该是为了学习“计算”。加法就是加法，不管是计算机所做，还是小孩利用数手指完成。我们的理论与其他许多理论一样，不涉及具体的对象而是理想化的对象，前者太复杂，而后者比较简单。我们考虑几种能够用数学定义的抽象计算模型和抽象机器，其中一些具备与真实机器一样的能力，另一些能力稍弱但更简单。简化机器仍然值得研究，部分因为从它们能够更容易地引入计算理论的数

11、学形式化，部分因为它们具有真实世界的对应物，部分因为它们完成的计算在真实世界的变形情况中是有用的。为了理解本专题中“语言”的含义，我们可以考虑一个决策问题的想法，决策问题就是对每个实例都能回答“是”或“否”的计算问题。下面是一个熟悉的有关数值的例子：给定一个正整数n，判断它是否是一个素数？输入的数值n用一个数字串表示，解决这个问题的计算输出“是”或“否”。我们可以认为这是一个语言识别问题：给定一个任意的数字串，判断它是否属于由所有表示素数的字符串组成的语言。同样，解决任何一个决策问题可以看成识别一种语言，这个语言由所有回答为“是”的表示问题实例的字符串组成。不是所有的计算问题都是决策问题，我们

12、更强大的计算模型能够处理更通用的情况，那些要求的答案比“是”或“否”更复杂的问题，往往存在对应的一个决策问题。比如，如果f是一个函数，回答这个问题：给定x和y，是否y=f(x)？等同于对任意的x计算f(x)。语言识别问题与计算的抽象模型是统一的主题。不同类型的计算机器识别不同复杂度的语言，因此对应我们研究的计算模型，我们得到一个由多种语言类型构成的层次结构。我们考虑的最简单的抽象机是有限自动机，或称有限机。它基于的原理很通用：任何具有有限数目的离散状态、在任一时刻处于某个状态、状态转移由单个输入信号决定的系统都可以用有限自动机模型化。这些机器能够识别的语言是正规语言，正规语言也能被描述成通过反

13、复应用某种基本操作从单元语言得到的语言。正规语言包括一些程序语言的部件，其相应机理用在编译器、文本编辑器等多种软件中。有限自动机最明显的限制是只跟踪当前状态，没有过去状态的纪录，因此只能识别简单的语言。上下文无关语言比正规语言有更丰富的语法，它可以由上下文无关文法产生，识别它的计算装置称为下推自动机，下推自动机是带有栈形式内存的有限自动机。上下文无关文法最初用于模型化自然语言，如英语，的一些特性，尽管能力有限，但由于能够描述高级程序设计语言及其相关语言的大部分语法，因此在计算机科学中具有重要意义。上下文无关文法对应的机器下推自动机提供了一种自然的方法解决高级程序设计语言的指令分析问题，通过重建

14、规则序列来确定指令的语法，by which it is derived in the context-free grammar。辅助内存使得下推自动机成为比有限自动机更强大的计算装置，但内存组织方式的限制妨碍了下推自动机成为更通用的计算模型。Turing机，得名于发明它的英国数学家Alan Truing，是一种更强大的计算机。普遍认为Turing机能够处理任何算法，能够被Turing机识别的语言比上下文无关语言更广泛。而且由于Turing机能够输出字符串，而不仅仅是简单的“是”和“否”，因此理论上，尽管Turing机的处理比较笨拙和低效，但Turing机能够处理现代计算机能够处理的所有计算。然

15、而Turing机能够做的事仍然是有限制的，因为我们能够精确地描述这种抽象模型，所以我们能够公式化地说明它不能解决的计算问题。此时我们不再可能仅仅提出更强大的机器，也没有更强大的机器了，我们必须承认无解问题的存在。由于它们的存在，计算理论除了研究计算机的能力，还必须研究计算机的局限。最后，尽管Turing机实施计算是笨拙的，却是比较不同计算问题的固有复杂性的有效码尺。有些原理上可解的问题由于需要极大的空间和极长的时间，在实际中并不是真正可解的。有关Turing机的一个简单标准被广泛地用于区别可解问题和不可解问题。尽管这个标准简单，但并不总是很容易判断问题是否满足这个标准。在最后章，我们讨论了一类

16、有趣的问题，我们既无法找到解决它们的有效算法，也无法证明有效算法不存在。人类计算的历史已经有几千年了，但发明计算机器的历史并不长，而计算成为人类生活中密切相关的一部分的历史则更短。计算理论的历史比电子计算机稍长，这是因为这个领域的一些先驱，如Turing等，预见到了计算机潜在的能力，他们的工作奠定了现代数字计算机的概念模型。计算理论也受益于其他一些领域，比如数学、物理、语言学、生物学和电子工程等等。值得注意的是：这些看似无关的各部分很优美地融合进一个紧凑的理论。这个理论为计算机科学的各个领域提供了不断发展的洞见。4陶晓鹏 Copyright 2003语言与计算理论导引 可计算函数40陶晓鹏 Copyright 2003碎语注意，自动机领域的两大主线，确定型和非确定型。非确定型与概率的结合。比较Turing机和现代计算机。问题：集合越大的语言越复杂？不对，*集就很简