有限自动机理论CH.ppt
《有限自动机理论CH.ppt》由会员分享,可在线阅读,更多相关《有限自动机理论CH.ppt(178页珍藏版)》请在三一办公上搜索。
1、有限自动机理论06016004,陈文宇 电子科技大学计算机科学与工程学院,联系方式,cwyB1-513,学时:(前8周)学分:考试:闭卷、笔试考查:作业(3-4次),不参加考试,教材:,有限自动机理论 陈文宇 电子科技大学出版社 2007.3,参考书,形式语言与自动机理论(第2版)(蒋宗礼 姜守旭 清华大学出版社)形式语言与自动机(陈有祺 机械工业出版社),参考书,Introduction to Automata Theory,Languages,and Computation(Second Edition)自动机理论、语言和计算导论(John E.Hopcroft 清华大学出版社),理论来源
2、,形式语言和自动机的理论来源于(1)Chomsky对自然语言的研究;(2)ALGOL 60语言的语法描述方式;(3)Turing、Kleene、Neumann、Huffman等 对自动机的研究。,形式语言与自动机的作用,形式语言和自动机的理论已经成为计算机科学的理论基础。应用范围已被扩展到生物工程、自动控制系统、图象处理与模式识别等许多领域。,计算机学科的专业能力,计算思维能力 算法设计与分析能力 程序设计与实现能力 计算机系统的认知、分析、设计和运用能力,计算(机)思维能力,形式化描述能力抽象思维能力逻辑思维方法,相关理论是计算机学科基础。理论方面的知识是计算机科学的真正灵魂。这也是计算机科
3、学与其他学科的重要区别。,有限自动机理论在科学领域中得到直接应用 对于计算机科学人才的计算思维能力的培养,也具有重要作用。,在本科阶段,以 观察、描述、比较 分类、推断、应用的科学思维过程为主。,研究生阶段,需要进一步进行抽象思维、逻辑思维、创造思维能力的培养。本科生与研究生的根本区别在于研究生的需要 宽厚、坚实的理论知识。,第1章 基础知识,本章将对有限自动机理论中所需的数学基础知识作扼要的介绍。包括集合及其运算、关系、证明的方法、图与树的概念;以及一些常用术语 和 形式语言与自动机的发展。,内容:,1.1集合及其运算1.2 关系1.3 证明和证明的方法1.4 图与树 1.5 语言1.6 常
4、用术语 1.7 形式语言与自动机的发展,1.1 集合及其运算,一些没有重复的对象的全体称为集合,而这些被包含的对象称为该集合的元素。集合中元素可以按任意的顺序进行排列。使用大写英文字母表示一个集合。,有穷集合和无穷集合,如果一个集合包含的元素个数是有限的,称该集合为有穷集合。如果一个集合包含的元素是无限的,称该集合为无穷集合。无穷集合又分为可数集(如正奇数集)和不可数集(如实数集)。,集合的定义方法:,列举法命题法,列举法(穷举法),对于有穷的,且元素个数较少的集合,可以采用列举法,即将集合的所有元素全部列出,并放在一对花括号中。例 集合A=1,2,3,4,5,对于某些无穷集合,也可以使用类似
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中的每个元素都
6、是集合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的并,记为AB。集合A的所有元素和集合B的所有元素合并在一起组成的集合。AB=x|xA 或 xB,思考:,什么情况下:AB=A?,集合A与集合B的交,记为AB 是由集合A和集合B的所有公共元素组成的集合。AB=x|xA 且 xB,思考:,什么情况下:A B=A?,集合A与集合B的差,记为AB 属于集合A但不属于集合B的所有元素组成的集
7、合。AB=x|xA 且 x B,思考:,什么情况下:A-B=A?,如果B A,将AB称为集合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,幂集2A的元素个数,当集合A为有穷集时,如果|A|=n,那么A的幂集2A的元素个数(集合A的所有子集的个数)为2n。(集合A的幂集表示为2A的原因),定义1-4 笛卡儿积,集合A和B的笛卡儿乘积 A B(也简记为AB)A B=(a,b)|a A且b B
8、 当集合A、B为有穷集时|A B|=|A|*|B|,例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,2,3,5,1,2,3,4注意:没有5,5,1.2 关系,1.2.1 二元关系1.2.2 等价关系与等价类1.2.3 关系的合成,1.2.1
9、 二元关系,设A和B为两个集合,则A B的任何一个子集称为A到B的一个二元关系。若R为A到B的关系,当(a,b)R时,可记为aRb。若A=B,则称为A上的关系。,思考:,如果集合A和B都是有穷集合,则 A到B的二元关系有多少个?A到B的一个二元关系可以有多少个元素?,例1-3,设A为正整数集合,则A上的关系“”是集合(a,b)|a,b A,且a b=(1,2),(1,3),(1,4),.(2,3),(2,4),(2,5),.,1.2.2 等价关系,设R是A上的二元关系(1)如果对于a A,都有(a,a)R 则称R是自反的。,(2)如果对于a,b A(a,b)R(b,a)R 则称R是对称的。,(
10、3)若对a,b,c A(a,b)R且(b,c)R(a,c)R 则称R为传递的。,定义1-6,如果集合A上的二元关系R是自反的、对称的和传递的 则称R为等价关系。,等价关系的性质,等价关系的一个重要性质为:集合A上的一个等价关系R可以将集合A划分为若干个互不相交的子集-等价类,对A中的每个元素a,使用a表示a的等价类,即a=b|aRb。等价关系R将集合A划分成的等价类的数目-等价关系的指数。,例1-3,自然数集合N上的模3同余关系 R=(a,b)|a,b N,且 a mod 3=b mod 3。是一个等价关系。,0,3,6,3n,第1个等价类;1,4,7,3n+1,第2个等价类;2,5,8,3n
11、+2,第3个等价类;分别记为0,1和2。,N=0 1 2等价关系的指数为3,1.2.3 关系的合成,关系可以进行合成。,定义1-7,设R1 A B是A到B的(二元)关系 R2 B C是B到C 的(二元)关系R1与R2的合成是A到C的(二元)关系 R1R2=(a,c)|(a,b)R1且(b,c)R2,例1-5,R1和R2的是集合1,2,3,4上的关系R1=(1,1),(1,2),(2,3),(3,4)R2=(2,4),(4,1),(4,3),(3,1),(3,4)则R1R2=(1,4),(2,1),(2,4),(3,1),(3,3)R2R1=(4,1),(4,2),(4,4),(3,1),(3,
12、2),定义1-8 关系的n次幂,设R是S上的二元关系,则Rn递归定义为:(1)R0=(a,a)|a S(2)Ri=Ri-1 R(i=1,2,3,),定义1-9 关系的闭包,设R是S上的二元关系,R的正闭包R+为(1)R R+;(2)若(a,b),(b,c)R+,则(a,c)R+;(3)除(1),(2)外,R+不再含有其他任何元素。,普通定义:R+,R+=R R2 R3,且当S为有穷集时,有R+=R R2 R3 R|s|,关系的克林闭包,R*=R0 R+,例1-6,设R1=(a,b),(c,d),(b,d),(b,b),(d,e)R2=(a,a),(b,c),(d,c),(e,d),(c,a)则
13、R1 R2=(a,c),(c,c),(b,c),(d,d),R1+=(a,b),(c,d),(b,d),(b,b),(d,e),(a,d),(a,e),(c,e),(b,e)R1*=(a,a),(b,b),(c,c),(d,d),(e,e)R1+,1.3 证明和证明的方法,形式语言和有限自动机有很强的理论性,许多的论断以定理的形式进行描述,而定理的正确性是需要进行证明的。形式语言和有限自动机理论中定理的证明普遍使用反证法和归纳法,1.3.1 反证法1.3.2 归纳法1.3.3 递归定义与归纳证明,1.3.1反证法(归谬法),利用反证法证明一个命题时,一般的步骤为:(1)假设该命题不成立;(2)
14、进行一系列的推理;(3)在推理的过程中如果出现了下列情况之一:,与已知条件矛盾;与公理矛盾;与已证过的定理矛盾;与临时的假定矛盾;自相矛盾;,反证法(续),由于上述矛盾的出现,可以断言“假设该命题不成立”的假设不正确;从而肯定原命题正确。,反证法(续),反证法例子,是无理数。,演绎与归纳,演绎是从普遍性的理论知识出发,去认识个别的、特殊的现象的一种逻辑推理方法。演绎的基本形式是三段论。归纳是根据个别的、特殊的现象,得到普遍性知识的逻辑推理方法。,1.3.2 归纳法,归纳法是从特殊到一般的逻辑推理方法。分为完全归纳法和不完全归纳法两种形式。,完全归纳法是根据一切情况的分析而作出的推理。由于必须考
15、虑所有的情况,得出的结论是完全可靠的。,归纳法(续),不完全归纳法是根据一部分情况作出的推理。不能作为严格的证明方法。,在自动机理论中,普遍使用数学归纳法证明某个命题。,数学归纳法可以使用“有限步骤”解决“无限”问题。,数学归纳法,对于一切非负整数n的 命题M(n)(1)M(0)为真;(2)假设对于任意的k 0,M(k)为真,能够证明M(k+1)为真(3)则对一切n 0,M(n)为真。,第(1)步称为归纳基础 第(2)步称为归纳步骤 第(2)步中“设对于任意的k 0,M(k)为真”,称为归纳假设,数学归纳法的简化,对于0,证明结论成立;假设结论对于n成立,证明结论对于n成立。,1.3.3 集合
16、递归定义与归纳证明,递归定义(1)基础(2)归纳(3)极小性限定(有限性),递归定义集合步骤,(1)基础:首先定义该集合中最基本的元素 x1,x2,x3,xm,(2)归纳:对于该集合中的元素 x1,x2,x3,xn 使用某种组合方法对这些元素进行处理后所得的新元素在该集合中,(3)有限性:只有满足(1)和(2)的元素才在集合中,递归定义集合的优点,除集合的基本元素(直接定义)外 集合中的元素的产生遵从相同的规律。,例1-6 Fibonacci数,Fibonacci数组成的集合为:0,1,1,2,3,5,8,13,21,34,55,(1)基础:0和1是最基本的两个元素;(2)归纳:若m是第i个元
17、素,n是第i+1个元素 则第i+2个元素为n+m;(3)只有满足(1)和(2)的数,才是集合的元素,例,括号匹配的串构成的集合的定义(),()(),(),(1)基础:()是最基本的串,(2)归纳:若S是括号匹配的串,则(S)是括号匹配的串 若S是括号匹配的串,则SS是括号匹配的串,练习,给出下列对象的递归定义 字符串的倒序,1.4 图与树,1.3.1 无向图1.3.2 有向图1.3.3 树,图,现实世界中,许多问题可以抽象成图来表示。直观地,图是由一些点和连接两点的边组成的。,定义1-10无向图,设V是一个非空的有穷集合 E V V 称G=(V,E)为一个无向图。其中,V称为顶点集 E称为无向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有限 自动机 理论 CH

链接地址:https://www.31ppt.com/p-5990379.html