有限自动机理论01章基础知识

1、有限自动机理论有限自动机理论06016004 陈文宇陈文宇 电子科技大学计算机科学与工程学院电子科技大学计算机科学与工程学院 联系方式联系方式主楼主楼B1-509 课件下载：计算机学院网站课件下载：计算机学院网站-师资队伍师资队伍 -陈文宇陈文宇 课程情况课程情况 学时：学时：40（前前10周周） 学分：学分： 考试：作业（考试：作业（20%） 笔试笔试 （80%） 大概大概10周周 考查：作业考查：作业 （100%） 教材： 有限自动机理论（有限自动机理论（2 2版）版） 陈文宇陈文宇 田玲田玲 程伟程伟 刘贵松刘贵松 电子工业出版社电子工业出版社 2013.082

2、013.08 参考书参考书 形式语言与自动机理论形式语言与自动机理论(第第2版版) 蒋宗礼蒋宗礼 姜守旭姜守旭 清华大学出版社清华大学出版社2007 形式语言与自动机形式语言与自动机 陈有祺陈有祺 机械工业出版社机械工业出版社2008 参考书参考书 Introduction to Automata Theory, Languages, and Computation (Second Edition) 自动机理论、语言和计算导论自动机理论、语言和计算导论 （John E. Hopcroft 机械工业出版社）机械工业出版社） 理论来源理论来源 形式语言和自动机的理论来源于形式语言和自动机的理论来源

3、于 (1) Chomsky对自然语言的研究；对自然语言的研究； (2) ALGOL 60语言的语法描述方式；语言的语法描述方式； (3)Turing、Kleene、Neumann、Huffman 等等 对自动机的研究。对自动机的研究。 形式语言与自动机的作用形式语言与自动机的作用 形式语言和自动机的理论已经成形式语言和自动机的理论已经成 为计算机科学的为计算机科学的理论基础理论基础。 应用范围已被扩展到应用范围已被扩展到生物工程生物工程、 自动控制系统自动控制系统、图像图像处理处理与与模式识模式识 别别等许多领域。等许多领域。 计算机学科的专业能力 计算思维计算思维能力能力 算法设计与分析算法

4、设计与分析能力能力 程序设计与实现程序设计与实现能力能力 计算机系统的认知、分析、计算机系统的认知、分析、 设计和运用设计和运用能力能力 计算思维能力计算思维能力 形式化描述形式化描述(问题问题)能力能力 抽象思维抽象思维能力能力 逻辑思维逻辑思维能力能力 计算机学科的专业能力 相关理论是计算机学科基础。相关理论是计算机学科基础。 理论方面的知识是计算机科学的理论方面的知识是计算机科学的 灵魂。灵魂。 这也是计算机科学与其他学科的这也是计算机科学与其他学科的 重要区别。重要区别。 有限自动机理论有限自动机理论在科学领域中得在科学领域中得 到直接应用到直接应用 对于计算机学科人才的对于计算机学科

5、人才的计算思维计算思维 能力的培养能力的培养，也具有重要作用。，也具有重要作用。 研究生阶段研究生阶段 需要进一步进行需要进一步进行抽象思维抽象思维、逻辑逻辑 思维思维、创造能力创造能力的培养。的培养。 需要需要更更宽厚、坚实的宽厚、坚实的理论基础理论基础。 第第1章章 基础知识基础知识 本章将对有限自动机理论中所需本章将对有限自动机理论中所需 的的数学基础知识数学基础知识作作扼要的介绍扼要的介绍。 包括集合及其运算、关系、证明包括集合及其运算、关系、证明 的方法、图与树的概念；的方法、图与树的概念；常用术语常用术语 和形式语言与自动机的发展和形式语言与自动机的发展 。 内容：内容： 1.1

6、集合及其运算集合及其运算 1.2 关系关系 1.3 证明和证明的方法证明和证明的方法 1.4 图与树图与树 1.5 语言语言 1.6 常用术语常用术语 1.7 形式语言与自动机的发展形式语言与自动机的发展 1.1 集合及其运算集合及其运算 一些一些没有重复没有重复的对象的全体称为的对象的全体称为 集合集合，而这些被包含的对象称为该而这些被包含的对象称为该 集合的集合的元素元素。 集合中元素可以按集合中元素可以按任意的顺序任意的顺序进进 行排列。行排列。 使用使用大写英文字母大写英文字母表示一个集合。表示一个集合。 如何删 除 指 定如何删 除 指 定 位置元素？位置元素？数组数组 链表链表 有

7、穷集合有穷集合和和无穷集合无穷集合 如果一个集合包含的元素个数是有如果一个集合包含的元素个数是有 限的，称该集合为限的，称该集合为有穷有穷集合集合。 如果一个集合包含的元素是无限的，如果一个集合包含的元素是无限的， 称该集合为称该集合为无穷无穷集合集合。 无穷集合又分为无穷集合又分为可数集可数集(也称为也称为可列可列 集，集，如正奇数集如正奇数集)和和不可数集不可数集(如实数集如实数集)。 集合的定义方法：集合的定义方法： 列举列举法法 命题命题法法 列举法列举法(穷举法穷举法) 对于有穷的，且元素个数较少的对于有穷的，且元素个数较少的 集合，可以采用列举法，集合，可以采用列举法，即将集合即将

