本书以四类形式语言（短语结构语言、上下文有关语言、上下文无关语言、正则语言）和四种自动机（有穷自动机、下推自动机、图灵机、线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。

本书的主要特色
　　■取材丰富。涵盖了该领域国内外现有教材的主要内容。
　　■在写作方法上，循序渐进，深入浅出。在概念的引入和定理的证明上，尽量采用通俗的语言和形象化的方法来表达。
　　■理论与实际相结合。除具有配合定理和定义的大量例题外，许多章节还有现代计算机技术中应用的实例。
　　■适应面广。既适合作为本科生的教材，也适合作为研究生的教材。

　　作者简介
　　陈有祺，南开大学信息技术科学学院教授，多年来一直从事计算机软件方面的教学和研究工作，从1993年起享受国务院政府特殊津贴。讲授的课程主要有程序设计语言、编译原理、数据结构、形式语言与自动机等，研究领域包括编译理论、人工智能、自然语言理解、形式语言等。1980年至1982年在美国西密歇根大学作访问学者，研修人工智能和形式语言，回国后一直为研究生讲授“形式语言与自动机”课程。相关著作包括：《BCLR(k)文法及其分析算法》、《广义上下文无关文法和它的语法分析》、《从输入输出序列确定自动机的结构》、《形式语言与自动机》等。

无

形式语言和自动机理论是理论计算机科学的重要分支，自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章的部分内容)，否则就不能说学过“形式语言与自动机”这门课程。学习本课程之后，不仅能对学生学习某些后继课（如算法设计与分析、模式识别等）有直接帮助，而且更重要的是能提高他们的逻辑思维和抽象表达能力。
　　在写作方法上，作者力求做到深入浅出。在概念的引入和定理的证明上，一方面逻辑严谨、思维缜密；另一方面尽量采用通俗的语言和形象化的方法来表达，并配合一些能说明问题的例子，使读者容易理解抽象理论的实质，以达到加强理论素养和提高灵活运用能力的目的。书中每一章的最后都配有大量不同难度的习题，有助于读者掌握本书内容，读者可在教师的指导下选择一部分难易适当的习题来做。
本书在立项、编写和出版的过程中，得到机械工业出版社华章分社的大力支持，在此表示衷心的感谢。还要对辛运帏教授致以深深的谢意，她对本书从大纲到具体内容都提出了许多宝贵的意见。由于作者的水平有限，书中难免有错误和不确切之处，恳请各位专家和广大读者批评指正。

　　陈有祺
　　于南开园

本书以四类形式语言（短语结构语言、上下文有关语言、上下文无关语言、正则语言）和四种自动机（有穷自动机、下推自动机、图灵机、线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。 本书的主要特色 ■取材丰富。涵盖了该领域国内外现有教材的主要内容。 ■在写作方法上，循序渐进，深入浅出。在概念的引入和定理的证明上，尽量采用通俗的语言和形象化的方法来表达。 ■理论与实际相结合。除具有配合定理和定义的大量例题外，许多章节还有现代计算机技术中应用的实例。 ■适应面广。既适合作为本科生的教材，也适合作为研究生的教材。 作者简介 陈有祺，南开大学信息技术科学学院教授，多年来一直从事计算机软件方面的教学和研究工作，从1993年起享受国务院政府特殊津贴。讲授的课程主要有程序设计语言、编译原理、数据结构、形式语言与自动机等，研究领域包括编译理论、人工智能、自然语言理解、形式语言等。1980年至1982年在美国西密歇根大学作访问学者，研修人工智能和形式语言，回国后一直为研究生讲授“形式语言与自动机”课程。相关著作包括：《BCLR(k)文法及其分析算法》、《广义上下文无关文法和它的语法分析》、《从输入输出序列确定自动机的结构》、《形式语言与自动机》等。

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

　 “面向计算机科学与技术专业规范系列教材”编委会

出版者的话

序言

前言

教学建议


第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章文法的一般理论

21问题的提出

22形式文法与形式语言

23文法的乔姆斯基分类

习题

第3章有穷自动机

31非形式化描述

32有穷自动机的基本定义

33非确定的有穷自动机

34具有ε转移的有穷自动机

35有穷自动机的应用

351在文本中查找字符串

352用于文本搜索的非确定
的有穷自动机

353识别关键字集合的
DFA

*36具有输出的有穷自动机

习题

第4章正则表达式

41正则表达式的定义

42正则表达式和有穷自动机的
关系

43正则表达式的等价变换

431交换律与结合律

432单位元与零元

433分配律

434与“*”构造有关的
定律

435发现正则表达式定律的
一般方法

44正则表达式的应用

441UNIX中的正则

表达式

442词法分析

443查找文本中的模式

习题

第5章正则语言的性质

51正则文法和有穷自动机的
关系

52正则语言的泵引理

53正则语言的封闭性

54正则语言的判定算法

55有穷自动机的最小化

习题

第6章上下文无关文法

61上下文无关文法的语法分析

62上下文无关文法的化简

63上下文无关文法的范式

64上下文无关文法的应用

641用上下文无关文法描述
语言

642语法分析器生成工具
YACC

643标记语言

644XML和文档类型

定义

习题


第7章下推自动机

71下推自动机的定义

72下推自动机接受的语言

73下推自动机和上下文无关
文法的关系

74确定的下推自动机

习题

第8章上下文无关语言的性质

81上下文无关语言的泵引理

82上下文无关语言的封闭性

83上下文无关语言的

判定算法

习题

第9章图灵机导引

91图灵机的基本模型

92图灵机的程序设计技术

921在状态中存储符号

922多道技术

923子程序技术

93图灵机的变形

931双向无限带

932多带

933非确定的图灵机

934双栈机

935作为枚举器的
图灵机

94图灵机与计算机

941用计算机模拟
图灵机

942用图灵机模拟

计算机



943比较计算机与图灵机的
运行时间

95图灵机与0型文法的关系

习题

第10章不可判定性

101递归集和递归可枚举集的
性质

102通用图灵机和第一个不可判定
问题

103归约方法和莱斯定理

104关于上下文无关语言的不可
判定问题

*105波斯特对应问题的不可判定性
及其应用

习题

第11章线性有界自动机和上下文
有关文法

111线性有界自动机

112线性有界自动机和上下文有关
文法的关系

113上下文有关语言的性质及其与
递归集的关系

114各语言类之间的关系

习题

*第12章确定的上下文无关语言和
LR(k)文法

121确定的下推自动机的标准
形式

122确定的上下文无关语言的
性质

123LR(0)文法

124LR(0)文法与DPDA的

关系

125LR(k)文法

习题

参考文献