形式语言与自动机 -1到5章-清华大学出版社.docVIP

形式语言与自动机 -1到5章-清华大学出版社 形式语言与自动机理论 Formal Languages and Automata Theory 课程目的和基本要求 ? 课程性质 ? 基础知识要求 ? 主要特点 数学分析（或者高等数学），离散数学 抽象和形式化 理论证明和构造性 基本模型的建立与性质 技术基础 ? 本专业人员4种基本的专业能力 计算思维能力 算法的设计与分析能力 程序设计和实现能力 计算机软硬件系统的认知、分析、设计与应用能力 逻辑思维能力和抽象思维能力 构造模型对问题进行形式化描述 理解和处理形式模型 ? 计算思维能力 ? 知识 ? 能力 掌握正则语言、上下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。 培养学生的形式化描述和抽象思维能力。 使学生了解和初步掌握―问题、形式化描述、自动化（计算机化）‖这一最典型的计算机问题求解思路。 主要内容 ? 语言的文法描述。 ? RL（Regular Language正则语言） RG（Regular Grammar正则文法）、FA（Finite Automation有穷状态自动机）、RE（Regular Expression正则表达式）、RL的性质。 ? CFL（Context Free Language上下文无关语言） CFL–CFG(CNF、GNF)、PDA、CFL的性质。 CFG（Context Free Grammar上下文无关文法） CNF（Chomsky Normal Form乔姆斯基范式） GNF（Greibach Normal Form格雷巴赫范式） PDA（Pushdown Automation下推自动机） 1 ? TM（Turing Machine图灵机） 基本TM、构造技术、TM的修改。 CSL（Context Sensitive Language上下文有关语言） CSG（Context Sensitive Grammar上下文有关文法）、LBA（Linear Bounded Automation线性有界自动机）。 教材及主要参考书目 [1] 蒋宗礼，姜守旭. 形式语言与自动机理论. 北京：清华大学出版社，2003年 [2] John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman. 自动机理论、语言和计算导论（原书第三版）. 北京: 机械工业出版社, 2008. John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Publishing Company, 2006 [3] Thomas A. Sudkamp. 语言与机器: 计算机科学理论导论（原书第三版）. 北京: 机械工业出版社, 2008. [4] Peter Linz. 形式语言与自动机导论（原书第三版）. 北京: 机???工业出版社, 2005. [5] 陈有祺. 形式语言与自动机理论. 北京: 机械工业出版社, 2008. 第1章 绪论 1.1 集合的基础知识 1.1.1 集合及其表示 ? 集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set)，简称为集(set)。 ? 元素：集合的成员为该集合的元素(element)。 N——自然数集 Q——有理数集 R——实数集 Σ——字母集 ? 集合描述形式：列举法{1,3,5,…}、命题法{x|3x2+8x+4=0}。 ? 基数（势）|A|。 ? 集合的分类：空集Φ、有限（穷）集、无穷集、可数集、不可数集。 1.1.2 集合之间的关系 ? 子集 如果集合A的每个元素都是集合B的元素，则称集合A是集合B的子集(subset)，集合B是集合A的包集(container)。记作A?B。也可记作B?A。A?B读作集合A包含在集合B中；B?A读作集合B包含集合A。 如果A?B，且?x∈B，但x?A，则称A是B的真子集(proper subset)，记作A?B ? 集合相等 如果集合A，B含有的元素完全相同，则称集合A与集合B相等 2 (equivalence)，记作A=B。 对任意集合A、B、C： ⑴ A=B iff A?B且B?A。 ⑵