8、集合 的所有元素全部列出的所有元素全部列出，并放在一对，并放在一对 花括号中。花括号中。 例如例如 集合集合A =1，2，3，4，5 对于某些无穷集合，也可以使用对于某些无穷集合，也可以使用类似类似 列举列举的方法进行描述的方法进行描述 如自然数集合：如自然数集合： 0，1，2，3， 命题法命题法 对于集合元素较多的有穷集合或者是对于集合元素较多的有穷集合或者是 无穷集合，可使用集合元素的形成模式无穷集合，可使用集合元素的形成模式 x | P(x) 进行描述。进行描述。 其中：其中：x表示集合中的任一元素表示集合中的任一元素, P(x)是是 一个一个谓词谓词，对，对x进行限定。进行限定。 用来

9、描述或判定客体性质、用来描述或判定客体性质、 特征的词项。特征的词项。 x | P(x) 表示表示 由满足由满足P(x)的一切的一切x构成的集合。构成的集合。 可以使用自然语言，或者数学表可以使用自然语言，或者数学表 示法来描述（表达）谓词示法来描述（表达）谓词P(x) 例如： n | n是偶数是偶数或或 n | n mod 2 = 0 描述了由所有偶数组成的集合。描述了由所有偶数组成的集合。 集合的基数集合的基数 若集合若集合A包含元素包含元素x，记为记为x A 反之，反之， x A 对于有穷集合对于有穷集合A，使用使用|A|表示该集表示该集 合包含的元素的合包含的元素的个数个数，也称，也称

10、基数基数或或势势 |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 A 定义定义1-2 集合的运算集合的运算 集合集合A与集合与集合B的的并运算并运算，记为，

11、记为AB 集合集合A的所有元素和集合的所有元素和集合B的所有的所有 元素元素合并合并在一起组成的集合。在一起组成的集合。 AB=x | xA 或或 xB 思考： 什么情况下：什么情况下： AB=A ？ 集合集合A与集合与集合B的的交运算交运算，记为，记为AB 是由集合是由集合A和集合和集合B的所有的所有公共元素公共元素 组成的集合。组成的集合。 AB= x | xA 且且 xB 思考： 什么情况下：什么情况下： A B=A ？ 集合集合A与集合与集合B的的差运算差运算，记为，记为A B 属于属于集合集合A但但不属于集合不属于集合B的所有元的所有元 素组成的集合。素组成的集合。 A B= x |

12、xA 且且 x B 思考思考: 什么情况下：什么情况下： A - B=A ？ 如果如果B A，将，将A B称为集合称为集合B（关（关 于集合于集合A）的）的补运算补运算。 集合集合A称为集合称为集合B的全集（或的全集（或论域论域） 定义定义1-3 幂集幂集 设设A为一个集合，那么为一个集合，那么A的的幂集幂集 为为A的所有子集的所有子集组成的集合组成的集合 记为记为2A 2A=B | B A 例1-1 集合集合A=1，2，3，则则A的幂集为的幂集为: 2A= ， 1，2，3， 1，2，1，3，2，3， 1，2，3 任取其中任取其中2个元素构成的集合个元素构成的集合 幂集幂集2A的元素个数的元素

13、个数 当当集合集合A为有穷集为有穷集时，如果时，如果|A|=n， 那么那么A的幂集的幂集2A的元素个数的元素个数(集合集合A的的 所有子集的个数所有子集的个数)为为2n。 （集合（集合A的幂集表示为的幂集表示为2A的原因）的原因） 无论集合无论集合A A是有穷集合，还是无穷集合，都使用是有穷集合，还是无穷集合，都使用2 2A A 表示集合表示集合A A的幂集。的幂集。 定义定义1-4 笛卡儿积笛卡儿积 集合集合A和和B的的笛卡儿笛卡儿乘积乘积 A B（也简记为（也简记为AB） A B = (a, b) |a A且且b B 当当集合集合A、B为有穷集为有穷集时时 |A B|= |A| *| B|

14、 例例1-2 设设A = a, b, c, B = 0, 1, 则则A B =(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1) B A=(0, a), (0, b), (0, c), (1, a), (1, b), (1, c) 也可根据约定记为：也可根据约定记为： A B=a0, a1, b0, b1, c0, c1 思考思考 什么情况下：什么情况下： A B = B A ? 练习练习 110之间的和为之间的和为10的整数的整数集集 合的集合合的集合 1, 9, 2, 8, 3, 7, 4, 6, 1, 2, 7, 1, 3, 6, 1, 4, 5

