形式语言与自动机 讲稿.doc

形式语言与自动机理论 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下推自动机） ? 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. 形式语言与自动机形式语言与自动机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相等(equivalence)，记作A=B。 对任意集合A、B、C： ⑴ A=B iff A(B且B(A。 ⑵ 如果A(B，则|A|≤|B|。 ⑶ 如果A(B，则|A|≤|B|。 ⑷ 如果A是有穷集，且A(B，则|A||B|。 ⑸ 如果A(B，则对(x∈A，有x∈B。 ⑹ 如果A(B，则对(x∈A，有x∈B并且(x∈B，但x(A。 ⑺ 如果A(B且B(C，则A(C。 ⑻ 如果A(B且B(C，或者A(B且B(C，或者A(B且B(C，则A(C。 ⑼ 如果A=B，则|A|=|B|。 1.1.3 集合的运算 ? 并(union) A与B的并(union)是一个集合，该