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

有限自动机理论06016004陈文宇电子科技大学计算机科学与工程学院联系方式[e-mail]13808181782主楼B1-509课件下载：计算机学院网站-师资队伍-陈文宇课程情况学时：40（前10周）学分：２考试：闭卷、笔试大概10周考试作业20%+考试80%考查：作业100%不参加考试教材：有限自动机理论（2版）陈文宇田玲程伟刘贵松电子工业出版社2013.08参考书形式语言与自动机理论(第2版)蒋宗礼姜守旭清华大学出版社2007形式语言与自动机陈有祺机械工业出版社2008参考书IntroductiontoAutomataTheory,Languages,andComputation(SecondEdition)自动机理论、语言和计算导论（JohnE.Hopcroft机械工业出版社）理论来源形式语言和自动机的理论来源于(1)Chomsky对自然语言的研究；(2)ALGOL60语言的语法描述方式；(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|nmod2=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AA,B是两个集合，如果AB，且xB，但xA，则称A是B的真子集AB两个集合相等，当且仅当AB且BA注意：不是AB且BA定义1-2集合的运算集合A与集合B的并运算，记为A∪B集合A的所有元素和集合B的所有元素合并在一起组成的集合。A∪B={x|x∈A或x∈B}思考：什么情况下：A∪B=A？集合A与集合B的交运算，记为A∩B是由集合A和集合B的所有公共元素组成的集合。A∩B={x|x∈A且x∈B}思考：什么情况下：A∩B=A？集合A与集合B的差运算，记为AB属于集合A但不属于集合B的所有元素组成的集合。AB={x|x∈A且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}，{2，3}，{1，2，3}}任取其中2个元素构成的集合幂集2A的元素个数当集合A为有穷集时，如果|A|=n，那么A的幂集2A的元素个数(集合A的所有子集的个数)为2n。（集合A的幂集表示为2A的原因）无论集合A是有穷集合，还是无穷集合，都使用2A表示集合A的幂集。定义1-4笛卡儿积集合A和B的笛卡儿乘积AB（也简记为AB）AB={(a,b)|aA且bB}当集合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?练习1～10之间的和为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}｛10，0｝｛10｝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的二元关系有多少个？A到B的一个二元关系最多可以有多少个元素？最少可以有多少个元素例1-3设A为正整数集合，则A上的关系“”是集合{(a,b)|a,bA,且ab}={(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是对称的。(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,且amod3=bmod3}是一个等价关系。{0,3,6,…,3n,…}第1个等价类；{1,4,7,…,3n+1,…}第2个等价类；{2,5,8,…,3n+2,…}第3个等价类；分别记为[0]，[1]和[2]。N=[0]∪[1]∪[2]等价关系的指数为3思考自然数集合N上的相等关系1.2.3关系的合成关系可以进行合成。定义1-7设R1AB是A到B的(二元)关系R2BC是B到C的(二元)关系R1与R2的合成是A到C的(二元)关系R1οR2={(a,c)|(a,b)R1且(b,c)R2}例1-5R1和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)}则R1οR2={(1,4),(2,1),(2,4),(3,1),(3,3)}R2οR1={(4,1),(4,2),(4,4),(3,1),(3,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)}则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)进行一系列的推理；(3)在推理的过程中如果出现了下列情况之一：与已知条件矛盾；与公理矛盾；与已证过的定理矛盾；与临时的假定矛盾；自相矛盾；反证法(续)由于上述矛盾的出现，可以断言“假设该命题不成立”的假设不正确；从而肯定原命题正确。反证法(续)反证法例子是无理数。2演绎与归纳演绎是从普遍性的理论知识出发，去认识个别的、特殊的现象的一种逻辑推理方法。演绎的基本形式是三段论。归纳是根据个别的、特殊的现象，得到普遍性知识的逻辑推理方法。1.3.2归纳法归纳法是从特殊到一般的逻辑推理方法。分为完全归纳法和不完全归纳法两种形式。完全归纳法是根据一切情况的分析而作出的推理。由于必须考虑所有的情况，得出的结论是完全可靠的。归纳法（续）不完全归纳法是根据一部分情况作出的推理。不能作为严格的证明方法。在自动机理论中，普遍使用数学归纳法证明某个命题。数学归纳法可以使用“有限步骤”解决“无限”问题。数学归纳法对于一切非负整数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集合递归定义与归纳证明递归定义(1)基础(2)归纳(3)极小性限定(有限性)递归定义集合步骤(1)基础：首先定义该集合中最基本的元素x1,x2,x3,…xm(2)归纳：对于该集合中的元素x1,x2,x3,…xn使用某种方法对这些元素进行处理后所得的新元素在该集合中(3)有限性：只有满足(1)和(2)的元素才在集合中递归定义集合的优点除集合的基本元素(直接定义)外集合中的元素的产生遵从相同的规律。例1-6Fibonacci数Fibonacci数组成的集合为：{0,1,1,2,3,5,8,13,21,34,55,…}(1)基础：0和1是最基本的两个元素；(2)归纳：若m是第i个元素,n是第i+1个元素则第i+2个元素为n+m;(3)只有满足(1)和(2)的数，才是集合的元素例括号匹配的串构成的集合的定义{(),()(),((