chen形式语言及自动机(1-2).ppt

形式语言与自动机理论Formal Languages and Automata Theory 陈圣波 上海大学计算机学院 schen@shu.edu.cn 要求 上课时间：每周二（6-8），13:05-15:50 考核方案：平时成绩30% 考试成绩70% 不迟到、早退 教材 蒋宗礼,姜守旭.形式语言与自动机理论(第2版).清华大学出版社. 2007年7月. 课程目的和基本要求 课程性质 技术基础 基础知识要求 数学分析（或者高等数学），离散数学 主要特点 抽象和形式化 理论证明和构造性 基本模型的建立与性质 课程目的和基本要求 本专业人员4种基本的专业能力 计算思维能力 算法的设计与分析能力 程序设计和实现能力 计算机软硬件系统的认知、分析、设计与应用能力 计算思维能力 逻辑思维能力和抽象思维能力 构造模型对问题进行形式化描述 理解和处理形式模型 课程目的和基本要求 知识 掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。 能力 培养学生的形式化描述和抽象思维能力。 使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。 主要内容 语言的文法描述。 RL RG、 FA、RE、RL的性质 。 CFL CFG(CNF、GNF)、PDA、CFL的性质。 TM 基本TM、构造技术、TM的修改。 CSL CSG、LBA。 教材及主要参考书目 蒋宗礼，姜守旭. 形式语言与自动机理论(第2版). 北京：清华大学出版社，2007年. John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Prentice Hall. September 10, 2006. 第1章? 绪论 1.1 集合的基础知识 1.1.1 集合及其表示 集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set)，简称为集(set)。 元素：集合的成员为该集合的元素(element)。 集合描述形式。 基数。 集合的分类。 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 1.1.2 集合之间的关系 集合相等 如果集合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，则|B||A|。 1.1.2 集合之间的关系 ⑸ 如果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)是一个集合，该集合中的元素要么是A的元素，要么是B的元素，记作A∪B。 A∪B={a|a∈A或者a∈B} A1∪A2∪…∪An={a|?i，1≤i≤n，使得a∈Ai} A1∪A2∪…∪An ∪…={a|?i，i∈N,使得a∈Ai} 交(intersection) 集合A和B中都有的所有元素放在一起构成的集合为A与B的交 ，记作A∩B。 A∩B={a|a∈A且a∈B} “∩”为交运算符，A∩B读作A交B。 如果A∩B=Φ，则称A与B不相交。 ⑴ A∩B= B∩A。 ⑵ (A∩B)∩C=A∩(B∩C)。 ⑶ A∩A=A。 交(intersection