有限自动机理论1章基础知识.ppt
《有限自动机理论1章基础知识.ppt》由会员分享,可在线阅读,更多相关《有限自动机理论1章基础知识.ppt(171页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、有限自动机理论有限自动机理论06016004陈文宇陈文宇电子科技大学计算机科学与工程学院电子科技大学计算机科学与工程学院联系方式联系方式cwy主楼主楼B1-509课件下载:计算机学院网站课件下载:计算机学院网站-师资队伍师资队伍-陈文宇陈文宇课程情况课程情况学时:学时:40(前前10周周)学分:学分:考试:闭卷、笔试考试:闭卷、笔试大概大概10周考试周考试作业作业20%+考试考试80%考查:作业考查:作业100%不参加考试不参加考试教材:有限自动机理论(有限自动机理论(2 2版)版)陈文宇陈文宇 田玲田玲 程伟程伟 刘贵松刘贵松 电子工业出版社电子工业出版社 2013.082013.08参考书
2、参考书形式语言与自动机理论形式语言与自动机理论(第第2版版)蒋宗礼蒋宗礼姜守旭姜守旭清华大学出版社清华大学出版社2007形式语言与自动机形式语言与自动机陈有祺陈有祺机械工业出版社机械工业出版社2008参考书参考书IntroductiontoAutomataTheory,Languages,andComputation(SecondEdition)自动机理论、语言和计算导论自动机理论、语言和计算导论(JohnE.Hopcroft机械工业出版社)机械工业出版社)理论来源理论来源形式语言和自动机的理论来源于形式语言和自动机的理论来源于(1)Chomsky对自然语言的研究;对自然语言的研究;(2)AL
3、GOL60语言的语法描述方式;语言的语法描述方式;(3)Turing、Kleene、Neumann、Huffman等等 对自动机的研究。对自动机的研究。形式语言与自动机的作用形式语言与自动机的作用形形式式语语言言和和自自动动机机的的理理论论已已经经成成为计算机科学的为计算机科学的理论基础理论基础。应应用用范范围围已已被被扩扩展展到到生生物物工工程程、自自动动控控制制系系统统、图图像像处处理理与与模模式式识识别别等许多领域。等许多领域。计算机学科的专业能力 计算思维计算思维能力能力 算法设计与分析算法设计与分析能力能力 程序设计与实现程序设计与实现能力能力 计算机系统的认知、分析、计算机系统的认
4、知、分析、设计和运用设计和运用能力能力计算思维能力形式化描述能力形式化描述能力抽象思维能力抽象思维能力逻辑思维方法逻辑思维方法计算机学科的专业能力 相关理论是计算机学科基础。相关理论是计算机学科基础。理论方面的知识是计算机科学的理论方面的知识是计算机科学的灵魂。灵魂。这也是计算机科学与其他学科的这也是计算机科学与其他学科的重要区别。重要区别。有有限限自自动动机机理理论论在在科科学学领领域域中中得得到直接应用到直接应用对对于于计计算算机机学学科科人人才才的的计计算算思思维维能力的培养能力的培养,也具有重要作用。,也具有重要作用。研究生阶段研究生阶段需要进一步进行需要进一步进行抽象思维抽象思维、逻
5、辑逻辑思维思维、创造思维能力创造思维能力的培养。的培养。需要更宽厚、坚实的需要更宽厚、坚实的理论基础理论基础。第第1章章基础知识基础知识 本章将对有限自动机理论中所需本章将对有限自动机理论中所需的的数学基础知识数学基础知识作作扼要的介绍扼要的介绍。包括集合及其运算、关系、证明包括集合及其运算、关系、证明的方法、图与树的概念;的方法、图与树的概念;常用术语常用术语和形式语言与自动机的发展和形式语言与自动机的发展。内容:内容:1.1集合及其运算集合及其运算1.2关系关系1.3证明和证明的方法证明和证明的方法1.4图与树图与树1.5语言语言1.6常用术语常用术语1.7形式语言与自动机的发展形式语言与
6、自动机的发展1.1集合及其运算集合及其运算一些一些没有重复没有重复的对象的全体称为的对象的全体称为集合集合,而这些被包含的对象称为该而这些被包含的对象称为该集合的集合的元素元素。集合中元素可以按集合中元素可以按任意的顺序任意的顺序进进行排列。行排列。使用使用大写英文字母大写英文字母表示一个集合。表示一个集合。如如何何删删除除指指定定位位置的元素?置的元素?数组数组链表链表有穷集合有穷集合和和无穷集合无穷集合如果一个集合包含的元素个数是有如果一个集合包含的元素个数是有限的,称该集合为限的,称该集合为有穷有穷集合集合。如果一个集合包含的元素是无限的,如果一个集合包含的元素是无限的,称该集合为称该集
7、合为无穷无穷集合集合。无穷集合又分为无穷集合又分为可数集可数集(也称为也称为可列可列集,集,如正奇数集如正奇数集)和和不可数集不可数集(如实数集如实数集)。集合的定义方法:集合的定义方法:列举列举法法命题命题法法列举法列举法(穷举法穷举法)对于有穷的,且元素个数较少的对于有穷的,且元素个数较少的集合,可以采用列举法,集合,可以采用列举法,即将集合即将集合的所有元素全部列出的所有元素全部列出,并放在一对,并放在一对花括号中。花括号中。例如例如集合集合A=1,2,3,4,5对于某些无穷集合,也可以使用对于某些无穷集合,也可以使用类似类似列举列举的方法进行描述的方法进行描述如自然数集合:如自然数集合
8、:0,1,2,3,命题法命题法对于集合元素较多的有穷集合或者是对于集合元素较多的有穷集合或者是无穷集合,可使用集合元素的形成模式无穷集合,可使用集合元素的形成模式x|P(x)进行描述。进行描述。其中:其中:x表示集合中的任一元素表示集合中的任一元素,P(x)是是一个一个谓词谓词,对,对x进行限定。进行限定。用来描述或判定客体性质、用来描述或判定客体性质、特征的词项。特征的词项。x|P(x)表示表示由满足由满足P(x)的一切的一切x构成的集合。构成的集合。可以使用自然语言,或者数学表可以使用自然语言,或者数学表示法来描述(表达)谓词示法来描述(表达)谓词P(x)例如:n|n是偶数是偶数或或n|n
9、mod2=0描述了由所有偶数组成的集合。描述了由所有偶数组成的集合。集合的基数集合的基数若集合若集合A包含元素包含元素x,记为记为x A反之,反之,x A对于有穷集合对于有穷集合A,使用使用|A|表示该集表示该集合包含的元素的合包含的元素的个数个数,也称,也称基数基数或或势势|A|=0A=定义定义1-1子集子集设设A,B是两个集合,如果集合是两个集合,如果集合A中的每中的每个元素都是集合个元素都是集合B的元素,则称集合的元素,则称集合A是是集合集合B的子集的子集(集合集合B是集合是集合A的包集的包集)A B 或或B A A,B是两个集合,如果是两个集合,如果A B,且且 x B,但但x A,则
10、称则称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思考:什么情况下:什么情况下:AB=A?集合
11、集合A与集合与集合B的的差运算差运算,记为,记为A B属于属于集合集合A但但不属于集合不属于集合B的所有元的所有元素组成的集合。素组成的集合。A B=x|xA且且x B思考思考:什么情况下:什么情况下:A-B=A?如果如果B A,将,将A B称为集合称为集合B(关(关于集合于集合A)的)的补运算补运算。集合集合A称为集合称为集合B的全集(或的全集(或论域论域)定义定义1-3幂集幂集设设A为一个集合,那么为一个集合,那么A的的幂集幂集为为A的所有子集的所有子集组成的集合组成的集合记为记为2A2A=B|B A例1-1集合集合A=1,2,3,则则A的幂集为的幂集为:2A=,1,2,3,1,2,1,3
12、,2,3,1,2,3任取其中任取其中2个元素构成的集合个元素构成的集合幂集幂集2A的元素个数的元素个数当当集合集合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当当
13、集合集合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,510,0101.2关
14、系关系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的的二元关系有多少个二元关系有多少个?A到到B的一个二元关系的一个二元关系最多最多可以有多少个元素可以有多少个元素?最少最少可以有多少个元素可以有多少个
15、元素例例1-3设设A为正整数集合,则为正整数集合,则A上的关系上的关系“”是集合是集合(a,b)|a,b A,且且a 0n0(5)用用AB代表集合代表集合A与与B的连接的连接A=a1,a2,a3,anB=b1,b2,b3,bmAB=a1b1,a1b2,a1b3,a1bm,a2b1,a2b2,a2b3,a2bm,a3b1,a3b2,a3b3,a3bm,anb1,anb2,anb3,anbm注意:A=A=一般,一般,AB与与BA是不相等的。是不相等的。思考思考:AB与与BA在什么情况下相等在什么情况下相等?1)当当A=B;2)A或或B中有一个为中有一个为,则则A=A=A3)A和和B中有一个为中有一
16、个为,则则A=A=6)An代表集合代表集合A的的n次连接次连接(幂幂)A的的n次次幂幂定义为:定义为:(1)A0=(2)An=An-1An 17)A*代表代表A上所有字符串的集合上所有字符串的集合即即表表示示集集合合A中中的的所所有有字字符符串串进进行行任意次任意次连接连接而形成的串的集合而形成的串的集合A*称为集合称为集合A的闭包的闭包(克林闭包克林闭包)A*=A0A1A2An例 A=0,1A0=即即长度为长度为0的的0和和1组成的串的集合组成的串的集合A1=A=0,1即即长度为长度为1的的0和和1组成的串的集合组成的串的集合A2=AA=00,01,10,11即即长度为长度为2的的0和和1组
17、成的串集合组成的串集合A3=A2A=000,001,010,011,100,101,110,111即即长度为长度为3的的0和和1组成的串的集合组成的串的集合A*=A0A1A2An=0和和1组成的所有的串组成的所有的串=w|w是是0和和1组成的串组成的串如如果果串串是是集集合合A的的闭闭包包中中的的串串,也称也称是集合是集合A上的串上的串。对于任何集合对于任何集合A有有(A*)*=A*8)A+称为称为A的正闭包的正闭包A+=AA2A3AnA*与 A+A*=A+A0即即A*=A+注意:注意:A0=*=+=*=+=思考思考是否对于任意的集合是否对于任意的集合A,都有都有A+=A*-辨析与思考辨析与思
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有限 自动机 理论 基础知识
限制150内