15、, 2, 3, 5, 1, 2, 3, 4 注意：注意：没有没有5，5 10，010 1.2 关系关系 1.2.1 二元关系二元关系 1.2.2 等价关系等价关系与等价类与等价类 1.2.3 关系的关系的合成合成 1.2.1 二元关系二元关系 设设A和和B为两个集合，则为两个集合，则A B 的的任何一个子集任何一个子集称为称为A到到B的一的一 个二元关系。个二元关系。 若若R为为A到到B的关系，当的关系，当 (a, b) R时，可记为时，可记为aRb 若若A = B ，则称则称R为为A上上的关系的关系 思考：思考： 如果集合如果集合A和和B都是有穷集合，则都是有穷集合，则 A到到B的的二元关系

16、有多少个二元关系有多少个？ A到到B的一个二元关系的一个二元关系 最多最多可以有多少个元素可以有多少个元素？ 最少最少可以有多少个元素可以有多少个元素 例例1-3 设设A为正整数集合，则为正整数集合，则A上的上的“” 关系是集合关系是集合 (a, b) | a, b A,且且a 0n0 (5) 用用AB代表集合代表集合A与与B的连接的连接 A=a1,a2,a3,an B=b1,b2,b3,bm AB= a1b1，a1b2，a1b3，a1bm， a2b1，a2b2，a2b3，a2bm， a3b1，a3b2，a3b3，a3bm， anb1，anb2，anb3，anbm 注意： A=A= 一般，一般

17、，AB与与BA是不相等的。是不相等的。 思考思考: AB与与BA在什么情况下相等在什么情况下相等? 1)当当 A=B； 2)A或或B中有一个为中有一个为,则则 A=A=A 3)A和和B中有一个为中有一个为，则则 A=A= 6)An代表集合代表集合A的的n次连接次连接(幂幂) A的的n次次幂幂定义为：定义为： (1) A0 = (2) An = An-1A n 1 7) A*代表代表A上所有字符串的集合上所有字符串的集合 即表示集合即表示集合A中的所有字符串进中的所有字符串进 行行任意次任意次 连接连接而形成的串的集合而形成的串的集合 A*称为集合称为集合A的闭包的闭包(克林闭包克林闭包) A*

18、 = A0 A1 A2 An 例 A=0，1 A0= 即即长度为长度为0的的0和和1组成的串的集合组成的串的集合 A1=A=0,1 即即长度为长度为1的的0和和1组成的串的集合组成的串的集合 A2=AA=00,01,10,11 即即长度为长度为2的的0和和1组成的串集合组成的串集合 A3=A2A =000,001,010,011,100,101,110,111 即即长度为长度为3的的0和和1组成的串的集合组成的串的集合 A* = A0 A1 A2 An =0和和1 组成的所有的串组成的所有的串 =w|w是是0和和1 组成的串组成的串 如果串如果串是集合是集合A的闭包中的串，的闭包中的串， 也称

19、也称是集合是集合A上的串上的串。 对于任何集合对于任何集合A 有有(A*)*= A* 8) A+称为称为A的正闭包的正闭包 A+=AA2A3An A * 与 A+ A * = A+ A0 即即 A * = A+ 注意：注意： A0= *= += *= += 思考思考 是否对于任意的集合是否对于任意的集合A，都有都有 A+= A*- 辨析与思考辨析与思考与 | |=1 |=0 A=A A= 9）给定字母表）给定字母表，则，则*的任意的任意子集子集 L称为字母表称为字母表上的一个语言。上的一个语言。 本质上，本质上，语言语言L是是字母表字母表上的上的 字符串形成的字符串形成的集合集合。 语言的可分

20、为语言的可分为有穷语言有穷语言与与无穷语言无穷语言 10)设设 是一个字母表，是一个字母表， L *, x L, x称为称为L的一个的一个句子句子。 语言的乘积语言的乘积 设设 1, 2是两个字母表是两个字母表 L1 1*, L2 2*, 语言语言L1与与L2的乘积是一个语言：的乘积是一个语言： L1L2=xy | x L1, y L2 该语言是字母表该语言是字母表 1 2 上的语言上的语言 语言的例子语言的例子 字母表字母表 0, 1上的一些语言：上的一些语言： 00, 11 10, 1* 00, 1*1 0, 1*1110, 1* 语言的语言的n次幂次幂 设设 是一个字母表，是一个字母表，

21、 L *, L的的n次幂也是一个语言次幂也是一个语言 (1) 当当n = 0时，时， L0 = (2) 当当n 1时，时， Ln = Ln-1 L 语言的例子语言的例子 令令 = 0, 1 L = 0, 1 L = 0, 1, 00, 01, 10, 11, = + L = , 0, 1, 00, 01, 10, 11, = * L = 0n1n | n 1 L = 0n1m0k | n, m, k 1 L = 0n1m0k | n, m, k 0 语言的闭包语言的闭包 L的正闭包的正闭包L+是一个语言：是一个语言： L+ = L L2 L3 L的克林闭包的克林闭包L*是一个语言：是一个语言： L* = L0 L+ 1.7形式语言与自动机的发展形式语言与自动机的发展 （自学）（