《有限自动机理论章基础知识幻灯片.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论章基础知识幻灯片.ppt（181页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、有限自动机理论章基有限自动机理论章基础知识础知识第1页，共181页，编辑于2022年，星期六联系方式联系方式13808181782主楼主楼B1-509http:/ 陈文宇陈文宇 电子科技大学出版社电子科技大学出版社 2007.32007.3第4页，共181页，编辑于2022年，星期六参考书参考书形式语言与自动机理论形式语言与自动机理论(第第2版版)蒋宗礼蒋宗礼姜守旭姜守旭清华大学出版社清华大学出版社2007形式语言与自动机形式语言与自动机陈有祺陈有祺机械工业出版社机械工业出版社2008第5页，共181页，编辑于2022年，星期六参考书参考书IntroductiontoAutomataTheor
2、y,Languages,andComputation(SecondEdition)自动机理论、语言和计算导论自动机理论、语言和计算导论（JohnE.Hopcroft机械工业出版社）机械工业出版社）第6页，共181页，编辑于2022年，星期六理论来源理论来源形式语言和自动机的理论来源于形式语言和自动机的理论来源于(1)Chomsky对自然语言的研究；对自然语言的研究；(2)ALGOL60语言的语法描述方式；语言的语法描述方式；(3)Turing、Kleene、Neumann、Huffman等等 对自动机的研究。对自动机的研究。第7页，共181页，编辑于2022年，星期六形式语言与自动机的作用形式
3、语言与自动机的作用形形式式语语言言和和自自动动机机的的理理论论已已经经成成为计算机科学的为计算机科学的理论基础理论基础。应应用用范范围围已已被被扩扩展展到到生生物物工工程程、自自动动控控制制系系统统、图图像像处处理理与与模模式式识识别别等许多领域。等许多领域。第8页，共181页，编辑于2022年，星期六计算机学科的专业能力 计算思维计算思维能力能力 算法设计与分析算法设计与分析能力能力 程序设计与实现程序设计与实现能力能力 计算机系统的认知、分析、计算机系统的认知、分析、设计和运用设计和运用能力能力第9页，共181页，编辑于2022年，星期六计算思维能力形式化描述能力形式化描述能力抽象思维能力
4、抽象思维能力逻辑思维方法逻辑思维方法第10页，共181页，编辑于2022年，星期六计算机学科的专业能力 相关理论是计算机学科基础。相关理论是计算机学科基础。理论方面的知识是计算机科学的理论方面的知识是计算机科学的真正灵魂。真正灵魂。这也是计算机科学与其他学科的重这也是计算机科学与其他学科的重要区别。要区别。第11页，共181页，编辑于2022年，星期六有有限限自自动动机机理理论论在在科科学学领领域域中中得得到到直直接应用接应用对对于于计计算算机机学学科科人人才才的的计计算算思思维维能能力力的培养的培养，也具有重要作用。，也具有重要作用。第12页，共181页，编辑于2022年，星期六研究生阶段研
5、究生阶段需要进一步进行需要进一步进行抽象思维抽象思维、逻辑思逻辑思维维、创造思维能力创造思维能力的培养。的培养。需要更宽厚、坚实的需要更宽厚、坚实的理论基础理论基础。第13页，共181页，编辑于2022年，星期六第第1章章基础知识基础知识 本章将对有限自动机理论中所需本章将对有限自动机理论中所需的的数学基础知识数学基础知识作作扼要的介绍扼要的介绍。包括集合及其运算、关系、证明的包括集合及其运算、关系、证明的方法、图与树的概念；方法、图与树的概念；常用术语和形常用术语和形式语言与自动机的发展式语言与自动机的发展。第14页，共181页，编辑于2022年，星期六内容：内容：1.1集合及其运算集合及其
6、运算1.2关系关系1.3证明和证明的方法证明和证明的方法1.4图与树图与树1.5语言语言1.6常用术语常用术语1.7形式语言与自动机的发展形式语言与自动机的发展第15页，共181页，编辑于2022年，星期六1.1集合及其运算集合及其运算一些一些没有重复没有重复的对象的全体称为的对象的全体称为集集合合，而这些被包含的对象称为该集合而这些被包含的对象称为该集合的的元素元素。集合中元素可以按集合中元素可以按任意的顺序任意的顺序进行排进行排列。列。使用使用大写英文字母大写英文字母表示一个集合。表示一个集合。如如何何删删除除指指定定位位置的元素？置的元素？第16页，共181页，编辑于2022年，星期六有
7、穷集合有穷集合和和无穷集合无穷集合如果一个集合包含的元素个数是有限的，如果一个集合包含的元素个数是有限的，称该集合为称该集合为有穷有穷集合集合。如果一个集合包含的元素是无限的，称该如果一个集合包含的元素是无限的，称该集合为集合为无穷无穷集合集合。无穷集合又分为无穷集合又分为可数集可数集(也称为也称为可列集，可列集，如正奇数集如正奇数集)和和不可数集不可数集(如实数集如实数集)。第17页，共181页，编辑于2022年，星期六集合的定义方法：集合的定义方法：列举列举法法命题命题法法第18页，共181页，编辑于2022年，星期六列举法列举法(穷举法穷举法)对于有穷的，且元素个数较少的集合，对于有穷的
8、，且元素个数较少的集合，可以采用列举法，可以采用列举法，即将集合的所有元素即将集合的所有元素全部列出全部列出，并放在一对花括号中。，并放在一对花括号中。例如例如集合集合A=1，2，3，4，5第19页，共181页，编辑于2022年，星期六对于某些无穷集合，也可以使用对于某些无穷集合，也可以使用类似列类似列举举的方法进行描述的方法进行描述如自然数集合：如自然数集合：0，1，2，3，第20页，共181页，编辑于2022年，星期六命题法命题法对于集合元素较多的有穷集合或者是无对于集合元素较多的有穷集合或者是无穷集合，可使用集合元素的形成模式穷集合，可使用集合元素的形成模式x|P(x)进行描述。进行描述
9、。其中：其中：x表示集合中的任一元素表示集合中的任一元素,P(x)是一是一个个谓词谓词，对，对x进行限定。进行限定。用来描述或判定客体性质、用来描述或判定客体性质、特征的词项。特征的词项。第21页，共181页，编辑于2022年，星期六x|P(x)表示表示由满足由满足P(x)的一切的一切x构成的集合。构成的集合。可以使用自然语言，或者数学表可以使用自然语言，或者数学表示法来描述（表达）谓词示法来描述（表达）谓词P(x)第22页，共181页，编辑于2022年，星期六例如：n|n是偶数是偶数或或n|nmod2=0描述了由所有偶数组成的集合。描述了由所有偶数组成的集合。第23页，共181页，编辑于20
10、22年，星期六集合的基数集合的基数若集合若集合A包含元素包含元素x，记为记为x A反之，反之，x A对于有穷集合对于有穷集合A，使用使用|A|表示该集合包表示该集合包含的元素的含的元素的个数个数，也称，也称基数基数或或势势|A|=0A=第24页，共181页，编辑于2022年，星期六定义定义1-1子集子集设设A,B是两个集合，如果集合是两个集合，如果集合A中的每个中的每个元素都是集合元素都是集合B的元素，则称集合的元素，则称集合A是集合是集合B的子集的子集(集合集合B是集合是集合A的包集的包集)A B 或或B A A,B是两个集合，如果是两个集合，如果A B，且且 x B，但但x A，则称则称A
11、是是B的的真子集真子集 A B第25页，共181页，编辑于2022年，星期六两个两个集合相等集合相等，当且仅当，当且仅当A B且且B A注意：注意：不是不是A B且且B A第26页，共181页，编辑于2022年，星期六定义定义1-2集合的运算集合的运算集合集合A与集合与集合B的并，记为的并，记为AB集集合合A的的所所有有元元素素和和集集合合B的的所所有有元元素素合并合并在一起组成的集合。在一起组成的集合。AB=x|xA或或xB第27页，共181页，编辑于2022年，星期六思考：什么情况下：什么情况下：AB=A？第28页，共181页，编辑于2022年，星期六集合集合A与集合与集合B的交，记为的交
12、，记为AB是由集合是由集合A和集合和集合B的所有的所有公共元素公共元素组组成的集合。成的集合。AB=x|xA且且xB第29页，共181页，编辑于2022年，星期六思考：什么情况下：什么情况下：AB=A？第30页，共181页，编辑于2022年，星期六集合集合A与集合与集合B的差，记为的差，记为A B属于属于集合集合A但但不属于集合不属于集合B的所有元素组的所有元素组成的集合。成的集合。A B=x|xA且且x B第31页，共181页，编辑于2022年，星期六思考思考:什么情况下：什么情况下：A-B=A？第32页，共181页，编辑于2022年，星期六如果如果B A，将，将A B称为集合称为集合B（关
13、于集（关于集合合A）的）的补补。集合集合A称为集合称为集合B的全集（或的全集（或论域论域）第33页，共181页，编辑于2022年，星期六定义定义1-3幂集幂集设设A为一个集合，那么为一个集合，那么A的的幂集幂集为为A的所有子集的所有子集组成的集合组成的集合记为记为2A2A=B|B A第34页，共181页，编辑于2022年，星期六例1-1集合集合A=1，2，3，则则A的幂集为的幂集为:2A=，1，2，3，1，2，1，3，2，3，1，2，3任取其中任取其中2个元素构成的集合个元素构成的集合第35页，共181页，编辑于2022年，星期六幂集幂集2A的元素个数的元素个数当当集合集合A为有穷集为有穷集时
14、，如果时，如果|A|=n，那么那么A的幂集的幂集2A的元素个数的元素个数(集合集合A的的所有子集的个数所有子集的个数)为为2n。（集合（集合A的幂集表示为的幂集表示为2A的原因）的原因）无论集合无论集合A A是有穷集合，还是无穷集合，都使用是有穷集合，还是无穷集合，都使用2 2A A表示集合表示集合A A的幂集。的幂集。第36页，共181页，编辑于2022年，星期六定义定义1-4笛卡儿积笛卡儿积集合集合A和和B的的笛卡儿笛卡儿乘积乘积 A B（也简记为（也简记为AB）A B=(a,b)|a A且且b B当当集合集合A、B为有穷集为有穷集时时|A B|=|A|*|B|第37页，共181页，编辑于
15、2022年，星期六例例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第38页，共181页，编辑于2022年，星期六思考思考什么情况下：什么情况下：A B=B A?第39页，共181页，编辑于2022年，星期六练习练习110之间的和为之间的和为10的整数的整数集合集合的集合的集合 第40页，共181页，编辑于2022年，星期六1,9,2,8,3,7,4,6,1,2,7,
16、1,3,6,1,4,5,2,3,5,1,2,3,4注意：注意：没有没有5，5第41页，共181页，编辑于2022年，星期六1.2关系关系1.2.1二元关系二元关系1.2.2等价关系等价关系与等价类与等价类1.2.3关系的关系的合成合成第42页，共181页，编辑于2022年，星期六1.2.1二元关系二元关系设设A和和B为两个集合，则为两个集合，则A B的的任何一个子集任何一个子集称为称为A到到B的一个二的一个二元关系。元关系。若若R为为A到到B的关系，当的关系，当(a,b)R时，可记为时，可记为aRb若若A=B，则称则称R为为A上上的关系的关系第43页，共181页，编辑于2022年，星期六思考：
17、思考：如果集合如果集合A和和B都是有穷集合，则都是有穷集合，则A到到B的的二元关系有多少个二元关系有多少个？A到到B的一个二元关系的一个二元关系最多最多可以有多少个元素可以有多少个元素？最少最少可以有多少个元素可以有多少个元素第44页，共181页，编辑于2022年，星期六例例1-3设设A为正整数集合，则为正整数集合，则A上的关系上的关系“”是集合是集合(a,b)|a,b A,且且a 0n0第118页，共181页，编辑于2022年，星期六(5)用用AB代表集合代表集合A与与B的连接的连接A=a1,a2,a3,anB=b1,b2,b3,bm第119页，共181页，编辑于2022年，星期六AB=a1
18、b1，a1b2，a1b3，a1bm，a2b1，a2b2，a2b3，a2bm，a3b1，a3b2，a3b3，a3bm，anb1，anb2，anb3，anbm第120页，共181页，编辑于2022年，星期六注意：A=A=第121页，共181页，编辑于2022年，星期六一般，一般，AB与与BA是不相等的。是不相等的。第122页，共181页，编辑于2022年，星期六思考思考:AB与与BA在什么情况下相等在什么情况下相等?1)当当A=B；2)A或或B中有一个为中有一个为,则则A=A=A3)A和和B中有一个为中有一个为，则则A=A=第123页，共181页，编辑于2022年，星期六6)An代表集合代表集合A
19、的的n次连接次连接(幂幂)A的的n次次幂幂定义为：定义为：(1)A0=(2)An=An-1An 1第124页，共181页，编辑于2022年，星期六7)A*代表代表A上所有字符串的集合上所有字符串的集合即即表表示示集集合合A中中的的所所有有字字符符串串进进行行任意次任意次连接连接而形成的串的集合而形成的串的集合第125页，共181页，编辑于2022年，星期六A*称为集合称为集合A的闭包的闭包(克林闭包克林闭包)A*=A0A1A2An第126页，共181页，编辑于2022年，星期六例 A=0，1A0=即即长度为长度为0的的0和和1组成的串的集合组成的串的集合A1=A=0,1即即长度为长度为1的的0
20、和和1组成的串的集合组成的串的集合第127页，共181页，编辑于2022年，星期六A2=AA=00,01,10,11即即长度为长度为2的的0和和1组成的串集合组成的串集合A3=A2A=000,001,010,011,100,101,110,111即即长度为长度为3的的0和和1组成的串的集合组成的串的集合第128页，共181页，编辑于2022年，星期六A*=A0A1A2An=0和和1组成的所有的串组成的所有的串=w|w是是0和和1组成的串组成的串第129页，共181页，编辑于2022年，星期六如如果果串串是是集集合合A的的闭闭包包中中的的串串，也称也称是集合是集合A上的串上的串。对于任何集合对于
21、任何集合A有有(A*)*=A*第130页，共181页，编辑于2022年，星期六8)A+称为称为A的正闭包的正闭包A+=AA2A3An第131页，共181页，编辑于2022年，星期六A*与 A+A*=A+A0即即A*=A+第132页，共181页，编辑于2022年，星期六注意：注意：A0=*=+=*=+=第133页，共181页，编辑于2022年，星期六思考思考是否对于任意的集合是否对于任意的集合A，都有都有A+=A*-第134页，共181页，编辑于2022年，星期六辨析与思考辨析与思考与|=1|=0 A=A A=第135页，共181页，编辑于2022年，星期六9）给给定定字字母母表表，则则*的的任
22、任意意子子集集L称为字母表称为字母表上的一个语言。上的一个语言。本本质质上上，语语言言L是是字字母母表表上上的的字字符串形成的符串形成的集合集合。第136页，共181页，编辑于2022年，星期六10)给给定定字字母母表表，L是是字字母母表表上上的一个语言，的一个语言，是是L的一个字符串的一个字符串称称为为L的一个的一个句子句子。第137页，共181页，编辑于2022年，星期六串的长度串的长度|=0；|=n；若若=a1a2a3an；其中：其中：ai，n0；第138页，共181页，编辑于2022年，星期六11)前缀和后缀：前缀和后缀：x,y,z*，且且x=yzy是是x的前缀；的前缀；如果如果z，则
23、称则称y是是x的的真前缀真前缀；z是是x的后缀；的后缀；如果如果y，则称则称z是是x的的真后缀真后缀；第139页，共181页，编辑于2022年，星期六例1-13串串abcde：前缀：前缀：，a，ab，abc，abcd，abcde真前缀：真前缀：，a，ab，abc，abcd后缀：后缀：，e，de，cde，bcde，abcde真后缀：真后缀：，e，de，cde，bcde第140页，共181页，编辑于2022年，星期六对于任意字符串对于任意字符串x，x的前缀有的前缀有|x|+1个个 真前缀有真前缀有|x|个个第141页，共181页，编辑于2022年，星期六对对于于任任何何字字符符串串x，x的的任任意
24、意前前缀缀y有有惟惟一一的的一一个个后后缀缀z与与之之对对应应，使使得得x=yz，反反之之亦然；亦然；对对于于任任何何字字符符串串x，x的的任任意意真真前前缀缀y有有惟惟一一的的一一个个真真后后缀缀z与与之之对对应应，使使得得x=yz，反之亦然（除了反之亦然（除了以外）；以外）；第142页，共181页，编辑于2022年，星期六对于任何字符串对于任何字符串xx是是自身的前缀自身的前缀，但，但不是真前缀不是真前缀x是是自身的后缀自身的后缀，但，但不是真后缀不是真后缀第143页，共181页，编辑于2022年，星期六对于任何字符串对于任何字符串x，是是x的前缀，且是真前缀；的前缀，且是真前缀；是是x的
25、后缀，且是真后缀；的后缀，且是真后缀；第144页，共181页，编辑于2022年，星期六思考：思考：对于对于，前缀是？真前缀？前缀是？真前缀？后缀是？真后缀？后缀是？真后缀？第145页，共181页，编辑于2022年，星期六12)语言的前缀性质语言的前缀性质设设L是某个字母表上的语言是某个字母表上的语言如如果果L中中的的任任何何句句子子都都是是另另一一个个句句子子的的真真前前缀缀，则则称称语语言言L具具有有前前缀缀性性质质。第146页，共181页，编辑于2022年，星期六例1-14字母表字母表0，1上的语言上的语言L1=0n|n=0具有前缀性质；具有前缀性质；语言语言L2=0n1|n=0不具有前缀
26、性质。不具有前缀性质。第147页，共181页，编辑于2022年，星期六语言与句子语言与句子设设 是一个字母表，是一个字母表，L *,L称称为字母表为字母表 上的一个上的一个语言语言 x L,x称为称为L的一个的一个句子句子。语言的可分为语言的可分为有穷语言有穷语言与与无穷语言无穷语言第148页，共181页，编辑于2022年，星期六语言的乘积语言的乘积设设 1,2是两个字母表是两个字母表L1 1*,L2 2*,语言语言L1与与L2的乘积是一个语言：的乘积是一个语言：L1L2=xy|x L1,y L2该语言是字母表该语言是字母表 1 2上的语言上的语言第149页，共181页，编辑于2022年，星期
27、六语言的例子语言的例子字母表字母表0,1上的一些语言：上的一些语言：00,110,1,00,1100,1*10,1*1110,1*第150页，共181页，编辑于2022年，星期六语言的语言的n次幂次幂设设 是一个字母表，是一个字母表，L *,L的的n次幂是一个语言次幂是一个语言(1)当当n=0时，时，Ln=(2)当当n 1时，时，Ln=Ln-1 L第151页，共181页，编辑于2022年，星期六语言的例子语言的例子令令=0,1，L=0,1L=0,1,00,01,10,11,=+L=,0,1,00,01,10,11,=*第152页，共181页，编辑于2022年，星期六L=0n1n|n 1L=0n
28、1m0k|n,m,k 1L=0n1m0k|n,m,k 第153页，共181页，编辑于2022年，星期六语言的闭包语言的闭包L的正闭包的正闭包L+是一个语言：是一个语言：L+=LL2L3L的克林闭包的克林闭包L*是一个语言：是一个语言：L*=L0L+第154页，共181页，编辑于2022年，星期六1.7形式语言与自动机的发展形式语言与自动机的发展l语语言言学学家家Chomsky(乔乔姆姆斯斯基基)最最早早从从产产生生语语言言的的角角度度研研究究语语言言。1956年年，通通过过抽抽象象，Chomsky将将语语言言形形式式地地定定义义为为由由一一个个字字母母表表的的字字母母组组成成的的一一些些串串的
29、的集集合合：对对于于任任意意语语言言L，有有一一个个字字母母表表，使使得得LC*。可可以以在在字字母母表表上上按按照照一一定定的的形形成成规规则则定定义义一一个个文文法法，该该文文法法产产生生的的所所有有的的句句子子组组成成的的集集合合就就是是该该文法产生的语言。文法产生的语言。第155页，共181页，编辑于2022年，星期六l1959年年，Chomsky根根据据产产生生语语言言的的文文法法的的产产生生式式的的不不同同特特点点，将将文文法法和和对对应应产产生生的的语语言言分为三大类。分为三大类。第156页，共181页，编辑于2022年，星期六l数数学学家家Kleene（克克林林）在在19511
30、956年年间间，从从识识别别语语言言的的角角度度来来研研究究语语言言，给给出出了了语语言言的的另另一一种种描描述述方方式式。Kleene在在研研究究神神经经细细胞胞时时建建立立了了自自动动机机模模型型，Kleene使使用用该该模模型型来来识识别别（接接收收）一一个个语语言言：按按照照某某种种识识别别规规则则构构造造自自动动机机，该该自自动动机机就就定定义义了了一一个个语语言言，该该语语言言由由自自动动机机能能够识别的所有字符串构成。够识别的所有字符串构成。第157页，共181页，编辑于2022年，星期六l语语言言的的两两种种不不同同的的定定义义方方式式进进一一步步引引起起了了人人们们的的研研究
31、究兴兴趣趣。一一个个语语言言，可可以以采采取取不不同同的的描描述述方方式式：文文法法产产生生语语言言和和自自动动机机识识别别语语言言。由由于于是是同同一一个个语语言言，两两种种方方式式应应该该是是等等价价的的，也也就就存存在在两两种种方方式式之之间间的的等等价价的的相相互互转转换换方方法。法。第158页，共181页，编辑于2022年，星期六lChomsky于于1959年年，将将他他本本人人的的形形式式语语言言的的研研究究成成果果和和Kleene的的自自动动机机的的研研究究成成果果结结合合起起来来，不不仅仅确确定定了了文文法法和和自自动动机机分分别别从从产产生生和和识识别别角角度度定定义义语语言
32、言，而而且且证证明明了了文文法法与与自自动动机机的的等等价价性性。此此时时，形形式式语语言言与与自自动动机机理理论论才才真真正正诞诞生生。并被置于数学的光芒之下。并被置于数学的光芒之下。第159页，共181页，编辑于2022年，星期六l形形式式语语言言与与自自动动机机理理论论出出现现后后，迅迅速速在在计计算算机机科科学学技技术术领领域域得得到到了了应应用用。使使用用巴巴科科斯斯-诺诺尔尔范范式式（BNF-Backus-NaurForm）成成功功地地对对高高级级程程序序设设计计语语言言ALGOL-60的的词词法法和和语语法法规规则则进进行行了了形形式式化化的的描描述述（实实际际上上，巴巴科科斯斯
33、-诺诺尔尔范范式式就就是是上上下下文文无无关关文文法法的的产产生生式式另另一一种种表表示示方方式式）。这这一一成成功功，使使得得形形式式语语言言与与自自动动机机理理论论得得到到了了进进一一步步的发展。的发展。第160页，共181页，编辑于2022年，星期六l尤尤其其是是上上下下文文无无关关文文法法，被被作作为为计计算算机机程程序序设设计计语语言言语语法法的的最最佳佳近近似似描描述述得得到到了了较较为为深深入入的的研研究究。后后来来，人人们们又又将将上上下下文文无无关关文文法法应应用用到到了了模模式式匹匹配配和和模模型型化化处处理理等等方方面面，而而这这些些内内容容都都是是算算法法描描述述和和分
34、分析析、计计算算复复杂杂性性理论和可计算性理论的研究基础。理论和可计算性理论的研究基础。第161页，共181页，编辑于2022年，星期六l形形式式语语言言理理论论的的研研究究对对象象与与以以前前的的所所有有语语言言研研究究不不同同，不不止止自自然然语语言言，而而是是人人类类一一切切语语言言：既既有有自自然然语语言言，也也有有人人工工语语言言，包包括括计计算算机机编编程程的的高高级级语语言言。乔乔姆姆斯斯基基的的形形式式语语言言理理论论得得到到了了多多重重验验证证，于于是是才才为为语语言言学学界界和和计计算算机机科科学学界界所所折折服服，“引引发发了了语语言言学学中中伽伽利略式的科学革命的开端。
35、利略式的科学革命的开端。”第162页，共181页，编辑于2022年，星期六l乔乔姆姆斯斯基基的的形形式式语语言言理理论论得得到到过过计计算算机机科科学的三种验证。学的三种验证。第163页，共181页，编辑于2022年，星期六l验验证证一一：乔乔氏氏4型型文文法法与与4种种语语言言自自动动机机一一一一对对应。应。第164页，共181页，编辑于2022年，星期六l验验证证二二：计计算算机机所所使使用用的的各各种种高高级级语语言言，如如ALGOL、FORTRAN、PASCAL、C、LISP等等，都都遵遵循循一一种种程程序序语语言言文文法法描描述述的的范范式式，即即巴巴科科斯斯诺诺尔尔范范式式。计计算
36、算机机科科学学家家发发现现，巴巴科科斯斯诺诺尔尔范范式式等等价价于于乔乔姆姆斯斯基基的的2型型文文法法，即即与与上上下下文文无无关关文文法法。而而乔乔姆姆斯斯基基的的3型型文文法法正正则则文文法法，在在研研究究文文字字的的计计算算机机模模式式识识别别时时，也也被被有有效效应应用用。于于是是，乔乔氏氏的的4种种类类型型文文法法被被计计算算机机科科学学界界称称作作乔姆斯基分类。乔姆斯基分类。第165页，共181页，编辑于2022年，星期六l验验证证三三：乔乔姆姆斯斯基基用用形形式式语语言言理理论论的的思思想想证证明明了了计计算算机机科科学学的的一一个个重重大大理理论论问问题题：计计算算机机程程序序
37、语语言言是是否否有有歧歧义义性性是是不可判定的。不可判定的。l20世世纪纪中中期期，程程序序语语言言ALGOL60问问世世不不久久，人人们们发发现现它它有有歧歧义义性性。当当计计算算机机科科学学家家绞绞尽尽脑脑汁汁寻寻找找办办法法来来判判断断一一种种程程序序语语言言是是否否有有歧歧义义性性时时，乔乔姆姆斯斯基基用用形形式式语语言言理理论论的的思思想想证证明明，一一个个任任意意的的上上下下文文无无关关文文法法是是否否有有歧歧义义性性是是不不可可判判定定的的，因因此此，属属于于上上下下文文无无关关文文法法的的程程序序语语言言是是否否有有歧歧义义性也是不可判定的。乔姆斯基的论证令计算机科学界折服。性
38、也是不可判定的。乔姆斯基的论证令计算机科学界折服。第166页，共181页，编辑于2022年，星期六l实实际际上上，形形式式语语言言与与自自动动机机理理论论除除了了在在计计算算机机科科学学与与技技术术领领域域的的直直接接应应用用外外，更更在在计计算算机机计计算算机机科科学学与与技技术术领领域域的的人人才才的的计计算算思思维维能能力力的的培培养养中中占占有极其重要的地位。有极其重要的地位。第167页，共181页，编辑于2022年，星期六l计算机科学与技术学科强调计算机科学与技术学科强调4个方面的专业能个方面的专业能力：计算思维能力、算法设计与分析能力、力：计算思维能力、算法设计与分析能力、程序设计
39、与实现能力、计算机系统的认知、程序设计与实现能力、计算机系统的认知、分析、设计和运用能力。这也是计算机科分析、设计和运用能力。这也是计算机科学与其他学科的重要区别。相关的理论是学与其他学科的重要区别。相关的理论是计算机学科的基础。计算机学科的基础。l理论方面的知识是计算机的真正灵魂。理论方面的知识是计算机的真正灵魂。第168页，共181页，编辑于2022年，星期六l在本科阶段的学习过程中，学生以观察、在本科阶段的学习过程中，学生以观察、描述、比较、分类、推断、应用、创造描述、比较、分类、推断、应用、创造思维等科学思维过程为主，强调自学的思维等科学思维过程为主，强调自学的能力在培养；能力在培养；
40、l研究生阶段，需要对学生进一步进行抽研究生阶段，需要对学生进一步进行抽象思维、逻辑思维、创造思维能力的培象思维、逻辑思维、创造思维能力的培养。养。第169页，共181页，编辑于2022年，星期六l建建立立物物理理符符号号系系统统并并对对起起实实施施等等价价变变换换是是计计算算机机学学科科进进行行问问题题描描述述和和求求解解的的重重要要手手段段。“可可行行性性”所所要要求求的的“形形式式化化”及及其其“离离散散特特征征”使使得得数数学学成成为为重重要要的的工工具具，而而计计算算模模型型无无论论从从方方法法还还是是从从工工具具等等方方面面，都表现出它在计算机上科学中的重要作用。都表现出它在计算机上
41、科学中的重要作用。第170页，共181页，编辑于2022年，星期六l计计算算机机科科学学与与技技术术学学科科要要求求学学生生具具有有形形式式化化描描述述和和抽抽象象思思维维能能力力，要要求求掌掌握握逻逻辑辑思思维维方方法法。这这种种能能力力就就是是计计算算思思维维能能力或计算机思维能力。力或计算机思维能力。第171页，共181页，编辑于2022年，星期六l计计算算机机学学科科系系统统地地研研究究信信息息描描述述和和变变换换算算法法，重重要要包包括括信信息息描描述述和和变变换换算算法法的的理理论论、分分析析、效效率率、实实现现和和运运用用。学学科科的的根根本本问问题题在在于于：什什么么能能被被（
42、有有效效地地）自自动动化化？学学科科的的重重要要内内容容之之一一是是研研究究计计算算领领域域中中的的一一些些普普遍遍规规律律，描描述述算算法法的的基本概念与模型。基本概念与模型。第172页，共181页，编辑于2022年，星期六l计算思维能力的培养主要是通过基础计算思维能力的培养主要是通过基础理论系列课程实现的，该系列是由数理论系列课程实现的，该系列是由数学和抽象度较高的理论课程组成，包学和抽象度较高的理论课程组成，包括数学分析、集合和图论、形式语言括数学分析、集合和图论、形式语言与自动机、近世代数、数学建模等课与自动机、近世代数、数学建模等课程。程。第173页，共181页，编辑于2022年，星
43、期六练习练习(见习题见习题)l3(2)l4第174页，共181页，编辑于2022年，星期六3 给出下列对象的递归定义对于任意对于任意x *,字符串字符串x的倒序的倒序(1)若若|x|1，令令x=ya，其中其中y +,a ，则则xT=ayT第175页，共181页，编辑于2022年，星期六4 0，1，请给出语言的形式表示，请给出语言的形式表示l所有以所有以0开头的串的语言。开头的串的语言。l所有以所有以0开头，以开头，以1结尾的串的语言。结尾的串的语言。l所有以所有以11开头，开头，11结尾的串的语言。结尾的串的语言。l所有最多有一对连续的所有最多有一对连续的0或者最多有一或者最多有一对连续的对连
44、续的1的串的语言。的串的语言。l所有长度为偶数的串的语言。所有长度为偶数的串的语言。第176页，共181页，编辑于2022年，星期六l所有长度为奇数的串的语言。所有长度为奇数的串的语言。l所有包含子串所有包含子串01011的串的语言。的串的语言。l所有包含所有包含3个连续个连续0的串的语言。的串的语言。l所有的第所有的第10个字符是个字符是0的串的语言。的串的语言。l所有倒数第所有倒数第6个字符是个字符是0的串的语言。的串的语言。第177页，共181页，编辑于2022年，星期六习题评讲习题评讲(续续)l4(1)00,1*(2)00,1*1(3)110,1*11111，11(4)?第178页，共181页，编辑于2022年，星期六习题评讲习题评讲(续续)(5)0,10,1*(6)0,10,1*0,1(7)0,1*010110,1*(8)0,1*0000,1*第179页，共181页，编辑于2022年，星期六习题评讲习题评讲(续续)(9)0,1900,1*(10)0,1*00,15第180页，共181页，编辑于2022年，星期六小结小结l复习复习集合、关系、图集合、关系、图等相关知识等相关知识l引入引入形式语言形式语言基本概念基本概念第181页，共181页，编辑于2022年，星期六