形式语言与自动机

　　本书以四类形式语言（短语结构语言、上下文有关语言、上下文无关语言、正则语言）和四种自动机（有穷自动机、下推自动机、图灵机、线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。书中每一章的最后都配有大量不同难度的习题，有助于读者掌握本书内容。
　　 本书采用通俗的语言和形象化的方法来表达概念和定理，逻辑严谨、思维缜密，可作为高等院校计算机及相关专业“形式语言与自动机”课程的教材。

出版者的话
序言
前言
教学建议
第1章　预备知识
　1.1　定理及其证明方法
　　1.1.1　演绎法
　　1.1.2　反证法
　　1.1.3　归纳法
　1.2　集合及其基本运算
　　1.2.1　集合基础知识
　　1.2.2　集合的基本运算
　　1.2.3　关系与映射
　1.3　图和树简介
　　1.3.1 图的基本概念
　　1.3.2 图的矩阵表示
　　1.3.3　树的基本知识
　1.4　字母表、字符串和语言
　习题
第2章　文法的一般理论

　　形式语言和自动机理论是理论计算机科学的重要分支，自20世纪60年代以来发展极为迅速，已经在计算机科学的许多领域起着理论基础和方法论的作用，特别是对程序语言的设计、编译理论与技术、模式识别和自然语言理解等领域起了重要的促进作用。近年来，形式语言和自动机理论的应用范围不断扩大，无论是自然科学的许多领域，还是社会科学的某些领域，都在应用形式语言和自动机的理论成果和描述方式。因此，各发达国家的计算机科学界和教育界对此十分重视，各大学的计算机科学系都把形式语言和自动机方面的内容列为本科高年级学生和研究生的重要课程。美国每年的计算机专业GRE考试中，都有和本书内容有关的考题。我国从改革开放以来，各主要大学也都陆续开设了这方面的课程，而且形式语言和自动机理论越来越受到有关方面的重视，并有不断推广的趋势。.
　　本书作者从事形式语言与自动机方面的教学和研究工作已有30余年，在总结经验的基础上，广泛参考国内外有关著作（包括国外最新出版的教科书），编写了这本教材。教材内容以四类形式语言和四种自动机为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。全书共分12章：第1章为预备知识，介绍一些本书常用的基本概念和推理方法。第2章引入文法的概念，按乔姆斯基体系介绍四类形式文法。第3章到第5章是一个单元，其中，第3章引入有穷自动机的基本概念，并详细介绍各种形式的有穷自动机和它们的应用；第4章介绍正则表达式，提出各种等价变换方法，并论述正则表达式和有穷自动机的关系；第5章对正则语言的各种表现形式加以总结，论述正则语言的各种重要性质，并重点讨论有穷自动机的极小化问题。第6章到第8章是一个单元，其中，第6章详细讨论乔姆斯基体系中最重要的一类文法——上下文无关文法；第7章引入下推自动机的概念，并证明下推自动机和上下文无关文法的等价性；第8章讨论上下文无关语言的性质，作为本单元的一个总结。第9章引入最重要的一类自动机——图灵机，给出它的基本模型和各种变形，其中用很多例子表明图灵机具有很强的识别能力和计算能力，并对图灵机与现代计算机的能力做了比较，最后证明图灵机和0型文法的等价性。第10章集中论述不可判定问题，这一章理论性较强，有一定的难度。第11章介绍线性有界自动机，并证明它与上下文有关文法的等价性，最后对各语言类之间的关系做一总结。第12章进一步讨论确定的下推自动机和确定的上下文无关语言，给出LR(k)文法的定义，并论述它和确定的下推自动机之间的关系。..
　　本书内容较为丰富，如要完全讲授至少需要70学时。建议目录中加“*”号的章节不讲，第10章内容对研究生可以少讲，对本科生可以不讲。此外，其他章节内容也可适当略去一些。但是，无论如何都要保留四类语言和四种自动机以及它们的对应关系这个主线(即本书前9章的主要内容和第11章的部分内容)，否则就不能说学过“形式语言与自动机”这门课程。学习本课程之后，不仅能对学生学习某些后继课（如算法设计与分析、模式识别等）有直接帮助，而且更重要的是能提高他们的逻辑思维和抽象表达能力。
　　在写作方法上，作者力求做到深入浅出。在概念的引入和定理的证明上，一方面逻辑严谨、思维缜密；另一方面尽量采用通俗的语言和形象化的方法来表达，并配合一些能说明问题的例子，使读者容易理解抽象理论的实质，以达到加强理论素养和提高灵活运用能力的目的。书中每一章的最后都配有大量不同难度的习题，有助于读者掌握本书内容，读者可在教师的指导下选择一部分难易适当的习题来做。
　　本书在立项、编写和出版的过程中，得到机械工业出版社华章公司的大力支持，在此表示衷心的感谢。还要对辛运帏教授致以深深的谢意，她对本书从大纲到具体内容都提出了许多宝贵的意见。由于作者的水平有限，书中难免有错误和不确切之处，恳请各位专家和广大读者批评指正。...
　　陈有祺
　　于南开园
　　

