有限自动机理论CH1.ppt

有限自动机理 陈文宇 电子科技大学计算机科学与工程学院 联系方式 cwy@uestc.edu.cnB1-513 学时：４０（前8周） 学分：２ 考试：闭卷、笔试 考查：作业(3-4次)，不参加考试 教材： 有限自动机理论 陈文宇 电子科技大学出版社 2007.3 参考书 形式语言与自动机理论(第2版) （蒋宗礼 姜守旭 清华大学出版社） 形式语言与自动机 （陈有祺 机械工业出版社） 参考书 Introduction to Automata Theory, Languages, and Computation (Second Edition) 自动机理论、语言和计算导论 （John E. Hopcroft 清华大学出版社） 理论来源 形式语言和自动机的理论来源于 (1) Chomsky对自然语言的研究； (2) ALGOL 60语言的语法描述方式； (3)Turing、Kleene、Neumann、Huffman等 对自动机的研究。 形式语言与自动机的作用 形式语言和自动机的理论已经成为计算机科学的理论基础。 应用范围已被扩展到生物工程、自动控制系统、图象处理与模式识别等许多领域。 计算机学科的专业能力 计算思维能力 算法设计与分析能力 程序设计与实现能力 计算机系统的认知、分析、 设计和运用能力 计算(机)思维能力 形式化描述能力 抽象思维能力 逻辑思维方法 相关理论是计算机学科基础。 理论方面的知识是计算机科学的真正灵魂。 这也是计算机科学与其他学科的重要区别。 有限自动机理论在科学领域中得到直接应用 对于计算机科学人才的计算思维能力的培养，也具有重要作用。 在本科阶段, 以 观察、描述、比较 分类、推断、应用 的科学思维过程为主。 研究生阶段，需要进一步进行抽象思维、逻辑思维、创造思维能力的培养。 本科生与研究生的根本区别在于研究生的需要 宽厚、坚实的理论知识。 　　第1章 基础知识 本章将对有限自动机理论中所需的数学基础知识作扼要的介绍。 包括集合及其运算、关系、证明的方法、图与树的概念；以及一些常用术语 和 形式语言与自动机的发展 。 内容： 1.1集合及其运算 1.2 关系 1.3 证明和证明的方法 1.4 图与树 1.5 语言 1.6 常用术语 1.7 形式语言与自动机的发展 1.1 集合及其运算 一些没有重复的对象的全体称为集合，而这些被包含的对象称为该集合的元素。 集合中元素可以按任意的顺序进行排列。 使用大写英文字母表示一个集合。 有穷集合和无穷集合 如果一个集合包含的元素个数是有限的，称该集合为有穷集合。 如果一个集合包含的元素是无限的，称该集合为无穷集合。 无穷集合又分为可数集(如正奇数集)和不可数集(如实数集)。 集合的定义方法： 列举法 命题法 列举法(穷举法) 对于有穷的，且元素个数较少的集合，可以采用列举法，即将集合的所有元素全部列出，并放在一对花括号中。 例 集合A ={1，2，3，4，5} 对于某些无穷集合，也可以使用类似列举的方法进行描述 如自然数集合： {0，1，2，3，…} 命题法 对于集合元素较多的有穷集合或者是无穷集合，可使用集合元素的形成模式 {x | P(x)} 进行描述。 其中：x表示集合中的任一元素, P(x)是一个谓词，对x进行限定。 {x | P(x)} 表示 由满足P(x)的一切x构成的集合。 可以使用自然语言，或者数学表示法来描述谓词P(x)。 例如： {n | n是偶数}　　或 {n | n mod 2 = 0} 表明了由所有偶数组成的集合。 集合的基数 若集合A包含元素x，记为x ? A 反之， x ? A 对于有穷集合A，使用|A|表示该集合包含的元素的个数，也称基数或势 |A| = 0 ? A = ? 。 定义1-1 子集 设A, B是两个集合，如果集合A中的每个元素都是集合B的元素，则称集合A是集合B的子集(集合B是集合A的包集) A ? B 或 B ? A A, B是两个集合，如果A ? B，且?x ? B，但x ? A，则称A是B的真子集 A ? B 两个集合相等，当且仅当 A ? B且B ? A 注意： 不是A ? B且B