形式语言与自动机理论电子教案省公共课一等奖全国赛课获奖课件.pptx

/10/101形式语言与自动机理论形式语言与自动机理论FormalLanguagesandAutomataTheory蒋宗礼蒋宗礼第1页/10/102课程目和基本要求课程性质课程性质技术基础技术基础基础知识要求基础知识要求数学分析（或者高等数学），离散数学数学分析（或者高等数学），离散数学主要特点主要特点抽象和形式化抽象和形式化理论证实和结构性理论证实和结构性基本模型建立与性质基本模型建立与性质 第2页/10/103课程目和基本要求本专业人员本专业人员4 4种基本专业能力种基本专业能力计算思维能力计算思维能力算法设计与分析能力算法设计与分析能力程序设计和实现能力程序设计和实现能力计算机软硬件系统认知、分析、设计与应用能力计算机软硬件系统认知、分析、设计与应用能力计算思维能力计算思维能力逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力结构模型对问题进行形式化描述结构模型对问题进行形式化描述了解和处理形式模型了解和处理形式模型第3页/10/104课程目和基本要求 知识知识掌握正则语言、下文无关语言文法、识别模型掌握正则语言、下文无关语言文法、识别模型及其基本性质、图灵机基本知识。及其基本性质、图灵机基本知识。能力能力培养学生形式化描述和抽象思维能力。培养学生形式化描述和抽象思维能力。使学生了解和初步掌握使学生了解和初步掌握“问题、形式化描述、问题、形式化描述、自动化（计算机化）自动化（计算机化）”这一最经典计算机问题这一最经典计算机问题求解思绪。求解思绪。第4页/10/105主要内容主要内容 语言语言文法文法描述。描述。RLRG、FA、RE、RL性质性质。CFLCFG(CNF、GNF)、PDA、CFL性质。性质。TM基本基本TM、结构技术、结构技术、TM修改。修改。CSLCSG、LBA。第5页/10/106教材及主要参考书目教材及主要参考书目蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，John E Hopcroft,Rajeev Motwani,Jeffrey D Ullman.Introduction to Automata Theory,Languages,and Computation(2nd Edition).Addison-Wesley Publishing Company,John E Hopcroft,Jeffrey D Ullman.Introduction to Automata Theory,Languages,and Computation.Addison-Wesley Publishing Company,1979第6页/10/107第第1章章绪论绪论1.1集合基础知识集合基础知识1.1.1集合及其表示集合及其表示集集合合：一一定定范范围围内内、确确定定、而而且且彼彼此此能能够够区区分分对对象象聚聚集集在在一一起起形形成成整整体体叫叫做做集集合合(set)，简简称称为为集集(set)。元素：集合组员为该集合元素：集合组员为该集合元素元素(element)。集合描述形式。集合描述形式。基数。基数。集合分类。集合分类。第7页/10/1081.1.2集合之间关系集合之间关系 子集子集假假如如集集合合A中中每每个个元元素素都都是是集集合合B元元素素，则则称称集集合合A是是集集合合B子子集集(subset)，集集合合B是是集集合合A包包集集(container)。记记作作A B。也也可可记记作作B A。A B读读作作集集合合A包包含含在在集集合合B中中；B A读读作作集合集合B包含集合包含集合A。假假如如A B，且且 xB，但但x A，则则称称A是是B真真子集子集(propersubset)，记作，记作A B第8页/10/1091.1.2集合之间关系集合之间关系集合相等集合相等假假如如集集合合A，B含含有有元元素素完完全全相相同同，则则称称集集合合A与集合与集合B相等相等(equivalence)，记作，记作A=B。对任意集合对任意集合A、B、C：A=BiffA B且且B A。假如假如A B，则，则|A|B|。假如假如A B，则，则|A|B|。假如假如A是有穷集，且是有穷集，且A B，则，则|B|A|。第9页/10/10101.1.2集合之间关系集合之间关系假如假如A B，则对，则对 xA，有，有xB。假假 如如 A B，则则 对对 xA，有有 xB而而 且且 xB，但，但x A。假如假如A B且且B C，则，则A C。假假如如A B且且B C，或或者者A B且且B C，或者或者A B且且B C，则，则A C。假如假如A=B，则，则|A|=|B|。第10页/10/10111.1.3集合运算集合运算 并并(union)A与与B并并(union)是是一一个个集集合合，该该集集合合中中元元素素要要么么是是A元素，要么是元素，要么是B元素，记作元素，记作AB。AB=a|aA或者或者aBA1A2An=a|i，1in，使得，使得aAiA1A2An=a|i，iN,使得使得aAi第11页/10/1012交交(intersection)集集合合A和和B中中都都有有全全部部元元素素放放在在一一起起组组成成集集合为合为A与与B交交，记作，记作AB。AB=a|aA且且aB“”为交运算符，为交运算符，AB读作读作A交交B。假如假如AB=，则称，则称A与与B不相交。不相交。AB=BA。(AB)C=A(BC)。AA=A。第12页/10/1013交交(intersection)AB=AiffA B。A=。|AB|min|A|，|B|。A(BC)=(AB)(AC)。A(BC)=(AB)(AC)。A(AB)=A。A(AB)=A。第13页/10/1014差差(difference)属属于于A，但但不不属属于于B全全部部元元素素组组成成集集合合叫叫做做A与与B差，记作差，记作A-B。A-B=a|aA且且a B“-”为减为减(差差)运算符，运算符，A-B读作读作A减减B。A-A=。A-=A。A-BB-A。A-B=AiffAB=。A(B-C)=(AB)-(AC)。|A-B|A|。第14页/10/1015对称差对称差(symmetricdifference)属属于于A但但不不属属于于B，属属于于B但但不不属属于于A全全部部元元素素组成集合叫组成集合叫A与与B对称差，记作对称差，记作ABAB。AB=a|aAAB=a|aA且且a a B B或者或者a a A A且且aB aB“”为对称差运算符。为对称差运算符。ABAB读作读作A A对称减对称减B B。AB=(AB)-(AB)=(A-B)(B-A)AB=(AB)-(AB)=(A-B)(B-A)。第15页/10/1016笛卡儿积笛卡儿积(Cartesianproduct)A与与B笛笛卡卡儿儿积积(Cartesianproduct)是是一一个个集集合合，该该集集合合是是由由全全部部这这么么有有序序对对(a，b)组组成成：其其中中aA，bB，记作，记作AB。AB=(a，b)|aA&bB。“”为笛卡儿乘运算符。为笛卡儿乘运算符。AB读作读作A叉乘叉乘B。ABBA。(AB)CA(BC)。AAA。A=。第16页/10/1017笛卡儿积笛卡儿积(Cartesianproduct)A(BC)=(AB)(AC)。(BC)A=(BA)(AC)。A(BC)=(AB)(AC)。(BC)A=(BA)(CA)。A(B-C)=(AB)-(AC)。(B-C)A=(BA)-(CA)。当当A、B为有穷集时，为有穷集时，|AB|=|A|*|B|。第17页/10/1018幂集幂集(powerset)A幂集幂集(powerset)是一个集合，该集合是是一个集合，该集合是由由A全部子集组成，记作全部子集组成，记作2A。2A=B|B A。2A读作读作A幂集。幂集。第18页/10/1019幂集幂集(powerset)2A。2A。2A。2=。A2A。假如假如A是有穷集，则是有穷集，则|2A|=2|A|。2AB=2A2B。假如假如A B，则，则2A 2B。第19页/10/1020补集补集(complementaryset)A是论域U上一个集合，A补集补集是由U中、不在A中全部元素组成集合，记作第20页/10/1021补集补集(complementaryset)假如假如A B，则，则。第21页/10/10221.2关系关系 二元关系二元关系递归定义与归纳证实递归定义与归纳证实关系闭包关系闭包 第22页/10/10231.2.1二元关系二元关系(binaryrelation)二元关系二元关系 任意RAB，R是A到B二元关系。二元关系。(a，b)R，也可表示为：aRb。A称为定义域定义域(domain)，B称为值域值域(range)。当A=B时，则称R是A上二元关系。二元关系性质二元关系性质自反(reflexive)性、反自反(irreflexive)性、对称(symmetric)性、反对称(asymmetric)性、传递(transitive)性。第23页/10/10241.2.1二元关系二元关系(binaryrelation)三歧性三歧性自反性、对称性、传递性。自反性、对称性、传递性。等价关系等价关系(equivalencerelation)含有三歧性二元关系称为等价关系。等价关系。第24页/10/10251.2.1二元关系二元关系(binaryrelation)等价类等价类(equivalenceclass)S满足以下要求划分：满足以下要求划分：S1、S2、S3、Sn称为称为S关于关于R等价划分，等价划分，Si称为等价类。称为等价类。S=S1S2S3Sn；假如假如ij，则，则SiSj=；对任意对任意i，Si中任意两个元素中任意两个元素a、b，aRb恒成立；恒成立；对任意对任意i，j，ij，Si中任意元素中任意元素a和和Sj中任意元素中任意元素b，aRb恒不成立恒不成立第25页/10/10261.2.1二元关系二元关系(binaryrelation)指数指数(index)把把R将将S分成等价类个数称为是分成等价类个数称为是R在在S上上指数指数。假如假如R将将S分成有穷多个等价类，则称分成有穷多个等价类，则称R含有有含有有穷指数；假如穷指数；假如R将将S分成无穷多个等价类，则称分成无穷多个等价类，则称R含有没有穷指数。含有没有穷指数。给定集合给定集合S上一个等价关系上一个等价关系R，R就确定了就确定了S一一个等价分类，当给定另一个不一样等价关系时，个等价分类，当给定另一个不一样等价关系时，它会确定它会确定S一个新等价分类。一个新等价分类。第26页/10/10271.2.1二元关系二元关系(binaryrelation)关系合成关系合成(composition)设设R1 AB是是A到到B关系、关系、R2 BC是是B到到C关关系，系，R1与与R2合成合成R1R2是是A到到C关系：关系：R1R2=(a，c)|(a，b)R1且且(b，c)R2。第27页/10/10281.2.1二元关系二元关系(binaryrelation)R1R2R2R1。(R1R2)R3=R1(R2R3)。(结合率结合率)(R1R2)R3=R1R3R2R3。(右分配率右分配率)R3(R1R2)=R3R1R3R2。(左分配率左分配率)(R1R2)R3 R1R3R2R3。R3(R1R2)R3R1R3R2。第28页/10/10291.2.1二元关系二元关系(binaryrelation)1.关关系系这这一一个个概概念念用用来来反反应应对对象象集集合合元元素之间联络和性质素之间联络和性质2.二二元元关关系系则则是是反反应应两两个个元元素素之之间间关关系系，包包含某个元素某种属性。含某个元素某种属性。3.对对二二元元关关系系性性质质，要要强强调调全全称称量量词词是是对对什什么样范围而言。么样范围而言。第29页/10/10301.2.2等价关系与等价类等价关系与等价类（略）1.2.3关系合成关系合成（略）第30页/10/10311.2.4递归定义与归纳证实递归定义与归纳证实递归定义(recursivedefinition)又称为归纳定义(inductivedefinition)，它来定义一个集合。集合递归定义由三部分组成：基础(basis)：用来定义该集合最基本元素。归纳(induction)：指出用集合中元素来结构集合新元素规则。极小性限定：指出一个对象是所定义集合中元素充要条件是它能够经过有限次使用基础和归纳条款中所给要求结构出来。第31页/10/10321.2.4递归定义与归纳证实递归定义与归纳证实归纳证实归纳证实与递归定义相对应。与递归定义相对应。归纳证实方法包含三大步：归纳证实方法包含三大步：基础基础(basis)：证实最基本元素含有对应性质。：证实最基本元素含有对应性质。归纳归纳(induction)：证实假如一些元素含有对：证实假如一些元素含有对应性质，则依据这些元素用所要求方法得到应性质，则依据这些元素用所要求方法得到新元素也含有对应性质。新元素也含有对应性质。依据归纳法原理，全部元素含有对应性质。依据归纳法原理，全部元素含有对应性质。第32页/10/10331.2.4递归定义与归纳证实递归定义与归纳证实定义定义1-17设设R是是S上关系，我们递归地定义上关系，我们递归地定义Rn幂：幂：R0=(a，a)|aS。Ri=Ri-1R(i=1,2,3,4,5,)。第33页/10/10341.2.4递归定义与归纳证实递归定义与归纳证实例例1-17著名斐波那契著名斐波那契(Fibonacci)数定义数定义基基础础：0是是第第一一个个斐斐波波那那契契数数，1第第二二个个斐斐波波那契数；那契数；归归纳纳：假假如如n是是第第i个个斐斐波波那那契契数数，m是是第第i+1个个斐斐波波那那契契数数，则则n+m是是第第i+2个个斐斐波波那那契契数数，这里这里i为大于等于为大于等于1正整数。正整数。只有满足只有满足(1)和和(2)数才是斐波那契数数才是斐波那契数0，1，1，2，3，5，8，13，21，34，55，第34页/10/10351.2.4递归定义与归纳证实递归定义与归纳证实例例1-18算术表示式算术表示式基基础础：常常数数是是算算术术表表示示式式，变变量量是是算算术术表表示式；示式；归归纳纳：假假如如E1、E2是是表表示示式式，则则+E1、-E1、E1+E2、E1-E2、E1*E2、E1/E2、E1*E2、Fun(E1)是算术表示式。其中是算术表示式。其中Fun为函数名。为函数名。只有满足只有满足(1)和和(2)才是算术表示式。才是算术表示式。第35页/10/10361.2.4递归定义与归纳证实递归定义与归纳证实例例1-19对有穷集合对有穷集合A，证实，证实|2A|=2|A|。证实：证实：设设A为一个有穷集合为一个有穷集合,施归纳于施归纳于|A|：基础：当基础：当|A|=0时时,|2A|=|=1。归纳：假设归纳：假设|A|=n时结论成立，这里时结论成立，这里n0，往证当，往证当|A|=n+1时结论成立时结论成立 2A=2BCa|C2B2BCa|C2B=第36页/10/10371.2.4递归定义与归纳证实递归定义与归纳证实|2A|=|2BCa|C2B|=|2B|+|Ca|C2B|=|2B|+|2B|=2*|2B|=2*2|B|=2|B|+1=2|A|由归纳法原理，结论对任意有穷集合成立。由归纳法原理，结论对任意有穷集合成立。第37页/10/10381.2.4递归定义与归纳证实递归定义与归纳证实例例1-20表示式前缀形式是指将运算符写表示式前缀形式是指将运算符写在前面，后跟对应运算对象。如：在前面，后跟对应运算对象。如：+E1前缀形前缀形式为式为+E1，E1+E2前缀形式为前缀形式为+E1E2，E1*E2前前缀形式为缀形式为*E1E2，E1*E2前缀形式为前缀形式为*E1，Fun(E1)前缀形式为前缀形式为FunE1。证实例证实例1-18所定义表示式能够用这里定义所定义表示式能够用这里定义前缀形式表示。前缀形式表示。第38页/10/10391.2.4递归定义与归纳证实递归定义与归纳证实递归定义给出概念有利于归纳证实。在计递归定义给出概念有利于归纳证实。在计算机科学与技术学科中，有许多问题能够算机科学与技术学科中，有许多问题能够用递归定义描述或者用归纳方法进行证实，用递归定义描述或者用归纳方法进行证实，而且在许多时候，这么做会带来许多方便。而且在许多时候，这么做会带来许多方便。主要是掌握主要是掌握递归定义与归纳证实递归定义与归纳证实叙述格式。叙述格式。第39页/10/10401.2.5关系闭包关系闭包闭包闭包(closure)设设P是关于关系性质集合，关系是关于关系性质集合，关系RP闭包闭包(closure)是包含是包含R而且含有而且含有P中全部性质最小中全部性质最小关系关系。正闭包正闭包(positiveclosure)(1)R R+。(2)假如假如(a，b)，(b，c)R+则则(a，c)R+。(3)除除(1)、(2)外，外，R+不再含有其它任何元素不再含有其它任何元素。第40页/10/10411.2.5关系闭包关系闭包传递闭包传递闭包(transitiveclosure)含有传递性闭包。含有传递性闭包。R+含有传递性。含有传递性。能够证实，对任意二元关系能够证实，对任意二元关系R，R+=RR2R3R4而且当而且当S为有穷集时：为有穷集时：R+=RR2R3R|S|第41页/10/10421.2.5关系闭包关系闭包克林闭包克林闭包(Kleeneclosure)R*(1)R R0 0 R R*,R,R R R*。(2)假如假如(a(a，b)b)，(b(b，c)Rc)R*则则(a(a，c)Rc)R*。(3)除除(1)(1)、(2)(2)外，外，R R*不再含有其它任何元素。不再含有其它任何元素。自反传递闭包自反传递闭包(reflexiveandtransitiveclosure)R*含有自反性、传递性含有自反性、传递性。第42页/10/10431.2.5关系闭包关系闭包能够证实，对任意二元关系能够证实，对任意二元关系R，R*=R0R+R*=R0RR2R3R4而且当而且当S为有穷集时：为有穷集时：R*=R0RR2R3R|S|第43页/10/10441.2.5关系闭包关系闭包R1、R2是是S上两个二元关系上两个二元关系(1)+=。(2)(R1+)+=R1+。(3)(R1*)*=R1*。(4)R1+R2+(R1R2)+。(5)R1*R2*(R1R2)*。第44页/10/10451.3图图数学家欧拉数学家欧拉(L.Euler)处理著名哥尼斯堡七桥。处理著名哥尼斯堡七桥。直观地讲，图是由一些点和一些连接两点直观地讲，图是由一些点和一些连接两点边组成。边组成。含无方向边图为无向图，含带有方向边图含无方向边图为无向图，含带有方向边图为有向图。为有向图。第45页/10/10461.3.1无向图无向图无向图无向图(undirectedgraph)设设V是一个非空有穷集合，是一个非空有穷集合，E VV，G=(V，E)称为称为无向图无向图(undirectedgraph)。其中。其中V中元中元素称为素称为顶点顶点(vertex或或node)，V称为顶点集，称为顶点集，E中元素称为中元素称为无向边无向边(undirectededge)，E为无向为无向边集。边集。图表示图表示V中称为顶点中称为顶点v元素用标识为元素用标识为v小圈表示，小圈表示，E中元中元素素(v1，v2)用标识为用标识为v1，v2顶点之间连线表示。顶点之间连线表示。第46页/10/10471.3.1无向图无向图路路(path)假如对于假如对于0ik-1，k1，都有，都有(vi，vi+1)E，则，则称称v0，v1，vk是是G=(V，E)一条长为一条长为k路。路。回路或圈回路或圈(cycle)当路当路v0，v1，vk中中v0=vk时，时，v0，v1，vk叫做一个叫做一个回路或圈回路或圈(cycle)。第47页/10/10481.3.1无向图无向图顶点度数顶点度数对对于于vV，|v|(v，w)E|称称为为无无向向图图G=(V，E)顶点顶点v度数，记作度数，记作deg(v)。对于任何一个图，图中全部顶点度数之和为图对于任何一个图，图中全部顶点度数之和为图中边中边2倍。倍。第48页/10/1049deg(v1)=3deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=3deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=16第49页/10/10501.3.1无向图无向图连通图连通图假如对于假如对于 v，wV，vw，v与与w之间最少有之间最少有一条路存在，则称一条路存在，则称G=(V，E)是是连通图连通图。图图G是连通充要条件是是连通充要条件是G中存在一条包含图全中存在一条包含图全部顶点路。部顶点路。第50页/10/10511.3.2有向图有向图有向图有向图(directedgraph)G=(V，E)。V：顶点顶点(vertex或或node)集。集。(v1，v2)E：顶点顶点v1到顶点到顶点v2有向边有向边(directededge)，或，或弧弧(arc)，v1称为称为前导前导(predecessor)，v2称为称为后继后继(successor)。有向路有向路(directedpath)假如对于假如对于0ik-1，k1，都有，都有(vi，vi+1)E，则，则称称v0，v1，vk是是G一条长为一条长为k有向路。有向路。第51页/10/10521.3.2有向图有向图有向回路或有向圈有向回路或有向圈(directedcycle)对于对于0ik-1，k1，都有，都有(vi，vi+1)E，且且v0=vk，则称，则称v0，v1，vk是是G一条长为一条长为k有向有向路为路为一个一个有向回路。有向回路。有向回路又叫有向圈。有向回路又叫有向圈。有向图图表示有向图图表示图图G G图表示是满足以下条件图表示是满足以下条件“图图”：其中：其中V V中称中称为顶点为顶点v v元素用标识为元素用标识为v v小圈表示，小圈表示，E E中元素中元素(v(v1 1，v v2 2)用从标识为用从标识为v v1 1顶点到标识为顶点到标识为v v2 2顶点弧表示。顶点弧表示。第52页/10/10531.3.2有向图有向图顶点度数顶点度数入度入度(数数)：ideg(v)=|v|(w，v)E|。出度出度(数数)：odeg(v)=|v|(v，w)E|。对于任何一个有向图，图中全部顶点入度对于任何一个有向图，图中全部顶点入度之和与图中全部顶点出度之和恰好是图中之和与图中全部顶点出度之和恰好是图中边个数边个数第53页/10/1054两个不一样有向图两个不一样有向图第54页/10/10551.3.3树树满足以下条件有向图满足以下条件有向图G=(V，E)称为一棵称为一棵(有有序、有向序、有向)树树(tree)：根根(root)v：没有前导，且没有前导，且v到树中其它顶点都到树中其它顶点都有一条有向路。有一条有向路。每个非根顶点有且仅有一个前导。每个非根顶点有且仅有一个前导。每个顶点后继按其拓扑关系从左到右排序。每个顶点后继按其拓扑关系从左到右排序。第55页/10/10561.3.3树树树基本概念树基本概念(1)顶点也能够成为结点。顶点也能够成为结点。(2)结点前导为该结点结点前导为该结点父亲父亲(父结点父结点father)。(3)结点后继为它结点后继为它儿子儿子(son)。(4)假如树中有一条从结点假如树中有一条从结点v1到结点到结点v2路，则称路，则称v1是是v2祖先祖先(ancestor),v2是是v1后代后代(descendant)。(5)无儿子顶点叫做无儿子顶点叫做叶子叶子(leaf)。(6)非叶结点叫做非叶结点叫做中间结点中间结点(interior)。第56页/10/10571.3.3树树树层树层根处于树第根处于树第1层层(level)。假如结点假如结点v处于第处于第i层层(i1)，则，则v儿子处于第儿子处于第i+1层层。树最大层号叫做该树高度树最大层号叫做该树高度(height)。第57页/10/10581.3.3树树二元树二元树假如对于假如对于 vV，v最多只有最多只有2个儿子，则称个儿子，则称G=(V，E)为为二元树二元树(binarytree)。对一棵二元树，它第对一棵二元树，它第n层最多有层最多有2n-1个结点。一个结点。一棵棵n层二元树最多有个层二元树最多有个2n-1叶子。叶子。第58页/10/10591.4语言语言1.4.1什么是语言什么是语言 比如：比如：“学大一生是个我学大一生是个我”；“我是一我是一个大学生个大学生”。语言是一定群体用来进行交流工具。语言是一定群体用来进行交流工具。必须有着一系列生成规则、了解必须有着一系列生成规则、了解(语义语义)规规则则。第59页/10/10601.4.1什么是语言什么是语言第60页/10/10611.4.1什么是语言什么是语言斯大林：从强调语言作用出发，把语言定斯大林：从强调语言作用出发，把语言定义为义为“为广大人群所了解字和组合这些字为广大人群所了解字和组合这些字方法方法”。语言学家韦波斯特语言学家韦波斯特(Webster)：为相当大团：为相当大团体人所知道并使用字和组合这些字方法统体人所知道并使用字和组合这些字方法统一体。一体。要想对语言性质进行研究，用这些定义来要想对语言性质进行研究，用这些定义来建立语言数学模型是不够准确。必须有更建立语言数学模型是不够准确。必须有更形式化定义。形式化定义。第61页/10/10621.4.2形式语言与自动机理论产形式语言与自动机理论产生与作用生与作用语言学家乔姆斯基，毕业于宾西法尼亚大语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言角度研究语言。学，最初从产生语言角度研究语言。1956年，他将语言年，他将语言L定义为一个字母表定义为一个字母表中字母中字母组成一些串集合：组成一些串集合：L*。字母表上按照一定规则定义一个文法字母表上按照一定规则定义一个文法(grammar)，该文法所能产生全部句子组成，该文法所能产生全部句子组成集合就是该文法产生语言。集合就是该文法产生语言。1959年，乔姆斯基依据产生语言文法特征，年，乔姆斯基依据产生语言文法特征，将语言划分成将语言划分成3大类。大类。第62页/10/10631.4.2形式语言与自动机理论产形式语言与自动机理论产生与作用生与作用1951年到年到1956年，克林年，克林(Kleene)在研究神经在研究神经细胞中，建立了识别语言系统细胞中，建立了识别语言系统有穷状有穷状态自动机。态自动机。1959年，乔姆斯基发觉文法和自动机分别年，乔姆斯基发觉文法和自动机分别从生成和识别角度去表示语言，而且证实从生成和识别角度去表示语言，而且证实了文法与自动机等价性，这一结果被认为了文法与自动机等价性，这一结果被认为是将形式语言置于了数学光芒之下，使得是将形式语言置于了数学光芒之下，使得形式语言真正诞生了。形式语言真正诞生了。第63页/10/10641.4.2形式语言与自动机理论产形式语言与自动机理论产生与作用生与作用20世纪世纪50年代，巴科斯范式年代，巴科斯范式(BackusNourForm或或BackusNormalForm，BNF)实现实现了对高级语言了对高级语言ALGOL-60成功描述。这一成成功描述。这一成功，使得形式语言在功，使得形式语言在20世纪世纪60年代得到了年代得到了大力发展。尤其是上下文无关文法被作为大力发展。尤其是上下文无关文法被作为计算机程序设计语言文法最正确近似描述计算机程序设计语言文法最正确近似描述得到了较为深入研究。得到了较为深入研究。对应理论用于其它方面。对应理论用于其它方面。第64页/10/10651.4.2形式语言与自动机理论产形式语言与自动机理论产生与作用生与作用形式语言与自动机理论在计算机科学与技术形式语言与自动机理论在计算机科学与技术学科人才计算思维培养中占有极其主要地位。学科人才计算思维培养中占有极其主要地位。计算学科主题：计算学科主题：“什么能被有效地自动化什么能被有效地自动化”。第65页/10/10661.4.2形式语言与自动机理论产形式语言与自动机理论产生与作用生与作用计算机科学与技术学科人才专业能力组成计算机科学与技术学科人才专业能力组成“计算思维能力计算思维能力”抽象思维能力、逻辑思抽象思维能力、逻辑思维能力。维能力。算法设计与分析能力。算法设计与分析能力。程序设计与实现能力。程序设计与实现能力。计算机系统认知、分析、设计和应用能力。计算机系统认知、分析、设计和应用能力。第66页/10/10671.4.2形式语言与自动机理论产形式语言与自动机理论产生与作用生与作用第67页/10/10681.4.2形式语言与自动机理论产形式语言与自动机理论产生与作用生与作用考虑对象不一样，所需要思维方式和能力就不一样，考虑对象不一样，所需要思维方式和能力就不一样，经过这一系统教育，在不停升华过程中，逐步地培经过这一系统教育，在不停升华过程中，逐步地培养出了学生抽象思维能力和对逻辑思维方法掌握。养出了学生抽象思维能力和对逻辑思维方法掌握。创新意识建立和创新能力培养也在这个教育过程中创新意识建立和创新能力培养也在这个教育过程中循序渐进地进行着。循序渐进地进行着。内容用于后续课程和今后研究工作。内容用于后续课程和今后研究工作。是进行思维训练最正确知识载体。是进行思维训练最正确知识载体。是一个优异计算机科学工作者必修一门课程。是一个优异计算机科学工作者必修一门课程。第68页/10/10691.4.3基本概念基本概念对语言研究三个方面对语言研究三个方面表示表示(representation)无穷语言表示。无穷语言表示。有穷描述有穷描述(finitedescription)研究语言要么研究语言要么是有穷，要么是可数无穷，这里主要研究可数是有穷，要么是可数无穷，这里主要研究可数无穷语言有穷描述。无穷语言有穷描述。结构结构(structure)语言结构特征。语言结构特征。第69页/10/10701.4.3基本概念基本概念字母表字母表(alphabet)字母表字母表是一个非空有穷集合，字母表中元素称是一个非空有穷集合，字母表中元素称为该字母表一个为该字母表一个字母字母(letter)。又叫做。又叫做符号符号(symbol)、或者、或者字符字符(character)。非空性。非空性。有穷性。有穷性。比如：比如：a，b，c，da，b，c，z0,1第70页/10/10711.4.3基本概念基本概念字符两个特征字符两个特征整体性整体性(monolith)，也叫不可分性。，也叫不可分性。可识别性可识别性(distinguishable)，也叫可区分性。，也叫可区分性。例（续）例（续）a，a，b，baa，ab，bb，第71页/10/10721.4.3基本概念基本概念字母表乘积字母表乘积(product)12=ab|a1，b2比如：比如：0,10,1=00，01，10，000,1a，b，c，d=0a，0b，0c，0d，1a，1b，1c，1da，b，c，d0,1=a0，a1，b0，b1，c0，c1，d0，d1aa，ab，bb0,1=aa0，aa1，ab0，ab1，bb0，bb1第72页/10/10731.4.3基本概念基本概念字母表字母表n次次幂幂0=n=n-1是由是由中中0个字符组成。个字符组成。正闭包正闭包+=234克林闭包克林闭包*=0+=023第73页/10/10741.4.3基本概念基本概念比如：0,1+=0，1，00，01，11，000，001，010，011，100，0,1*=，0，1，00，01，11，000，001，010，011，100，a，b，c，d+=a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc，a，b，c，d*=，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc,第74页/10/10751.4.3基本概念基本概念结论：结论：*=x|x是是中中若若干干个个，包包含含0个个字字符符，连连接接而而成一个字符串成一个字符串。+=x|x是是中最少一个字符连接而成字符串中最少一个字符连接而成字符串。第75页/10/10761.4.3基本概念基本概念句子句子(sentence)是一个字母表，是一个字母表，x*，x叫做叫做上一个上一个句子。句子。句子相等。句子相等。两个句子被称为相等，假如它们对应位置上字符都对两个句子被称为相等，假如它们对应位置上字符都对应相等。应相等。别称别称字字(word)、(字符、符号字符、符号)行行(line)、(字符、符号字符、符号)串串(string)。第76页/10/10771.4.3基本概念基本概念出现出现(apperance)x，y*，a，句子，句子xay中中a叫做叫做a在该句子在该句子中一个中一个出现。出现。当当x=时，时，a这个出现为字符串这个出现为字符串xay首字符首字符假如假如a这个出现是字符串这个出现是字符串xay第第n个字符，则个字符，则y首首字符这个出现是字符串字符这个出现是字符串xay第第n+1个字符。个字符。当当y=时，时，a这个出现是字符串这个出现是字符串xay尾字符尾字符例：例：abaabb。第77页/10/10781.4.3基本概念基本概念句子长度句子长度(length)x*，句子，句子x中字符出现总个数叫做该中字符出现总个数叫做该句子长句子长度度，记作，记作|x|。长度为长度为0字符串叫字符串叫空句子空句子，记作，记作。比如：比如：|abaabb|=6|bbaa|=4|=0|bbabaabbbaa|=11第78页/10/10791.4.3基本概念基本概念注意事项注意事项是一个句子。是一个句子。这是因为。这是因为不是一个空集，它是含有不是一个空集，它是含有一个空句子一个空句子集合。集合。|=1，而，而|=0。第79页/10/10801.4.3基本概念基本概念并置并置(concatenation)x，y*，x，y并置并置是由串是由串x直接相接串直接相接串y所组所组成。记作成。记作xy。并置又叫做。并置又叫做连结。连结。串串xn次次幂幂x0=xn=xn-1x第80页/10/10811.4.3基本概念基本概念比如：对x=001，y=1101 x0=y0=x4=001001001001 y4=1101110111011101对x=0101，y=110110 x2=01010101 y2=110110110110 x4=0101010101010101 y4=110110110110110110110110 第81页/10/10821.4.3基本概念基本概念*上并置运算性质上并置运算性质结合律：结合律：(xy)z=x(yz)。左消去律：假如左消去律：假如xy=xz，则，则y=z。右消去律：假如右消去律：假如yx=zx，则，则y=z。惟惟一一分分解解性性：存存在在惟惟一一确确定定a1，a2，an，使得，使得x=a1a2an。单位元素：单位元素：x=x=x。第82页/10/10831.4.3基本概念基本概念前缀与后缀前缀与后缀 设x，y，z，w，v*，且x=yz，w=yv(1)y是x前缀(prefix)。(2)假如z，则y是x真前缀(properprefix)。(3)z是x后缀(suffix)；(4)假如y，则z是x真后缀(propersuffix)。(5)y是x和w公共前缀(commonPrefix)。第83页/10/10841.4.3基本概念基本概念公共公共前缀与后缀前缀与后缀(6)假如x和w任何公共前缀都是y前缀，则y是x和w最大公共前缀。(7)假如x=zy，w=vy，则y是x和w公共后缀(commonsuffix)。(8)假如x和w任何公共后缀都是y后缀，则y是x和w最大公共后缀。第84页/10/10851.4.3基本概念基本概念例例字母表=a，b上句子abaabb前缀、后缀、真前缀和真后缀以下：前缀：，a，ab，aba，abaa，a