有限自动机理论CH1.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,有限自动机理论,06016004,陈文宇,电子科技大学计算机科学与工程学院,联系方式,cwy,13808181782,B1-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,A,定义1-2 集合的运算,集合,A,与集合,B,的并，记为,AB,。,集合,A,的所有元素和集合,B,的所有元素,合并,在一起组成的集合。,AB=x|,xA,或,xB,思考：,什么情况下：,AB=A,？,集合,A,与集合,B,的交，记为,AB,是由集合,A,和集合,B,的所有,公共元素,组成的集合。,A,B=x|,xA,且,xB,思考：,什么情况下：,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,的所有子集,组成的集合,记为,2,A,2,A,=,B,|,B,A,例,1-1,集合,A,=1，2，3,，,则,A,的幂集为:,2,A,=,，,1，2，3,，,1，2，1，3，2，3,，,1，2，3,幂集,2,A,的元素个数,当,集合,A,为有穷集,时，如果,|A|=,n,，,那么,A,的幂集,2,A,的元素个数(集合,A,的所有子集的个数)为,2,n,。,（集合,A,的幂集表示为,2,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,=,a,0,a,1,b,0,b,1,c,0,c,1,思考,什么情况下：,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,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,，,则称为,A,上,的关系。,思考：,如果集合,A,和,B,都是有穷集合，则,A,到,B,的,二元关系有多少个,？,A,到,B,的一个二元关系可以,有多少个元素,？,例1-,3,设,A,为正整数集合，则,A,上的关系“,”是集合,(,a,b,)|,a,b,A,且,a,0,(5),用,AB,代表集合,A,与,B,的连接,A=a,1,a,2,a,3,a,n,B=b,1,b,2,b,3,b,m,AB=,a,1,b,1,，a,1,b,2,，a,1,b,3,，a,1,b,m,，,a,2,b,1,，a,2,b,2,，a,2,b,3,，a,2,b,m,，,a,3,b,1,，a,3,b,2,，a,3,b,3,，a,3,b,m,，,a,n,b,1,，a,n,b,2,，a,n,b,3,，,a,n,b,m,注意：,A=A=,一般，,AB,与,BA,是不相等的。,思考,:,AB,与,BA,在什么情况下相等?,1)当,A=B,；,2)A,或,B,中有一个为,则,A=,A,=A,3)A,和,B,中有一个为,，,则,A=A=,6),A,n,代表集合,A,的,n,次连接,(,幂,),A,的,n,次,幂,定义为：,(1),A,0,=,(2),A,n,=A,n,-1,A,n,1,7),A,*,代表,A,上所有字符串的集合,即表示集合,A,中的所有字符串进行,任意次 连接,而形成的串的集合,A,*,称为集合,A,的闭包,(,克林闭包,),A,*,=A,0,A,1,A,2,A,n,例,A=0，1,A,0,=,即,长度为0,的0和1组成的串的集合,A,1,=A=0,1,即,长度为1,的0和1组成的串的集合,A,2,=AA=00,01,10,11,即,长度为2,的0和1组成的串集合,A,3,=A,2,A,=000,001,010,011,100,101,110,111,即,长度为3,的0和1组成的串的集合,A,*,=A,0,A,1,A,2,A,n,=0,和1 组成的所有的串,=,w|w,是0和1 组成的串,如果串,是集合,A,的闭包中的串，也称,是集合,A,上的串,。,对于任何集合,A,有(,A,*,),*,=A,*,8),A,+,称为,A,的正闭包,A,+,=AA,2,A,3,A,n,A,*,与,A,+,A,*,=A,+,A,0,即,A,*,=A,+,注意：,A,0,=,*,=,+,=,*,=,+,=,思考,是否对于任意的集合,A，,都有,A,+,=A,*,-,辨析与思考,与,|,|=1|=0,A,=,A,A,=,9）给定字母表，则,*,的任意,子集,L,称为字母表上的一个语言。,本质上，,语言,L,是,字母表,上的字符串形成的,集合,。,10)给定字母表,，,L,是字母表上的一个语言，,是,L,的一个字符串,称,为,L,的一个,句子,。,串的长度,|,|=0；,|=n,；,若,=a,1,a,2,a,3,a,n,；,其中：,a,i,，n,0；,11),前缀和后缀：,x,y,z,*,，,且,x=,yz,y,是,x,的前缀；,如果,z,，,则称,y,是,x,的,真前缀,；,z,是,x,的后缀；,如果,y,，,则称,z,是,x,的,真后缀,；,例,1-13,串,abcde,：,前缀：,，a，ab，abc，abcd，abcde,真前缀：,，a，ab，abc，abcd,后缀：,，e，de，cde，bcde，abcde,真后缀：,，e，de，cde，bcde,对于任意字符串,x,，,x,的前缀有,|,x,|+1,个,真前缀有,|,x,|,个,对于任何字符串,x，x,的任意,前缀,y,有,惟一,的一个,后缀,z,与之对应，使得,x=,yz,，,反之亦然；,对于任何字符串,x，x,的任意,真前缀,y,有,惟一,的一个,真后缀,z,与之对应，使得,x=,yz,，,反之亦然（除了,以外）；,对于任何字符串,x,x,是,自身的前缀,，但,不是真前缀,x,是,自身的后缀,，但,不是真后缀,对于任何字符串,x,，,是,x,的前缀，且是真前缀；,是,x,的后缀，且是真后缀；,思考：,对于,，,前缀是？真前缀？,后缀是？真后缀？,12)语言的前缀性质,设,L,是某个字母表上的语言,如果,L,中的任何句子都是另一个句子的真前缀，则称语言,L,具有,前缀性质,。,例,1-14,字母表0，1上的语言,L,1,=0,n,|n=0,具有前缀性质；,语言,L,2,=0,n,1|n=0,不具有前缀性质。,语言与句子,设,是一个字母表，,L,*,L,称为字母表,上的一个,语言,x,L,x,称为,L,的一个,句子,。,语言的可分为,有穷语言,与,无穷语言,语言的乘积,设,1,2,是两个字母表,L,1,1,*,L,2,2,*,语言,L,1,与,L,2,的乘积是一个语言：,L,1,L,2,=,xy,|,x,L,1,y,L,2,该语言是字母表,1,2,上的语言,语言的例子,字母表,0,1,上的一些语言：,00,11,0,1,00,11,00,1,*,1,0,1,*,1110,1,*,语言的,n,次幂,设,是一个字母表，,L,*,L,的,n,次幂是一个语言,(1)当,n,=0,时，,L,n,=,(2)当,n,1,时，,L,n,=,L,n,-1,L,语言的例子,令,=0,1,，,L,=0,1,L,=0,1,00,01,10,11,=,+,L,=,0,1,00,01,10,11,=,*,L,=0,n,1,n,|,n,1,L,=0,n,1,m,0,k,|,n,m,k,1,L,=0,n,1,m,0,k,|,n,m,k,语言的闭包,L,的正闭包,L,+,是一个语言：,L,+,=,L,L,2,L,3,L,的克林闭包,L,*,是一个语言：,L,*,=,L,0,L,+,1.7形式语言与自动机的发展,语言学家,Chomsky(,乔姆斯基)最早从产生语言的角度研究语言。1956年，通过抽象，,Chomsky,将语言形式地定义为由一个字母表的字母组成的一些串的集合：对于任意语言,L，,有一个字母表，使得,L,C,*,。,可以在字母表上按照一定的形成规则定义一个文法，该文法产生的所有的句子组成的集合就是该文法产生的语言。,1959年，,Chomsky,根据产生语言的文法的产生式的不同特点，将文法和对应产生的语言分为三大类。,数学家,Kleene,（,克林）在19511956年间，从识别语言的角度来研究语言，给出了语言的另一种描述方式。,Kleene,在研究神经细胞时建立了自动机模型，,Kleene,使用该模型来识别（接收）一个语言：按照某种识别规则构造自动机，该自动机就定义了一个语言，该语言由自动机能够识别的所有字符串构成。,语言的两种不同的定义方式进一步引起了人们的研究兴趣。一个语言，可以采取不同的描述方式：文法产生语言和自动机识别语言。由于是同一个语言，两种方式应该是等价的，也就存在两种方式之间的等价的相互转换方法。,Chomsky,于1959年，将他本人的形式语言的研究成果和,Kleene,的自动机的研究成果结合起来，不仅确定了文法和自动机分别从产生和识别角度定义语言，而且证明了文法与自动机的等价性。此时，形式语言与自动机理论才真正诞生。并被置于数学的光芒之下。,形式语言与自动机理论出现后，迅速在计算机科学技术领域得到了应用。使用巴科斯-诺尔范式（,BNF-Backus-Naur Form）,成功地对高级程序设计语言,ALGOL-60,的词法和语法规则进行了形式化的描述（实际上，巴科斯-诺尔范式就是上下文无关文法的产生式另一种表示方式）。这一成功，使得形式语言与自动机理论得到了进一步的发展。,尤其是上下文无关文法，被作为计算机程序设计语言语法的最佳近似描述得到了较为深入的研究。后来，人们又将上下文无关文法应用到了模式匹配和模型化处理等方面，而这些内容都是算法描述和分析、计算复杂性理论和可计算性理论的研究基础。,形式语言理论的研究对象与以前的所有语言研究不同，不止自然语言，而是人类一切语言：既有自然语言，也有人工语言，包括计算机编程的高级语言。乔姆斯基的形式语言理论得到了多重验证，于是才为语言学界和计算机科学界所折服，“引发了语言学中伽利略式的科学革命的开端。”,乔姆斯基的形式语言理论得到过计算机科学的三种验证。,验证一：乔氏4型文法与4种语言自动机一一对应。,验证二：计算机所使用的各种高级语言，如,ALGOL、FORTRAN、PASCAL、C、LISP,等，都遵循一种程序语言文法描述的范式，即巴科斯瑙尔范式。计算机科学家发现，巴科斯瑙尔范式等价于乔姆斯基的2型文法，即与上下文无关文法。而乔姆斯基的3型文法正则文法，在研究文字的计算机模式识别时，也被有效应用。于是，乔氏的4种类型文法被计算机科学界称作乔姆斯基分类。,验证三：乔姆斯基用形式语言理论的思想证明了计算机科学的一个重大理论问题：计算机程序语言是否有歧义性是不可判定的。,20世纪中期，程序语言,ALGOL60,问世不久，人们发现它有歧义性。当计算机科学家绞尽脑汁寻找办法来判断一种程序语言是否有歧义性时，乔姆斯基用形式语言理论的思想证明，一个任意的上下文无关文法是否有歧义性是不可判定的，因此，属于上下文无关文法的程序语言是否有歧义性也是不可判定的。乔姆斯基的论证令计算机科学界折服。,实际上，形式语言与自动机理论除了在计算机科学与技术领域的直接应用外，更在计算机计算机科学与技术领域的人才的计算思维能力的培养中占有极其重要的地位。,计算机科学与技术学科强调,4,个方面的专业能力：计算思维能力、算法设计与分析能力、程序设计与实现能力、计算机系统的认知、分析、设计和运用能力。这也是计算机科学与其他学科的重要区别。相关的理论是计算机学科的基础。,理论方面的知识是计算机的真正灵魂。,在本科阶段的学习过程中，学生以观察、描述、比较、分类、推断、应用、创造思维等科学思维过程为主，强调,自学的能力,在培养；,研究生阶段，需要对学生进一步进行抽象思维、逻辑思维、创造思维能力的培养。,建立物理符号系统并对起实施等价变换是计算机学科进行问题描述和求解的重要手段。“可行性”所要求的“形式化”及其“离散特征”使得数学成为重要的工具，而计算模型无论从方法还是从工具等方面，都表现出它在计算机上科学中的重要作用。,计算机科学与技术学科要求学生具有形式化描述和抽象思维能力，要求掌握逻辑思维方法。这种能力就是计算思维能力或计算机思维能力。,计算机学科系统地研究信息描述和变换算法，重要包括信息描述和变换算法的理论、分析、效率、实现和运用。学科的根本问题在于：什么能被（有效地）自动化？学科的重要内容之一是研究计算领域中的一些普遍规律，描述算法的基本概念与模型。,计算思维能力的培养主要是通过基础理论系列课程实现的，该系列是由数学和抽象度较高的理论课程组成，包括数学分析、集合和图论、形式语言与自动机、近世代数、数学建模等课程。,练习(见习题,),3(2),4,3,给出下列对象的递归定义,对于任意,x,*,字符串,x,的倒序,若,|,x,|,1，,令,x,=,ya,，,其中,y,+,a,，,则,x,T,=,ay,T,习题评讲(续),9,(1)00,1,*,(2),00,1,*,1,(3),110,1,*,11,111,，,11,(4)?,习题评讲(续),(5),0,10,1,*,(6),0,10,1,*,0,1,(7),0,1,*,01011 0,1,*,(8),0,1,*,0000,1,*,习题评讲(续),(9),0,1,9,00,1,*,(10),0,1,*,0 0,1,5,小结,复习,集合、关系、图,等相关知识,引入,形式语言,基本概念,