形式语言与自动机理论引论

编辑推荐：形式语言与自动机理论因其以体现计算学科中模型描述、模型研究和模型计算为问题求解的主要特征而成为计算机科学与技术、软件工程、网络空间安全等计算机类学科教育的*重要内容之一。本书按照我国相关学科研究生教育当前的实际需求，根据作者30余年的教学实践编著而成，以正则语言与上下文无关语言的文法、识别模型及其性质，以及图灵机基本知识为载体，分9章讨论相关内容，力图使学生建立基于模型的建立、研究、处理而实现问题求解的意识，掌握相应的基本方法，提升解决问题的能力与水平。? 本书是基于国家精品教材《形式语言与自动机理论》编著的，重点考虑了研究生教育的需求。? 通过模型建立、等价变换、性质分析，使读者逐渐熟悉模型计算。层次分明，循序渐进，符合认知规律，突出设计形态内容，很好地体现了本专业理工兼有的特征和学科“抽象*”的教育基本原理。? 引导能力导向的教育。以知识为载体，注重模型建立、构造、变换、证明的方法与思想探讨，挖掘知识背后的内容，支持研究型教学，强化专业基本能力和创新能力的培养。? 取材合适，结构严谨，深入浅出，把握知识点间的联系，安排铺垫，分散难点，突出重点，努力化解深奥，保持基本内容抽象和形式化，通过思路表达的可视化提高了易懂性，富有启发性，使抽象、枯燥的内容变得吸引人。? 配有大量难度适当、前后呼应、富有启发性、努力结合专业、宏观和微观兼有的习题。附教学设计、缩写符号、词汇索引等，便于学习。教学资源：? 《形式语言与自动机理论(第3版)》（ISBN 9787302318026）：“十二五”普通高等教育本科*规划教材，高等教育*精品教材，北京市教学成果一等奖，北京市高等教育精品教材。优秀经典教材。本书集作者30余年相应课程的教学经验和20余年对专业教育的研究体会编著而成。自第1版在2003年出版以来，受到读者的厚爱，成为是国内主创的、发行量*、*秀的形式语言与自动机理论教材。? 《形式语言与自动机理论教学参考书(第3版)》（ISBN 9787302317814）：本书根据作者作为《形式语言与自动机理论》一书的配套读物，按照原书的结构编写而成。重点讨论有关内容的讲解和学习的要点、问题分析、求解思路和方法、注意事项、典型习题的解析等。按照小节给出知识点和主要内容解读。为读者学习和掌握原书中的知识点和问题求解方法、体会问题求解的核心思想提供帮助，对教师和学生来说，阅读这些内容都是有意义的。? 主教材的PPT电子课件：可在清华大学出版社网站下载。    本书是研究生和高年级本科生学习“形式语言与自动机理论”课程的优秀教材，配套教学资源丰富。本书的PPT电子课件、配套的源代码，可在清华大学出版社官网http://www.tup.com.cn下载。
 

形式语言与自动机理论因其以体现计算学科中模型描述、模型研究和模型计算为问题求解的主要特征而成为计算机科学与技术、软件工程、网络空间安全等计算机类学科教育的*重要的内容之一。本书按照我国当前计算机类及相关学科研究生教育实际需求，结合作者30余年的教学实践编著而成，以正则语言与上下文无关语言的文法、识别模型及其性质，以及图灵机基本知识为载体，分9章讨论相关内容，力图强化学生基于模型的建立、研究、处理，实现问题求解的意识，让学生掌握相应的基本方法，提升解决问题的能力与水平。
本书适合计算机类及相关学科研究生使用，也可以供相关专业高年级本科生、教师和科研人员参考。

 蒋宗礼，教授，博士生导师。*教学名师，享受政府特殊津贴，国家精品课程、国家精品资源共享课“编译原理”负责人、计算机软件基础课*教学团队负责人, 主编高等教育“十一五”、“十二五”*规划教材多部，《形式语言与自动机理论》为普通高等教育*精品教材。获国家教学成果二等奖2项，省部级教学、科研奖励十多项。曾获CCF杰出教育奖和中国高校优秀青年学者、宝钢优秀教师、航天部优秀青年教师等荣誉称号。主要学术兼职有中国工程教育认证协会学术委员会委员、结论审议委员会委员、计算机类专业认证委员会委员、教育部高校计算机类专业教学指导委员会副主任，历任全国高校计算机教育研究会正、副理事长，中国计算机学会教育专委正、副主任，中国计算机学会教育工委正、副主任，是计算机类*教学团队协作组发起人、国家精品资源共享课建设专家组成员。近年主讲编译原理、形式语言与自动机理论、新生研讨课等。