　　近20年里，计算机学科有了很大的发展，人们普遍认为，“计算机科学”这个名字已经难以涵盖该学科的内容，因此，改称其为计算学科(Computing Discipline)。在我国本科教育中，1996年以前曾经有计算机软件专业和计算机及应用专业，之后被合并为计算机科学与技术专业。2004年以来，教育部计算机科学与技术教学指导委员会根据我国计算机专业教育和计算学科的现状，为更好地满足社会对计算机专业人才需求，发布了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范(试行)》(以下简称《规范》)，提出在计算机科学与技术专业名称之下，构建计算机科学、计算机工程、软件工程和信息技术四大专业方向。《规范》中四大专业方向的分类，在于鼓励办学单位根据自己的情况设定不同的培养方案，以培养更具针对性和特色的计算机专业人才。.
　　为配合《规范》的实施，落实中央“提高高等教育质量”的精神，我们规划了“面向计算机科学与技术本科专业规范系列教材”。本系列教材面向全新的计算学科，针对我国高等院校逐步向新的计算机科学与技术专业课程体系过渡的趋势编写，在知识选择、内容组织和教学方法等方面满足《规范》的要求，并与国际接轨。本套教材具有以下几个特点：
　　(1)体现《规范》的基本思想，满足其课程要求。为使教材符合我国高等院校的教学实际，编委会根据《规范》的要求规划本套教材，广泛征集在国内知名高校中从事一线教学和科研工作、经验丰富的优秀教师承担编写任务。..
　　(2)围绕“提高教育质量”的宗旨开发教材。为了确保“精品”，本系列教材的出版不走盲目扩大的路子，每本教材的选题都将由编委会集体论证，并由一名编委担任责任编委，最大程度地保证这套教材的编写水准和出版质量。
　　(3)教材内容的组织科学、合理，体系得当。本套教材的编写注重研究学科的新发展和新成果，能够根据不同类型人才培养需求，合理地进行内容取舍、组织和叙述，还精心设计了配套的实验体系和练习体系。
　　(4)教材风格鲜明。本套教材按4个专业方向统一规划，分批组织，陆续出版。教材的编写体现了现代教育理念，探讨先进的教学方法。
　　(5)开展教材立体化建设。根据需要配合主教材的建设适时开发实验教材、教师参考书、学生参考书、电子参考资料等教辅资源，为教学实现多方位服务。
　　我们衷心希望本系列教材能够为我国高等院校计算机科学与技术等专业的教学作出贡献，欢迎广大读者广为选用。...
　　“面向计算机科学与技术专业规范系列教材”编委会
　　

　　第3章有穷自动机
　　继文法的一般理论之后，本章引入语言的另一种表示形式——有穷自动机。虽然有穷自动机是所有自动机中最简单的一种，它表示语言的能力是有限的，但是它构造简单，在生产和生活中都有它的原型，因此它在计算机科学技术和其他学科中都有广泛的应用。掌握了有穷自动机的基本概念，将为后面学习其他更复杂的自动机打下良好的基础。
　　3.1 非形式化描述
　　 在客观世界中，具有有穷多个状态的系统比比皆是。例如，日常用的指针式钟表就是一种有穷状态系统，它共有12×60×60个状态，秒针每走一步，系统就从一种状态转移到另一种状态。一局棋也是一种有穷状态系统，如围棋共有3（361）个状态，棋手每走一步，就从一种状态转移到另一种状态。在工业产品中，也有很多类似的例子。比如，电梯的控制结构就是有穷状态系统的一个典型例子。电梯停在每一楼层作为一个状态，它的控制系统不必记住以前的所有动作，而只要知道现在的位置以及用户给出的信号就可以通过改变它的状态（上或下）来满足用户的要求。某些电子产品中的开关电路，是有穷状态系统的又一实际例子。一个开关电路由有穷多个门电路组成，每个“门”可以处于两种状态——开和关（通常记为1和0）之一。具有n个门的开关网络有2（n）种状态，根据输入的信号可以从一种状态变为另一种状态。为了更清楚地说明实际生活中存在的有穷状态系统，我们简单介绍一个电子商务方面的例子。
　　 电子商务在日常生活中的一个应用就是网上购物，这里涉及三个互相关联的方面——顾客、商店和银行。为简单起见，假设只有一个顾客（而且只有一次购物活动），他已在银行建立了账户。假设商店也在银行建立了账户。顾客可以决定把账户上的钱传送给商店以购买商品，然后商店从银行拿到这笔钱并送货给顾客。而且，顾客可以在一定时间内选择取消购物。也就是说，顾客可以告诉银行不再用这笔钱付购物款。因此，三方之间的交互限于以下五种事件：
　　 （1）顾客决定付款购物。顾客告诉商店购买某种物品，并附带上自己的银行账号。
　　 （2）顾客决定取消付款。顾客通知银行，把购物这笔钱保留在自己的银行账号上。
　　（3）商店送货给顾客。
　　（4）商店兑换货款。商店要求银行把顾客购物这笔钱划拨到自己的银行账号上。
　　（5）银行将这笔钱转账。银行把顾客购物这笔钱划拨给商店的账号。
　　……