《有限自动机理论01章基础知识.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论01章基础知识.ppt（181页珍藏版）》请在金锄头文库上搜索。
1、有限自动机理论有限自动机理论06016004陈文宇陈文宇电子科技大学计算机科学与工程学院电子科技大学计算机科学与工程学院联系方式联系方式13808181782主楼主楼B1-509http:/ 陈文宇陈文宇 电子科技大学出版社电子科技大学出版社 2007.32007.3参考书参考书形式语言与自动机理论形式语言与自动机理论(第第2版版)蒋宗礼蒋宗礼姜守旭姜守旭清华大学出版社清华大学出版社2007形式语言与自动机形式语言与自动机陈有祺陈有祺机械工业出版社机械工业出版社2008参考书参考书IntroductiontoAutomataTheory,Languages,andComputation(Sec
2、ondEdition)自动机理论、语言和计算导论自动机理论、语言和计算导论 （JohnE.Hopcroft机械工业出版社）机械工业出版社）理论来源理论来源形式语言和自动机的理论来源于形式语言和自动机的理论来源于(1)Chomsky对自然语言的研究；对自然语言的研究；(2)ALGOL60语言的语法描述方式；语言的语法描述方式；(3)Turing、 Kleene、 Neumann、 Huffman等等 对自动机的研究。对自动机的研究。形式语言与自动机的作用形式语言与自动机的作用形形式式语语言言和和自自动动机机的的理理论论已已经经成成为计算机科学的为计算机科学的理论基础理论基础。应应用用范范围围已已
3、被被扩扩展展到到生生物物工工程程、自自动动控控制制系系统统、图图像像处处理理与与模模式式识识别别等许多领域。等许多领域。计算机学科的专业能力 计算思维计算思维能力能力 算法设计与分析算法设计与分析能力能力 程序设计与实现程序设计与实现能力能力 计算机系统的认知、分析、计算机系统的认知、分析、 设计和运用设计和运用能力能力计算思维能力形式化描述能力形式化描述能力抽象思维能力抽象思维能力逻辑思维方法逻辑思维方法计算机学科的专业能力 相关理论是计算机学科基础。相关理论是计算机学科基础。 理论方面的知识是计算机科学的理论方面的知识是计算机科学的真正灵魂。真正灵魂。 这也是计算机科学与其他学科的这也是计
4、算机科学与其他学科的重要区别。重要区别。有有限限自自动动机机理理论论在在科科学学领领域域中中得得到直接应用到直接应用对对于于计计算算机机学学科科人人才才的的计计算算思思维维能力的培养能力的培养，也具有重要作用。，也具有重要作用。研究生阶段研究生阶段需要进一步进行需要进一步进行抽象思维抽象思维、逻辑逻辑思维思维、创造思维能力创造思维能力的培养。的培养。需要更宽厚、坚实的需要更宽厚、坚实的理论基础理论基础。第第1章章基础知识基础知识 本章将对有限自动机理论中所需本章将对有限自动机理论中所需的的数学基础知识数学基础知识作作扼要的介绍扼要的介绍。 包括集合及其运算、关系、证明包括集合及其运算、关系、证
5、明的方法、图与树的概念；的方法、图与树的概念；常用术语常用术语和形式语言与自动机的发展和形式语言与自动机的发展。内容：内容：1.1集合及其运算集合及其运算1.2关系关系1.3证明和证明的方法证明和证明的方法1.4图与树图与树1.5语言语言1.6常用术语常用术语1.7形式语言与自动机的发展形式语言与自动机的发展1.1集合及其运算集合及其运算一些一些没有重复没有重复的对象的全体称为的对象的全体称为集合集合，而这些被包含的对象称为该而这些被包含的对象称为该集合的集合的元素元素。集合中元素可以按集合中元素可以按任意的顺序任意的顺序进进行排列。行排列。使用使用大写英文字母大写英文字母表示一个集合。表示一
6、个集合。如如何何删删除除指指定定位置的元素？位置的元素？有穷集合有穷集合和和无穷集合无穷集合如果一个集合包含的元素个数是有如果一个集合包含的元素个数是有限的，称该集合为限的，称该集合为有穷有穷集合集合。如果一个集合包含的元素是无限的，如果一个集合包含的元素是无限的，称该集合为称该集合为无穷无穷集合集合。无穷集合又分为无穷集合又分为可数集可数集(也称为也称为可列可列集，集，如正奇数集如正奇数集)和和不可数集不可数集(如实数集如实数集)。集合的定义方法：集合的定义方法：列举列举法法命题命题法法列举法列举法(穷举法穷举法)对于有穷的，且元素个数较少的对于有穷的，且元素个数较少的集合，可以采用列举法，
7、集合，可以采用列举法，即将集合即将集合的所有元素全部列出的所有元素全部列出，并放在一对，并放在一对花括号中。花括号中。例如例如集合集合A=1，2，3，4，5对于某些无穷集合，也可以使用对于某些无穷集合，也可以使用类似类似列举列举的方法进行描述的方法进行描述如自然数集合：如自然数集合：0，1，2，3，命题法命题法对于集合元素较多的有穷集合或者是对于集合元素较多的有穷集合或者是无穷集合，可使用集合元素的形成模式无穷集合，可使用集合元素的形成模式x |P(x)进行描述。进行描述。其中：其中：x表示集合中的任一元素表示集合中的任一元素,P(x)是是一个一个谓词谓词，对，对x进行限定。进行限定。用来描述
8、或判定客体性质、用来描述或判定客体性质、特征的词项。特征的词项。x|P(x)表示表示由满足由满足P(x)的一切的一切x构成的集合。构成的集合。可以使用自然语言，或者数学表可以使用自然语言，或者数学表示法来描述（表达）谓词示法来描述（表达）谓词P(x)例如：n|n是偶数是偶数或或n|nmod2=0描述了由所有偶数组成的集合。描述了由所有偶数组成的集合。集合的基数集合的基数若集合若集合A包含元素包含元素x，记为记为x A反之，反之，x A对于有穷集合对于有穷集合A，使用使用|A|表示该集表示该集合包含的元素的合包含的元素的个数个数，也称，也称基数基数或或势势|A|=0A = 定义定义1-1子集子集
9、设设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的的所所有有元元素素合并合并在一起组成的集合。在一起
10、组成的集合。AB=x|xA或或xB思考：什么情况下：什么情况下：AB=A？集合集合A与集合与集合B的交，记为的交，记为AB是由集合是由集合A和集合和集合B的所有的所有公共元素公共元素组成的集合。组成的集合。AB=x|xA且且xB思考：什么情况下：什么情况下：AB=A？集合集合A与集合与集合B的差，记为的差，记为A B属于属于集合集合A但但不属于集合不属于集合B的所有元的所有元素组成的集合。素组成的集合。A B=x|xA且且x B思考思考:什么情况下：什么情况下：A-B=A？如果如果B A，将，将A B称为集合称为集合B（关（关于集合于集合A）的）的补补。集合集合A称为集合称为集合B的全集（或的
11、全集（或论域论域）定义定义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 A是
12、有穷集合，还是无穷集合，都使用是有穷集合，还是无穷集合，都使用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|例例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,c
13、0,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，51.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
14、，则称则称R为为A上上的关系的关系思考：思考：如果集合如果集合A和和B都是有穷集合，则都是有穷集合，则A到到B的的二元关系有多少个二元关系有多少个？A到到B的一个二元关系的一个二元关系最多最多可以有多少个元素可以有多少个元素？最少最少可以有多少个元素可以有多少个元素例例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，a3
15、b3，a3bm，anb1，anb2，anb3，anbm注意：A=A=一般，一般，AB与与BA是不相等的。是不相等的。思考思考:AB与与BA在什么情况下相等在什么情况下相等?1)当当A=B；2)A或或B中有一个为中有一个为,则则A=A=A3)A和和B中有一个为中有一个为，则则A=A=6)An代表集合代表集合A的的n次连接次连接(幂幂)A的的n次次幂幂定义为：定义为：(1)A0= (2)An =An-1An 17)A*代表代表A上所有字符串的集合上所有字符串的集合即即表表示示集集合合A中中的的所所有有字字符符串串进进行行任意次任意次连接连接而形成的串的集合而形成的串的集合A*称为集合称为集合A的闭
16、包的闭包(克林闭包克林闭包)A*=A0A1A2An例 A=0，1A0=即即长度为长度为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*=A0A1A2An=0和和1组成的所有的串组成的所有的串=w|w是是0和和1组成的串组成的串如如果果串串是是集集合合A的的闭闭包包中中的的串串，也称也称是集合是集合A上的串
17、上的串。对于任何集合对于任何集合A有有(A*)*=A*8)A+称为称为A的正闭包的正闭包A+=AA2A3AnA * 与 A+A*=A+ A0即即A*=A+ 注意：注意：A0=*=+=*=+=思考思考是否对于任意的集合是否对于任意的集合A，都有都有A+=A*-辨析与思考辨析与思考与| |=1|=0 A=A A=9）给给定定字字母母表表，则则*的的任任意意子子集集L称为字母表称为字母表上的一个语言。上的一个语言。本本质质上上，语语言言L是是字字母母表表上上的的字字符串形成的符串形成的集合集合。10)给给定定字字母母表表，L是是字字母母表表上上的的一一个个语语言言，是是L的的一一个个字字符串符串称称
18、为为L的一个的一个句子句子。串的长度串的长度|=0；|=n；若若=a1a2a3an；其中：其中：ai，n0；11)前缀和后缀：前缀和后缀：x,y,z*，且且x=yzy是是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个个 真前缀有
19、真前缀有|x|个个对对于于任任何何字字符符串串x，x的的任任意意前前缀缀y有有惟惟一一的的一一个个后后缀缀z与与之之对对应应，使使得得x=yz，反之亦然；反之亦然；对对于于任任何何字字符符串串x，x的的任任意意真真前前缀缀y有有惟惟一一的的一一个个真真后后缀缀z与与之之对对应应，使使得得x=yz，反之亦然（除了反之亦然（除了以外）；以外）；对于任何字符串对于任何字符串xx是是自身的前缀自身的前缀，但，但不是真前缀不是真前缀x是是自身的后缀自身的后缀，但，但不是真后缀不是真后缀对于任何字符串对于任何字符串x ，是是x的前缀，且是真前缀；的前缀，且是真前缀；是是x的后缀，且是真后缀；的后缀，且是真
20、后缀；思考：思考：对于对于，前缀是？真前缀？前缀是？真前缀？后缀是？真后缀？后缀是？真后缀？12)语言的前缀性质语言的前缀性质设设L是某个字母表上的语言是某个字母表上的语言如如果果L中中的的任任何何句句子子都都是是另另一一个个句句子子的的真真前前缀缀，则则称称语语言言L具具有有前前缀性质缀性质。例1-14字母表字母表0，1上的语言上的语言L1=0n|n=0具有前缀性质；具有前缀性质；语言语言L2=0n1|n=0不具有前缀性质。不具有前缀性质。语言与句子语言与句子设设 是一个字母表，是一个字母表， L *,L称为字母表称为字母表 上的一个上的一个语言语言 x L,x称为称为L的一个的一个句子句子
21、。语言的可分为语言的可分为有穷语言有穷语言与与无穷语言无穷语言语言的乘积语言的乘积设设 1, 2是两个字母表是两个字母表L1 1*,L2 2*,语言语言L1与与L2的乘积是一个语言：的乘积是一个语言：L1L2=xy|x L1,y L2该语言是字母表该语言是字母表 1 2上的语言上的语言语言的例子语言的例子字母表字母表0,1上的一些语言：上的一些语言：00,110,1,00,1100,1*10,1*1110,1*语言的语言的n次幂次幂设设 是一个字母表，是一个字母表， L *,L的的n次幂是一个语言次幂是一个语言(1)当当n =0时，时，Ln = (2)当当n 1时，时，Ln =Ln-1 L语言
22、的例子语言的例子令令 =0,1，L=0,1L=0,1,00,01,10,11,= +L= ,0,1,00,01,10,11,= *L=0n1n |n 1L=0n1m0k |n,m,k 1L=0n1m0k |n,m,k 语言的闭包语言的闭包L的正闭包的正闭包L+是一个语言：是一个语言：L+=LL2L3L的克林闭包的克林闭包L*是一个语言：是一个语言：L*=L0L+1.7形式语言与自动机的发展形式语言与自动机的发展l语语言言学学家家Chomsky(乔乔姆姆斯斯基基)最最早早从从产产生生语语言言的的角角度度研研究究语语言言。1956年年，通通过过抽抽象象，Chomsky将将语语言言形形式式地地定定义
23、义为为由由一一个个字字母母表表的的字字母母组组成成的的一一些些串串的的集集合合：对对于于任任意意语语言言L，有有一一个个字字母母表表，使使得得LC*。可可以以在在字字母母表表上上按按照照一一定定的的形形成成规规则则定定义义一一个个文文法法，该该文文法法产产生生的的所所有有的的句句子子组组成成的的集集合就是该文法产生的语言。合就是该文法产生的语言。l1959年年，Chomsky根根据据产产生生语语言言的的文文法法的的产产生生式式的的不不同同特特点点，将将文文法法和和对对应应产产生生的的语言分为三大类。语言分为三大类。l数数学学家家Kleene（克克林林）在在19511956年年间间，从从识识别别
24、语语言言的的角角度度来来研研究究语语言言，给给出出了了语语言言的的另另一一种种描描述述方方式式。Kleene在在研研究究神神经经细细胞胞时时建建立立了了自自动动机机模模型型，Kleene使使用用该该模模型型来来识识别别（接接收收）一一个个语语言言：按按照照某某种种识识别别规规则则构构造造自自动动机机，该该自自动动机机就就定定义义了了一一个个语语言言，该该语语言言由由自自动动机机能能够够识识别别的的所所有字符串构成。有字符串构成。l语语言言的的两两种种不不同同的的定定义义方方式式进进一一步步引引起起了了人人们们的的研研究究兴兴趣趣。一一个个语语言言，可可以以采采取取不不同同的的描描述述方方式式：
25、文文法法产产生生语语言言和和自自动动机机识识别别语语言言。由由于于是是同同一一个个语语言言，两两种种方方式式应应该该是是等等价价的的，也也就就存存在在两两种种方方式式之之间间的的等等价的相互转换方法。价的相互转换方法。lChomsky于于1959年年，将将他他本本人人的的形形式式语语言言的的研研究究成成果果和和Kleene的的自自动动机机的的研研究究成成果果结结合合起起来来，不不仅仅确确定定了了文文法法和和自自动动机机分分别别从从产产生生和和识识别别角角度度定定义义语语言言，而而且且证证明明了了文文法法与与自自动动机机的的等等价价性性。此此时时，形形式式语语言言与与自自动动机机理理论论才才真真
26、正正诞诞生生。并并被被置置于于数数学学的光芒之下。的光芒之下。l形形式式语语言言与与自自动动机机理理论论出出现现后后，迅迅速速在在计计算算机机科科学学技技术术领领域域得得到到了了应应用用。使使用用巴巴科科斯斯-诺诺尔尔范范式式（BNF-Backus-NaurForm）成成功功地地对对高高级级程程序序设设计计语语言言ALGOL-60的的词词法法和和语语法法规规则则进进行行了了形形式式化化的的描描述述（实实际际上上，巴巴科科斯斯-诺诺尔尔范范式式就就是是上上下下文文无无关关文文法法的的产产生生式式另另一一种种表表示示方方式式）。这这一一成成功功，使使得得形形式式语语言言与与自自动动机机理理论论得得
27、到到了了进进一一步步的发展。的发展。l尤尤其其是是上上下下文文无无关关文文法法，被被作作为为计计算算机机程程序序设设计计语语言言语语法法的的最最佳佳近近似似描描述述得得到到了了较较为为深深入入的的研研究究。后后来来，人人们们又又将将上上下下文文无无关关文文法法应应用用到到了了模模式式匹匹配配和和模模型型化化处处理理等等方方面面，而而这这些些内内容容都都是是算算法法描描述述和和分分析析、计计算算复复杂杂性性理理论论和和可可计计算算性性理理论论的的研研究究基基础。础。l形形式式语语言言理理论论的的研研究究对对象象与与以以前前的的所所有有语语言言研研究究不不同同，不不止止自自然然语语言言，而而是是人
28、人类类一一切切语语言言：既既有有自自然然语语言言，也也有有人人工工语语言言，包包括括计计算算机机编编程程的的高高级级语语言言。乔乔姆姆斯斯基基的的形形式式语语言言理理论论得得到到了了多多重重验验证证，于于是是才才为为语语言言学学界界和和计计算算机机科科学学界界所所折折服服，“引引发发了了语语言言学学中中伽伽利利略略式式的的科科学学革革命命的的开开端端。”l乔乔姆姆斯斯基基的的形形式式语语言言理理论论得得到到过过计计算算机机科科学的三种验证。学的三种验证。l验验证证一一：乔乔氏氏4型型文文法法与与4种种语语言言自自动动机机一一一对应。一对应。l验验证证二二：计计算算机机所所使使用用的的各各种种高
29、高级级语语言言，如如ALGOL、FORTRAN、PASCAL、C、LISP等等，都都遵遵循循一一种种程程序序语语言言文文法法描描述述的的范范式式，即即巴巴科科斯斯诺诺尔尔范范式式。计计算算机机科科学学家家发发现现，巴巴科科斯斯诺诺尔尔范范式式等等价价于于乔乔姆姆斯斯基基的的2型型文文法法，即即与与上上下下文文无无关关文文法法。而而乔乔姆姆斯斯基基的的3型型文文法法正正则则文文法法，在在研研究究文文字字的的计计算算机机模模式式识识别别时时，也也被被有有效效应应用用。于于是是，乔乔氏氏的的4种种类类型型文文法法被被计计算算机机科科学学界界称称作作乔姆斯基分类。乔姆斯基分类。l验验证证三三：乔乔姆姆
30、斯斯基基用用形形式式语语言言理理论论的的思思想想证证明明了了计计算算机机科科学学的的一一个个重重大大理理论论问问题题：计计算算机机程程序序语语言言是是否否有有歧歧义义性是不可判定的。性是不可判定的。l20世世纪纪中中期期，程程序序语语言言ALGOL60问问世世不不久久，人人们们发发现现它它有有歧歧义义性性。当当计计算算机机科科学学家家绞绞尽尽脑脑汁汁寻寻找找办办法法来来判判断断一一种种程程序序语语言言是是否否有有歧歧义义性性时时，乔乔姆姆斯斯基基用用形形式式语语言言理理论论的的思思想想证证明明，一一个个任任意意的的上上下下文文无无关关文文法法是是否否有有歧歧义义性性是是不不可可判判定定的的，因
31、因此此，属属于于上上下下文文无无关关文文法法的的程程序序语语言言是是否否有有歧歧义义性性也也是是不不可可判判定定的的。乔乔姆姆斯斯基基的的论论证证令令计计算机科学界折服。算机科学界折服。l实实际际上上，形形式式语语言言与与自自动动机机理理论论除除了了在在计计算算机机科科学学与与技技术术领领域域的的直直接接应应用用外外，更更在在计计算算机机计计算算机机科科学学与与技技术术领领域域的的人人才才的的计计算算思思维维能能力力的的培培养养中中占占有极其重要的地位。有极其重要的地位。l计算机科学与技术学科强调计算机科学与技术学科强调4个方面的专个方面的专业能力：计算思维能力、算法设计与分析业能力：计算思维
32、能力、算法设计与分析能力、程序设计与实现能力、计算机系统能力、程序设计与实现能力、计算机系统的认知、分析、设计和运用能力。这也是的认知、分析、设计和运用能力。这也是计算机科学与其他学科的重要区别。相关计算机科学与其他学科的重要区别。相关的理论是计算机学科的基础。的理论是计算机学科的基础。l理论方面的知识是计算机的真正灵魂。理论方面的知识是计算机的真正灵魂。l在本科阶段的学习过程中，学生以观在本科阶段的学习过程中，学生以观察、描述、比较、分类、推断、应用、察、描述、比较、分类、推断、应用、创造思维等科学思维过程为主，强调创造思维等科学思维过程为主，强调自学的能力自学的能力在培养；在培养；l研究生
33、阶段，需要对学生进一步进行研究生阶段，需要对学生进一步进行抽象思维、逻辑思维、创造思维能力抽象思维、逻辑思维、创造思维能力的培养。的培养。l建建立立物物理理符符号号系系统统并并对对起起实实施施等等价价变变换换是是计计算算机机学学科科进进行行问问题题描描述述和和求求解解的的重重要要手手段段。“可可行行性性”所所要要求求的的“形形式式化化”及及其其“离离散散特特征征”使使得得数数学学成成为为重重要要的的工工具具，而而计计算算模模型型无无论论从从方方法法还还是是从从工工具具等等方方面面，都都表表现现出出它它在计算机上科学中的重要作用。在计算机上科学中的重要作用。l计计算算机机科科学学与与技技术术学学
34、科科要要求求学学生生具具有有形形式式化化描描述述和和抽抽象象思思维维能能力力，要要求求掌掌握握逻逻辑辑思思维维方方法法。这这种种能能力力就就是是计计算算思维能力或计算机思维能力。思维能力或计算机思维能力。l计计算算机机学学科科系系统统地地研研究究信信息息描描述述和和变变换换算算法法，重重要要包包括括信信息息描描述述和和变变换换算算法法的的理理论论、分分析析、效效率率、实实现现和和运运用用。学学科科的的根根本本问问题题在在于于：什什么么能能被被（有有效效地地）自自动动化化？学学科科的的重重要要内内容容之之一一是是研研究究计计算算领领域域中中的的一一些些普普遍遍规规律律，描述算法的基本概念与模型。
35、描述算法的基本概念与模型。l计算思维能力的培养主要是通过基础计算思维能力的培养主要是通过基础理论系列课程实现的，该系列是由数理论系列课程实现的，该系列是由数学和抽象度较高的理论课程组成，包学和抽象度较高的理论课程组成，包括数学分析、集合和图论、形式语言括数学分析、集合和图论、形式语言与自动机、近世代数、数学建模等课与自动机、近世代数、数学建模等课程。程。练习练习(见习题见习题)l3(2)l43 给出下列对象的递归定义对于任意对于任意x *,字符串字符串x的倒序的倒序(1)若若|x|1，令令x=ya，其中其中y +,a ，则则xT=ayT4 0，1，请给出语言的形式表示，请给出语言的形式表示l所
36、有以所有以0开头的串的语言。开头的串的语言。l所有以所有以0开头，以开头，以1结尾的串的语言。结尾的串的语言。l所有以所有以11开头，开头，11结尾的串的语言。结尾的串的语言。l所有最多有一对连续的所有最多有一对连续的0或者最多有或者最多有一对连续的一对连续的1的串的语言。的串的语言。l所有长度为偶数的串的语言。所有长度为偶数的串的语言。l所有长度为奇数的串的语言。所有长度为奇数的串的语言。l所有包含子串所有包含子串01011的串的语言。的串的语言。l所有包含所有包含3个连续个连续0的串的语言。的串的语言。l所有所有的的第第10个字符是个字符是0的串的语言。的串的语言。l所有倒数第所有倒数第6个字符是个字符是0的串的语言。的串的语言。习题评讲习题评讲(续续)l4(1)00,1*(2)00,1*1(3)110,1*11111，11(4)?习题评讲习题评讲(续续)(5)0,10,1*(6)0,10,1*0,1(7)0,1*010110,1*(8)0,1*0000,1*习题评讲习题评讲(续续)(9)0,1900,1*(10)0,1*00,15小结小结l复习复习集合、关系、图集合、关系、图等相关知识等相关知识引入引入形式语言形式语言基本概念基本概念