目录CONTENTS

第1章语言与文法1

1.1语言2

1.1.1什么是语言2

1.1.2形式语言与自动机理论的产生2

1.1.3基本概念3

1.2文法9

1.3文法的构造18

1.4文法的乔姆斯基体系26

1.5空语句36

1.6小结38

习题38

第2章有穷状态自动机44

2.1语言的识别44

2.2有穷状态自动机46

2.3不确定的有穷状态自动机57

2.3.1作为对DFA的修改57

2.3.2NFA的形式定义58

2.3.3NFA与DFA等价60

2.4带空移动的有穷状态自动机64

2.5FA是正则语言的识别器68

2.5.1FA与右线性文法68

2.5.2FA与左线性文法72

2.6FA的一些变形73

2.6.1双向有穷状态自动机74

2.6.2带输出的FA75

2.7小结76

习题77

第3章正则表达式82

3.1启示82

3.2正则表达式的形式定义83

3.3正则表达式与FA等价85

3.3.1正则表达式到FA的等价变换85

3.3.2正则语言可以用正则表达式表示93

3.4正则语言等价模型的总结98

3.5小结100

习题100

第4章正则语言的性质103

4.1正则语言的泵引理103

4.2正则语言的封闭性108

4.3MyhillNerode定理与DFA的极小化114

4.3.1MyhillNerode定理114

4.3.2DFA的极小化122

4.4关于正则语言的判定算法130

4.5小结131

习题132

目录形式语言与自动机理论引论第5章上下文无关语言134

5.1上下文无关文法134

5.1.1上下文无关文法的派生树135

5.1.2二义性140

5.1.3自顶向下的分析和自底向上的分析143

5.2上下文无关文法的化简145

5.2.1去无用符号146

5.2.2去ε产生式149

5.2.3去单一产生式组152

5.3乔姆斯基范式155

5.4格雷巴赫范式158

5.5自嵌套文法163

5.6小结164

习题164

第6章下推自动机168

6.1基本定义168

6.2PDA与CFG等价174

6.2.1PDA用空栈接受和用终止状态接受等价174

6.2.2PDA与CFG等价177

6.3小结186

习题186

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

7.1上下文无关语言的泵引理189

7.2上下文无关语言的封闭性195

7.3上下文无关语言的判定算法200

7.3.1L空否的判定200

7.3.2L是否有穷的判定201

7.3.3x是否为L的句子的判定202

7.4小结204

习题204

第8章图灵机205

8.1基本概念206

8.1.1基本图灵机206

8.1.2图灵机作为非负整函数的计算模型213

8.1.3图灵机的构造215

8.2图灵机的变形221

8.2.1双向无穷带图灵机221

8.2.2多带图灵机224

8.2.3不确定的图灵机226

8.2.4多维图灵机227

8.2.5其他图灵机229

8.3通用图灵机231

8.4几个相关的概念233

8.4.1可计算性233

8.4.2P与NP相关问题233

8.5小结234

习题234

第9章上下文有关语言237

9.1图灵机与短语结构文法的等价性237

9.2线性有界自动机及其与上下文有关文法的等价性240

9.3小结241

习题241

附录缩写符号243

词汇索引245

参考文献251

前言FOREWORD
计算机科学与技术、软件工程、网络空间安全等计算机类学科，统称为计算学科。学科通过在计算机上建立模型和系统，模拟实际过程进行科学调查和研究；通过数据搜集、存储、传输与处理等进行问题求解，包括科学、工程、技术和应用4部分。其科学部分的核心在于通过抽象建立模型实现对计算规律的研究；其工程部分的核心在于根据规律低成本地构建从基本计算系统到大规模复杂计算应用系统的各类系统；其技术部分的核心在于研究和发明用计算进行科学调查和研究中使用的基本手段和方法；其应用部分在于构建、维护和使用计算系统实现特定问题的求解。其根本问题是“什么能且如何被有效地自动计算”，而计算的自动化，均以问题描述和处理的符号化为基础。从事计算机科学研究、工程设计、开发、运行、应用、维护的计算机人才都不例外。也正因为如此，才有人用“问题抽象”、“系统抽象”、“数据抽象”来表述对计算机类专业人才的基本要求。2016年6月2日，在吉隆坡召开的国际工程联盟大会上，中国获全票通过，正式加入《华盛顿协议》，成为第18个正式成员，这被认为是中国高等教育取得的具有里程碑意义的历史性突破。该协议虽然是针对本科教育的，但对我们按照工程教育的要求，不断提升研究生教育的水平与质量也是很重要的。根据《华盛顿协议》，工程被定义为包括数学、自然科学和工程知识、技术和技能整体的、有目的性的应用。可见，“工程”对基础的强调。另外，《华盛顿协议》还规定，两年制的专科教育旨在培养学生解决狭义工程问题的能力，三年制专科旨在培养学生解决广义工程问题的能力，本科教育则聚焦培养学生解决复杂工程问题的能力。所谓的复杂工程问题是满足如下条件的工程问题: (1) 必须运用深入的工程原理经过分析才可能解决；(2) 需求涉及多方面的技术、工程和其他因素，并可能相互有一定冲突；(3) 需要通过建立合适的抽象模型才能解决，在建模过程中需要体现出创造性；(4) 不是仅靠常用方法就可以完全解决的；(5) 问题中涉及的因素可能没有完全包含在专业标准和规范中；(6) 问题相关各方利益不完全一致；(7) 具有较高的综合性，包含多个相互关联的子问题。作为本科教育后继的研究生教育，显然应该在本科教育的基础上开展。但是目前存在的问题是，很多年来，由于各方面的限制，部分专业点的教育还很难说达到了这一基本定位的要求，表现出来的现象是，进入研究生阶段学习的学生在对“深入原理的掌握”、“分析方法的掌握”，从而具有“分析能力”以及“建立合适的抽象模型”并且“在建模过程中需要体现出创造性”等方面都存在一定的差距。建模能力是如此之重要，以至于《华盛顿协议》还明确要求包括机械、电子、化工、建筑等在内的所有工科专业的教育都要包括数学、数值分析、统计，以及计算机和信息科学关于形式化方面的基本内容，以支持学科问题的分析和建模（WK2:  (mathematics and computer)conceptuallybased mathematics, numerical analysis, statistics and formal aspects of computer and information science to support analysis and modeling applicable to the discipline）。作为培养工程应用型人才为主的计算机类学科专业，更应如此。而形式语言与自动机理论则是培养学生这些方面能力的非常恰当的重要载体。希望通过这类课程的教育，支持这一要求的达成，同时促进学生在基础理论上更好地达到我国学位条例中 “在本门学科上掌握坚实的基础理论和系统的专门知识”的要求。另外，从复杂工程问题的定义不难看出，解决这类问题，需要有扎实的基础理论和深入的“原理性”知识，同时要强调对基本理论的应用。所以，包括研究生教育在内，需要追求理论指导下的、非简单的、高水平实践能力的培养，以追求高水平动脑指挥下的问题求解（实践、动手）。落实到本教材对应的课程教育，绝不仅仅是要让学生掌握其基本知识，而是要以这些知识为载体，使学生掌握其中的思想和典型方法，培养他们模型描述和模型计算的意识和能力。为此，要开展研究型的教与学: 教师在对问题的研究中教，学生在对未知的研究中学，努力体现基于产出（outcomebased education，OBE）的基本教育观点，纠正基于课程的教育观点（curricularbased education，CBE）。为了达到这一目的，在本书的写作中，我们除了以定义、定理、算法的形式叙述基本概念和结论外，还尽力进行相关的问题分析。希望读者不要限于简单地记忆定义、定理和相应的算法，要通过深入的分析，掌握相关的知识、思想和方法。多提问题，多想问题，这样才能有真正的收获。本书是基于国家精品教材《形式语言与自动机》编著的，重点考虑了研究生教育的需求，全书共分9章。第1章介绍语言和文法，包括相关的基本概念、文法的构造、Chomsky体系、左线性文法和右线性文法。第2章讨论有穷状态自动机，包括有穷状态自动机的定义、描述、构造方法，确定的、非确定的、带空移动的有穷状态自动机以及与正则文法的等价性。第3章研究正则表达式及其与有穷状态自动机的等价性。第4章讨论正则语言的性质，包括正则语言的泵引理、封闭性、MyhillNerode定理、极小化、判定算法。第5章为上下文无关语言，包括文法二义性、派生树、化简、Chomsky范式和Greibach范式。第6章讨论下推自动机，包括基本定义和构造方法以及下推自动机与上下文无关文法的等价性。第7章是上下文无关语言的性质，包括上下文无关语言的泵引理、Ogden引理、封闭性、判定算法。第8章介绍图灵机，包括基本定义、接受的语言、构造技术、通用图灵机、ChurchTuring论题、图灵机的变形、可计算语言、不可判定性、PNP问题。第9章介绍上下文有关语言，包括图灵机与短语结构文法的等价性，以及线性界限自动机的定义及与上下文有关语言的关系。书中难免存在不足，请读者不吝赐教。联系地址: [email protected]。
作者2017年1月

评论