形式语言与自动机理论--第一章课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,ppt课件,*,形式语言与自动机理论,Formal Languages and Automata Theory,蒋宗礼,1,ppt课件,形式语言与自动机理论Formal Languages an,课程目的和基本要求,课程性质,技术基础,基础知识要求,数学分析（或者高等数学），离散数学,主要特点,抽象和形式化,理论证明和构造性,基本模型的建立与性质,2,ppt课件,课程目的和基本要求课程性质2ppt课件,课程目的和基本要求,本专业人员4种基本的专业能力,计算思维能力,算法的设计与分析能力,程序设计和实现能力,计算机软硬件系统的认知、分析、设计与应用能力,计算思维能力,逻辑思维能力和抽象思维能力,构造模型对问题进行形式化描述,理解和处理形式模型,3,ppt课件,课程目的和基本要求本专业人员4种基本的专业能力3ppt课件,课程目的和基本要求,知识,掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。,能力,培养学生的形式化描述和抽象思维能力。,使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。,4,ppt课件,课程目的和基本要求 知识4ppt课件,主要内容,语言的,文法,描述。,RL,RG、 FA、RE、RL,的性质,。,CFL,CFG(CNF、GNF)、PDA、CFL,的性质。,TM,基本TM、构造技术、TM的修改。,CSL,CSG、LBA。,5,ppt课件,主要内容 语言的文法描述。5ppt课件,教材及主要参考书目,蒋宗礼，姜守旭,.,形式语言与自动机理论,.,北京：清华大学出版社，,2003,年,John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2,nd,Edition). Addison-Wesley Publishing Company, 2001,John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979,6,ppt课件,教材及主要参考书目蒋宗礼，姜守旭. 形式语言与自动机理论.,第1章,绪论,1.1 集合的基础知识,1.1.1 集合及其表示,集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做,集合,(set),，简称为集,(set),。,元素：集合的成员为该集合的,元素,(element)。,集合描述形式。,基数。,集合的分类。,7,ppt课件,第1章 绪论1.1 集合的基础知识 7ppt课件,1.1.2 集合之间的关系,子集,如果集合A中的每个元素都是集合B的元素，则称集合A是集合B的,子集,(subset)，集合B是集合A的,包集,(container)。记作A,B。也可记作B,A。A,B读作集合A包含在集合B中；B,A读作集合B包含集合A。,如果,A,B,，且,x,B,，但,x,A,，则称,A,是,B,的,真子集,(proper subset),，记作,A,B,8,ppt课件,1.1.2 集合之间的关系 子集 8ppt课件,1.1.2 集合之间的关系,集合相等,如果集合,A,，,B,含有的元素完全相同，则称集合,A,与集合,B,相等,(equivalence),，记作,A=B,。,对任意集合A、B、C：, A=B iff A,B且B,A。, 如果A,B，则|A|B|。, 如果A,B，则|A|B|。, 如果A是有穷集，且A,B，则|B|,|A|。,9,ppt课件,1.1.2 集合之间的关系集合相等 9ppt课件,1.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,ppt课件,1.1.2 集合之间的关系 如果AB，则对xA，有x,1.1.3 集合的运算,并,(union),A,与,B,的,并(union),是一个集合，该集合中的元素要么是,A,的元素，要么是,B,的元素，记作,A,B。,A,B=a|a,A,或者,a,B,A,1,A,2,A,n,=a|,i,，,1,i,n,，使得,a,A,i,A,1,A,2,A,n,=a|,i,，,i,N,使得,a,A,i,11,ppt课件,1.1.3 集合的运算 并(union) 11ppt课件,交,(intersection),集合,A,和,B,中都有的所有元素放在一起构成的集合为,A,与,B,的,交,，记作A,B。,A,B=a|a,A,且,a,B,“”为交运算符，,A,B,读作,A,交,B。,如果,A,B=,，则称,A,与,B,不相交。, AB= BA。, (AB)C=A(BC)。, AA=A。,12,ppt课件,交(intersection) 集合A和B中都有的所有元素放,交,(intersection), AB=A iff A,B。,A=,。, |AB|min|A|，|B|。, A(BC)=(AB)(AC)。, A(BC)=(AB)(AC)。, A(AB)=A。, A(AB)=A。,13,ppt课件,交(intersection) AB=A iff A,差(difference),属于,A,，但不属于,B,的所有元素组成的集合叫做,A,与,B,的,差，记作,A-B。,A-B=a|a,A,且,a,B,“,-,”为减,(,差,),运算符，,A-B,读作,A,减,B。, A-A=,。, A-,=A。, A-B B-A。, A-B=A iff AB=,。, A(B-C)=(AB)-(AC)。, |A-B|A|。,14,ppt课件,差(difference) 属于A，但不属于B的所有元素组成,对称差,(symmetric difference),属于,A,但不属于,B,，属于,B,但不属于,A,的所有元素组成的集合叫,A,与,B,的,对称差，记作,AB。,AB=a|aA且a,B或者a,A且aB,“”为对称差运算符。AB读作A对称减B。,AB=(AB)-(AB)=(A-B)(B-A)。,15,ppt课件,对称差(symmetric difference) 属于A但,笛卡儿积,(Cartesian product),A,与,B,的,笛卡儿积(Cartesian product),是一个集合，该集合是由所有这样的有序对,(a,，,b),组成的：其中,a,A,，,b,B ，记作A,B。,A,B=(a,，,b)|a,A& b,B 。,“,”为笛卡儿乘运算符。,A,B,读作,A,叉乘,B。,A,B,B,A。,(A,B),C,A,(B,C)。,A,A,A。,A,=,。,16,ppt课件,笛卡儿积(Cartesian product) A与B的笛卡,笛卡儿积,(Cartesian product),A,(B,C)=(A,B),(A,C)。,(B,C),A=(B,A),(A,C)。,A,(B,C)=(A,B),(A,C)。,(B,C),A=(B,A),(C,A)。,A,(B-C)=(A,B)-(A,C)。,(B-C),A=(B,A)-(C,A)。,当,A,、,B,为有穷集时，,|A,B|=|A|*|B|。,17,ppt课件,笛卡儿积(Cartesian product) A(B,幂集,(power set),A,幂集(power set),是一个集合，该集合是由,A,的所有子集组成的，记作,2,A,。,2,A,=B|B,A。,2,A,读作A的幂集。,18,ppt课件,幂集(power set) A幂集(power set)是一,幂集,(power set),2,A,。,2,A,。,2,A,。, 2,=,。, A2,A,。, 如果A是有穷集，则|2,A,|=2,|A|,。,2,AB,=2,A,2,B,。, 如果A,B，则2,A,2,B,。,19,ppt课件,幂集(power set) 2A。19ppt课,补集,(complementary set),A是论域U,上的一个集合，A,补集,是由U中的、不在A中的所有元素组成的集合，记作,20,ppt课件,补集(complementary set) A是论域U上的一,补集,(complementary set),如果A,B,，则,。,。,。,。,。,。,21,ppt课件,补集(complementary set)如果AB，则。,1.2 关系,二元关系,递归定义与归纳证明,关系的闭包,22,ppt课件,1.2 关系 二元关系 22ppt课件,1.2.1,二元关系,(binary relation),二元关系,任意的,R,A,B，,R是A到B的,二元关系。,(a，b) R，也可表示为：aRb。,A称为,定义域,(domain)，B称为,值域,(range)。,当A=B时，则称R是A上的二元关系。,二元关系的性质,自反,(reflexive)性、反自反(irreflexive)性、,对称(symmetric)性、反对称(asymmetric)性、传递,(transitive)性。,23,ppt课件,1.2.1 二元关系(binary relation) 二元,1.2.1,二元关系,(binary relation),三歧性,自反性、对称性、传递性。,等价关系,(equivalence relation),具有三歧性的二元关系称为,等价关系。,24,ppt课件,1.2.1 二元关系(binary relation)三歧性,1.2.1,二元关系,(binary relation),等价类,(equivalence class),S的满足如下要求的划分：S,1,、S,2,、S,3,、S,n,称为S关于R的等价划分，S,i,称为等价类。, S= S,1,S,2,S,3,S,n,；, 如果ij，则S,i,S,j,=,；, 对任意的i，S,i,中的任意两个元素a、b，aRb恒成立；, 对任意的i，j，ij，S,i,中的任意元素a和S,j,中的任意元素b，aRb恒不成立,25,ppt课件,1.2.1 二元关系(binary relation)等价类,1.2.1,二元关系,(binary relation),指数,(index),把R,将S分成的等价类的个数称为是R在S上的,指数,。如果R将S分成有穷多个等价类，则称R具有有穷指数；如果R将S分成无穷多个等价类，则称R具有无穷指数。,给定集合S上的一个等价关系R，R就确定了S的一个等价分类，当给定另一个不同的等价关系时，它会确定S的一个新的等价分类。,26,ppt课件,1.2.1 二元关系(binary relation)指数(,1.2.1,二元关系,(binary relation),关系的合成,(composition),设,R,1,A,B是A到B的关系、R,2,BC是B到C的关系，R,1,与R,2,的,合成,R,1,R,2,是A到C的关系：R,1,R,2,=(a，c)|,(a，b) R,1,且(b，c) R,2,。,27,ppt课件,1.2.1 二元关系(binary relation)关系的,1.2.1,二元关系,(binary relation), R,1,R,2,R,2,R,1。, (R,1,R,2,)R,3,=R,1,(R,2,R,3,)。 (结合率), (R,1,R,2,)R,3,=R,1,R,3,R,2,R,3。,(右分配率), R,3,(R,1,R,2,)=R,3,R,1,R,3,R,2。,(左分配率), (R,1,R,2,)R,3,R,1,R,3,R,2,R,3。, R,3,(R,1,R,2,),R,3,R,1,R,3,R,2。,28,ppt课件,1.2.1 二元关系(binary relation) R,1.2.1,二元关系,(binary relation),关系这一个概念用来反映对象集合元素之间的联系和性质,二元关系则是反映两个元素之间的关系，包括某个元素的某种属性。,对二元关系的性质，要强调全称量词是对什么样的范围而言的。,29,ppt课件,1.2.1 二元关系(binary relation)关系这,1.2.2,等价关系与等价类,（略）,1.2.3,关系的合成,（略）,30,ppt课件,1.2.2 等价关系与等价类（略）1.2.3 关系的合成,1.2.4 递归定义与归纳证明,递归定义,(recursive definition),又称为,归纳定义,(inductive definition)，它来定义一个集合。,集合的递归定义由三部分组成：,基础(basis)：用来定义该集合的最基本的元素。,归纳(induction)：指出用集合中的元素来构造集合的新元素的规则。,极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来。,31,ppt课件,1.2.4 递归定义与归纳证明递归定义(recursive,1.2.4 递归定义与归纳证明,归纳证明,与递归定义相对应。,归纳证明方法包括三大步：,基础(basis)：证明最基本元素具有相应性质。,归纳(induction)：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法得到的新元素也具有相应的性质。,根据归纳法原理，所有的元素具有相应的性质。,32,ppt课件,1.2.4 递归定义与归纳证明 归纳证明 32ppt课件,1.2.4 递归定义与归纳证明,定义 1-17,设R是S上的关系，我们递归地定义R,n,的幂：, R,0,=(a，a)|aS。, R,i,=R,i-1,R (i=1,2,3,4,5,)。,33,ppt课件,1.2.4 递归定义与归纳证明 定义 1-17 33ppt课,1.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,ppt课件,1.2.4 递归定义与归纳证明 例1-17 著名的斐波那契(,1.2.4 递归定义与归纳证明,例1-18,算术表达式, 基础：常数是算术表达式，变量是算术表达式；, 归纳：如果E,1,、E,2,是表达式，则 +E,1,、-E,1,、E,1,+E,2,、 E,1,-E,2,、E,1,*E,2,、E,1,/E,2,、E,1,*E,2,、Fun(E,1,)是算术表达式。其中Fun为函数名。, 只有满足(1)和(2)的才是算术表达式。,35,ppt课件,1.2.4 递归定义与归纳证明例1-18 算术表达式35pp,1.2.4 递归定义与归纳证明,例1-19,对有穷集合A，证明|2,A,|=2,|A|,。,证明：,设A为一个有穷集合, 施归纳于|A|：, 基础：当|A|=0时,|2,A,|=|,|=1。, 归纳：假设|A|=n时结论成立，这里n 0，往证当|A|=n+1时结论成立,2,A,=2,B,Ca|C2,B,2,B,Ca|C2,B,=,36,ppt课件,1.2.4 递归定义与归纳证明 例1-19 对有穷集合A，证,1.2.4 递归定义与归纳证明,|2,A,|=|2,B,Ca|C2,B,|,=|2,B,|+|Ca|C2,B,|,=|2,B,|+|2,B,|,=2*|2,B,|,=2*2,|B|,=2,|B|+1,=2,|A|, 由归纳法原理，结论对任意有穷集合成立。,37,ppt课件,1.2.4 递归定义与归纳证明,1.2.4 递归定义与归纳证明,例1-20,表达式的前缀形式是指将运算符写在前面，后跟相应的运算对象。如：,+E,1,的前缀形式为+E,1,，E,1,+E,2,的前缀形式为+E,1,E,2,，E,1,*E,2,的前缀形式为*E,1,E,2,， E,1,*E,2,的前缀形式为* E,1,，Fun(E,1,) 的前缀形式为FunE,1,。,证明例1-18所定义的表达式可以用这里定义的前缀形式表示。,38,ppt课件,1.2.4 递归定义与归纳证明例1-20 表达式的前缀形式,1.2.4 递归定义与归纳证明,递归定义给出的概念有利于归纳证明。在计算机科学与技术学科中，有许多问题可以用递归定义描述或者用归纳方法进行证明，而且在许多时候，这样做会带来许多方便。,主要是掌握,递归定义与归纳证明,的叙述格式。,39,ppt课件,1.2.4 递归定义与归纳证明 递归定义给出的概念有利于归纳,1.2.5 关系的闭包,闭包(closure),设P是关于关系的性质的集合，关系R的P,闭包(closure),是包含R并且具有P中所有性质的最小关系,。,正闭包(positive closure),(1)R,R,+,。,(2)如果(a，b)，(b，c)R,+,则(a，c)R,+,。,(3)除(1)、(2)外，R,+,不再含有其他任何元素,。,40,ppt课件,1.2.5 关系的闭包 闭包(closure) 40ppt课,1.2.5 关系的闭包,传递闭包(transitive closure),具有传递性的闭包。,R,+,具有传递性。,可以证明，对任意二元关系R，,R,+,= RR,2,R,3,R,4,而且当S为有穷集时：,R,+,= RR,2,R,3,R,|S|,41,ppt课件,1.2.5 关系的闭包传递闭包(transitive clo,1.2.5 关系的闭包,克林闭包(Kleene closure),R,*,(1),R,0,R,*,R,R,*,。,(2),如果(a，b)，(b，c)R,*,则(a，c)R,*,。,(3),除(1)、(2)外，R,*,不再含有其他任何元素。,自反传递闭包(reflexive and transitive closure),R,*,具有自反性、传递性,。,42,ppt课件,1.2.5 关系的闭包克林闭包(Kleene closure,1.2.5 关系的闭包,可以证明，对任意二元关系R，,R,*,= R,0,R,+,R,*,=R,0,RR,2,R,3,R,4,而且当S为有穷集时：,R,*,= R,0,RR,2,R,3,R,|S|,43,ppt课件,1.2.5 关系的闭包可以证明，对任意二元关系R，43ppt,1.2.5 关系的闭包,R,1,、R,2,是S上的两个二元关系,(1),+,=,。,(2)(R,1,+,),+,= R,1,+,。,(3) (R,1,*,),*,= R,1,*,。,(4) R,1,+,R,2,+,(R,1,R,2,),+,。,(5) R,1,*,R,2,*,(R,1,R,2,),*,。,44,ppt课件,1.2.5 关系的闭包R1、R2是S上的两个二元关系 44p,1.3 图,数学家欧拉(L.Euler)解决著名的哥尼斯堡七桥。,直观地讲，图是由一些点和一些连接两点的边组成。,含无方向的边的图为无向图，含带有方向的边的图为有向图。,45,ppt课件,1.3 图数学家欧拉(L.Euler)解决著名的哥尼斯堡七桥,1.3.1 无向图,无向图,(undirected graph),设V是一个非空的有穷集合，E,V,V，G=(V，E)称为,无向图,(undirected graph)。其中V中的元素称为,顶点,(vertex或node)，V称为顶点集，E中的元素称为,无向边,(undirected edge)，E为无向边集。,图表示,V中称为顶点v的元素用标记为v的小圈表示，E中的元素(v,1,，v,2,)用标记为v,1,，v,2,的顶点之间的连线表示。,46,ppt课件,1.3.1 无向图 无向图(undirected graph,1.3.1 无向图,路,(path),如果对于0ik-1，k1，均有(v,i,，v,i+1,)E，则称v,0,，v,1,，v,k,是G=(V，E)的一条长为k的,路。,回路或圈,(cycle),当路v,0,，v,1,，v,k,中v,0,=v,k,时，v,0,，v,1,，v,k,叫做一个,回路或圈,(cycle)。,47,ppt课件,1.3.1 无向图路(path)47ppt课件,1.3.1 无向图,顶点的度数,对于vV，|v|(v，w)E|称为无向图G=(V，E)的顶点v的度数，记作deg(v)。,对于任何一个图，图中所有顶点的度数之和为图中边的2倍。,48,ppt课件,1.3.1 无向图顶点的度数 48ppt课件,deg(v,1,)=3,deg(v,2,)=3,deg(v,3,)=4,deg(v,4,)=3,deg(v,5,)=3,deg(v,1,)+deg(v,2,)+deg(v,3,)+deg(v,4,)+deg(v,5,)=16,49,ppt课件,deg(v1)=349ppt课件,1.3.1 无向图,连通图,如果对于,v，wV，vw，v与w之间至少有一条路存在，则称G=(V，E)是,连通图,。,图G是连通的充要条件是G中存在一条包含图的所有顶点的路。,50,ppt课件,1.3.1 无向图连通图 50ppt课件,1.3.2 有向图,有向图,(directed graph),G=(V,，,E)。,V：,顶点(vertex或node),集。,(v,1,，,v,2,),E：,顶点,v,1,到顶点,v,2,的,有向边(directed edge),，或,弧(arc),，,v,1,称为,前导(predecessor),，,v,2,称为,后继(successor)。,有向路(directed path),如果对于,0,i,k-1,，,k,1,，均有,(v,i,，,v,i+1,),E,，则称,v,0,，,v,1,，,v,k,是,G,的一条长为,k,的,有向路。,51,ppt课件,1.3.2 有向图 有向图(directed graph),1.3.2 有向图,有向回路或有向圈(directed cycle),对于,0,i,k-1,，,k,1,，均有,(v,i,，,v,i+1,),E,， 且,v,0,=v,k,，则称,v,0,，,v,1,，,v,k,是,G,的一条长为,k,的,有向路为,一个,有向回路。,有向回路又叫有向圈。,有向图的图表示,图G的图表示是满足下列条件的“图”：其中V中称为顶点v的元素用标记为v的小圈表示，E中的元素(v,1,，v,2,)用从标记为v,1,的顶点到标记为v,2,的顶点的弧表示。,52,ppt课件,1.3.2 有向图有向回路或有向圈(directed cy,1.3.2 有向图,顶点的度数,入度(数),：,ideg(v)=|v|(w,，,v),E|。,出度(,数,)：,odeg(v)= |v|(v,，,w),E|。,对于任何一个有向图，图中所有顶点的入度之和与图中所有顶点的出度之和正好是图中边的个数,53,ppt课件,1.3.2 有向图顶点的度数 53ppt课件,两个不同的有向图,54,ppt课件,两个不同的有向图54ppt课件,1.3.3 树,满足如下条件的有向图,G=(V,，,E),称为一棵,(,有序、有向,),树,(tree),：,根,(root),v：,没有前导，且,v,到树中其他顶点均有一条有向路。,每个非根顶点有且仅有一个前导。,每个顶点的后继按其拓扑关系从左到右排序。,55,ppt课件,1.3.3 树 满足如下条件的有向图G=(V，E)称为一棵(,1.3.3 树,树的基本概念,(1),顶点也可以成为结点。,(2),结点的前导为该结点的,父亲,(,父结点,father)。,(3),结点的后继为它的,儿子,(son)。,(4),如果树中有一条从结点,v,1,到结点,v,2,的路，则称,v,1,是,v,2,的,祖先,(ancestor), v2,是,v1,的,后代,(descendant)。,(5),无儿子的顶点叫做,叶子,(leaf)。,(6),非叶结点叫做,中间结点,(interior)。,56,ppt课件,1.3.3 树 树的基本概念 56ppt课件,1.3.3 树,树的层,根处在树的第,1,层,(level)。,如果结点,v,处在第,i,层,(i,1),，则,v,的儿子处在第,i+1,层,。,树的最大层号叫做该树的高度,(height)。,57,ppt课件,1.3.3 树 树的层 57ppt课件,1.3.3 树,二元树,如果对于,v,V,，,v,最多只有,2,个儿子，则称,G=(V,，,E),为,二元树,(binary tree)。,对一棵二元树，它的第,n,层最多有,2,n-1,个结点。一棵,n,层二元树最多有个,2,n-1,叶子。,58,ppt课件,1.3.3 树 二元树 58ppt课件,1.4 语言,1.4.1 什么是语言,例如：“学大一生是个我”；“我是一个大学生”。,语言是一定的群体用来进行交流的工具。,必须有着一系列的生成规则、理解,(,语义,),规则,。,59,ppt课件,1.4 语言 1.4.1 什么是语言59ppt课件,1.4.1 什么是语言,60,ppt课件,1.4.1 什么是语言 60ppt课件,1.4.1 什么是语言,斯大林：从强调语言的作用出发，把语言定义为“为广大的人群所理解的字和组合这些字的方法”。,语言学家韦波斯特,(Webster),：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。,要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。必须有更形式化的定义。,61,ppt课件,1.4.1 什么是语言 斯大林：从强调语言的作用出发，把语言,1.4.2 形式语言与自动机理论的产生与作用,语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。,1956,年，他将语言,L,定义为一个字母表中的字母组成的一些串的集合：,L,*,。,字母表上按照一定的规则定义一个文法,(grammar),，该文法所能产生的所有句子组成的集合就是该文法产生的语言。,1959,年，乔姆斯基根据产生语言文法的特性，将语言划分成,3,大类。,62,ppt课件,1.4.2 形式语言与自动机理论的产生与作用 语言学家乔姆斯,1.4.2 形式语言与自动机理论的产生与作用,1951,年到,1956,年，克林,(Kleene),在研究神经细胞中，建立了识别语言的系统有穷状态自动机。,1959,年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被认为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。,63,ppt课件,1.4.2 形式语言与自动机理论的产生与作用 1951年到1,1.4.2 形式语言与自动机理论的产生与作用,20,世纪,50,年代，巴科斯范式,(Backus Nour Form,或,Backus Normal Form,，,BNF),实现了对高级语言,ALGOL-60,的成功描述。这一成功，使得形式语言在,20,世纪,60,年代得到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。,相应的理论用于其他方面。,64,ppt课件,1.4.2 形式语言与自动机理论的产生与作用20世纪50年代,1.4.2 形式语言与自动机理论的产生与作用,形式语言与自动机理论在计算机科学与技术学科的人才的计算思维的培养中占有极其重要的地位。,计算学科的主题：“什么能被有效地自动化”。,65,ppt课件,1.4.2 形式语言与自动机理论的产生与作用形式语言与自动机,1.4.2 形式语言与自动机理论的产生与作用,计算机科学与技术学科人才专业能力构成,“计算思维能力”抽象思维能力、逻辑思维能力。,算法设计与分析能力,。,程序设计与实现能力。,计算机系统的认知、分析、设计和应用能力。,66,ppt课件,1.4.2 形式语言与自动机理论的产生与作用计算机科学与技术,1.4.2 形式语言与自动机理论的产生与作用,67,ppt课件,1.4.2 形式语言与自动机理论的产生与作用67ppt课件,1.4.2 形式语言与自动机理论的产生与作用,考虑的对象的不同，所需要的思维方式和能力就不同，通过这一系统的教育，在不断升华的过程中，逐渐地培养出了学生的抽象思维能力和对逻辑思维方法的掌握。,创新意识的建立和创新能力的培养也在这个教育过程中循序渐进地进行着。,内容用于后续课程和今后的研究工作。,是进行思维训练的最佳知识载体。,是一个优秀的计算机科学工作者必修的一门课程。,68,ppt课件,1.4.2 形式语言与自动机理论的产生与作用考虑的对象的不同,1.4.3 基本概念,对语言研究的三个方面,表示(representation) 无穷语言的表示。,有穷描述(finite description) 研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。,结构(structure)语言的结构特征。,69,ppt课件,1.4.3 基本概念 对语言研究的三个方面 69ppt课件,1.4.3 基本概念,字母表,(alphabet),字母表,是一个非空有穷集合，字母表中的元素称为该字母表的一个,字母,(letter)。又叫做,符号,(symbol)、或者,字符,(character)。,非空性。,有穷性。,例如：,a，b，c，d, a，b，c，z,0,1,70,ppt课件,1.4.3 基本概念 字母表(alphabet) 70ppt,1.4.3 基本概念,字符的两个特性,整体性(monolith)，也叫不可分性。,可辨认性(distinguishable)，也叫可区分性。,例（续）,a，a，b，b,aa，ab，bb,，,71,ppt课件,1.4.3 基本概念 字符的两个特性 71ppt课件,1.4.3 基本概念,字母表的乘积(product),1,2,=ab|a,1,，b,2,例如：,0,10,1=00，01，10，00,0,1a，b，c，d=0a，0b，0c，0d，1a，1b，1c，1d,a，b，c，d0,1=a0，a1，b0，b1，c0，c1，d0，d1,aa，ab，bb0,1= aa0，aa1，ab0，ab1，bb0，bb1,72,ppt课件,1.4.3 基本概念 字母表的乘积(product) 72p,1.4.3 基本概念,字母表的n次,幂,0,=,n,=,n-1,是由中的0个字符组成的。,的,正闭包,+,=,2,3,4,的,克林闭包,*,=,0,+,=,0,2,3,73,ppt课件,1.4.3 基本概念 字母表的n次幂 73ppt课件,1.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,ppt课件,1.4.3 基本概念例如： 74ppt课件,1.4.3 基本概念,结论：,*,=x|x是中的若干个，包括0个字符，连接而成的一个字符串。,+,=x|x是中的至少一个字符连接而成的字符串。,75,ppt课件,1.4.3 基本概念结论：75ppt课件,1.4.3 基本概念,句子(sentence),是一个字母表，,x,*,，x叫做上的一个,句子。,句子相等。,两个句子被称为相等的，如果它们对应位置上的字符都对应相等。,别称,字(word)、(字符、符号)行(line)、(字符、符号)串(string)。,76,ppt课件,1.4.3 基本概念句子(sentence) 76ppt课件,1.4.3 基本概念,出现,(apperance),x，y,*,，a，句子xay中的a叫做a在该句子中的一个,出现。,当x=时，a的这个出现为字符串xay的首字符,如果a的这个出现是字符串xay的第n个字符，则y的首字符的这个出现是字符串xay的第n+1个字符。,当y=时，a的这个出现是字符串xay的尾字符,例：abaabb。,77,ppt课件,1.4.3 基本概念出现(apperance)77ppt课件,1.4.3 基本概念,句子的长度,(length),x,*,，句子,x,中字符出现的总个数叫做该,句子的长度,，记作,|x|。,长度为,0,的字符串叫,空句子,，记作。,例如：,|abaabb|=6,|bbaa|=4,|,|=0,|bbabaabbbaa|=11,78,ppt课件,1.4.3 基本概念句子的长度(length) 78ppt课,1.4.3 基本概念,注意事项,是一个句子。,。这是因为不是一个空集，它是含有一个空句子的集合。|=1，而|,|=0。,79,ppt课件,1.4.3 基本概念注意事项79ppt课件,1.4.3 基本概念,并置(concatenation),x，y,*,，x，y的,并置,是由串x直接相接串y所组成的。记作xy。并置又叫做,连结。,串x的n次,幂,x,0,=,x,n,=x,n-1,x,80,ppt课件,1.4.3 基本概念并置(concatenation) 80,1.4.3 基本概念,例,如：,对x=001，y=1101,x,0,=y,0,=,x,4,=001001001001,y,4,=1101110111011101,对x=0101，y=110110,x,2,=01010101,y,2,=110110110110,x,4,=0101010101010101,y,4,=110110110110110110110110,81,ppt课件,1.4.3 基本概念例如：81ppt课件,1.4.3 基本概念,*,上的并置运算性质, 结合律：(xy)z=x(yz)。, 左消去律：如果xy=xz，则y=z。, 右消去律：如果yx=zx，则y=z。, 惟一分解性：存在惟一确定的a,1,，a,2,，a,n,，使得x= a,1,a,2,a,n。, 单位元素：x=x=x。,82,ppt课件,1.4.3 基本概念*上的并置运算性质82ppt课件,1.4.3 基本概念,前缀与后缀,设x，y，z，w，v*，且x=yz，w=yv,(1)y是x的前缀(prefix)。,(2)如果z，则y是x的真前缀(proper prefix)。,(3) z是x的后缀(suffix)；,(4) 如果y，则z是x的真后缀(proper suffix)。,(5) y是x和w的公共前缀(common Prefix)。,83,ppt课件,1.4.3 基本概念前缀与后缀 83ppt课件,1.4.3 基本概念,公共,前缀与后缀,(6)如果x和w的任何公共前缀都是y的前缀，则y是x和w的最大公共前缀。,(7)如果x=zy，w=vy，则y是x和w的公共后缀(common suffix )。,(8)如果x和w的任何公共后缀都是y的后缀，则y是x和w的最大公共后缀。,84,ppt课件,1.4.3 基本概念公共前缀与后缀84ppt课件,1.4.3 基本概念,例,字母表=a，b上的句子abaabb的前缀、后缀、真前缀和真后缀如下：,前缀：，a，ab，aba，abaa，abaab，abaabb,真前缀：，a，ab，aba，abaa，abaab,后缀：，b，bb，abb，aabb，baabb，abaabb,真后缀：，b，bb，abb，aabb，baabb,85,ppt课件,1.4.3 基本概念例 85ppt课件,1.4.3 基本概念,结论, x的任意前缀y有惟一的一个后缀z与之对应，使得x=yz；反之亦然。, x的任意真前缀y有惟一的一个真后缀z与之对应，使得x=yz；反之亦然。, |w|w是x的后缀|=|w|w是x的前缀|。, |w|w是x的真后缀|=|w|w是x的真前缀|。, w|w是x的前缀=w|w是x的真前缀x，,|w|w是x的前缀|=|w|w是x的真前缀|+1。,86,ppt课件,1.4.3 基本概念结论86ppt课件,1.4.3 基本概念,结论, w|w是x的后缀=w|w是x的真后缀x，,|w|w是x的后缀|=|w|w是x的真后缀|+1。, 对于任意字符串w，w是自身的前缀，但不是自身的真前缀；w是自身的后缀，但不是自身的真后缀。, 对于任意字符串w，是w的前缀，且是w的真前缀；是w的后缀，且是w的真后缀,87,ppt课件,1.4.3 基本概念结论87ppt课件,1.4.3 基本概念,约定, 用小写字母表中较为靠前的字母a，b，c，表示字母表中的字母。, 用小写字母表中较为靠后的字母x，y，z，表示字母表上的句子。, 用x,T,表示x的倒序。例如，如果x=abc，则x,T,=cba。,88,ppt课件,1.4.3 基本概念约定 88ppt课件,1.4.3 基本概念,子串(substring),w，x，y，z,*,，且w=xyz，则称y是w的,子串。,公共子串(common substring),t，u，v，w，x，y，z,*,，且t=uyv，w=xyz，则称y是t和w的,公共子串(common substring),。如果y,1,，y,2,，y,n,是t和w的公共子串，且max|y,1,|，|y,2,|，|y,n,|=|y,j,|，则称y,j,是t和w的,最大公共子串。,两个串的最大公共子串并不一定是惟一的。,89,ppt课件,1.4.3 基本概念子串(substring) 89ppt课,1.4.3 基本概念,语言(language),L,*,，L称为字母表上的一个,语言(language),，,xL，x叫做L的一个句子。,例：0，1上的不同语言,00，11 ，0，1,0，1，00，11 ， 0，1，00，11，01，10,00，11,*,，01，10,*,，00，01，10，11,*,，,00，1,*,1，0，1,*,1110，1,*,90,ppt课件,1.4.3 基本概念语言(language) 90ppt课件,1.4.3 基本概念,语言的,乘积(product),L,1,1,*,，L,2,2,*,，语言L,1,与L,2,的,乘积,是一个语言，该语言定义为：,L,1,L,2,=xy| xL,1,，yL,2,是字母表,1,2,上的语言。,91,ppt课件,1.4.3 基本概念语言的乘积(product)91ppt课,1.4.3 基本概念,例, L,1,=0，1。, L,2,=00，01，10，11。, L,3,=0，1，00，01，10，11，000，=,+,。,L,4,=，0，1，00，01，10，11，000，=,*,。, L,5,=0,n,|n1。, L,6,=0,n,1,n,|n1。, L,7,=1,n,|n1。, L,8,=0,n,1,m,|n，m1。, L,9,=0,n,1,n,0,n,|n1。, L,10,=0,n,1,m,0,k,|n，m，k1。, L,11,=x|x,+,且x中0和1的个数相同。,92,ppt课件,1.4.3 基本概念例92ppt课件,1.4.3 基本概念,上述几个语言的部分特点及相互关系,上述所有语言都是,L,4,的子集,(,子语言,),；,L,1,，,L,2,是有穷语言；其他为无穷语言；其中,L,1,是上的所有长度为,1,的句子组成的语言，,L,2,是上的所有长度为,2,的句子组成的语言；,L,3,，,L,4,分别是的正闭包和克林闭包；,L,5,L,7,L,6,，但,L,5,L,7,= L,8,；同样,L,9,L,10,，但是我们有：,L,6,L,5,L,7,，,L,9,L,10。,93,ppt课件,1.4.3 基本概念上述几个语言的部分特点及相互关系 93p,1.4.3 基本概念,L,6,=0,n,1,n,|n,1,中的句子中的,0,和,1,的个数是相同的，并且所有的,0,在所有的,1,的前面，,L,11,=x|x,+,且,x,中,0,和,1,的个数相同,中的句子中虽然保持着,0,的个数和,1,的个数相等，但它并没要求所有的,0,在所有的,1,的前面。例如，,0101,，,1100,L,11,，但是,0101,L,6,，,1100,L,6,。而对,x,L,6,，有,x,L,11,。所以，,L,6,L,11。,94,ppt课件,1.4.3 基本概念L6=0n1n|n1中的句子中的0,1.4.3 基本概念,L,1,L,12,，,L,2,L,12,L,5,L,12,，,L,6,L,12,L,7,L,12,，,L,8,L,12,L,9,L,12,，,L,10,L,12,L,1,L,10,，,L,2,L,10,L,5,L,10,，,L,6,L,10,L,7,L,10,，,L,8,L,10,L,9,L,10,，,L,10,L,12,95,ppt课件,1.4.3 基本概念L1L12，L2L1295ppt课件,1.4.3 基本概念,例,x|x=x,T,，,x,。,xx,T,|x,+,。,xx,T,|x,*,。,xwx,T,|x,，,w,+,。,xx,T,w|x,，,w,+,。,96,ppt课件,1.4.3 基本概念例 96ppt课件,1.4.3 基本概念,幂,L,*,，L的n次,幂,是一个语言，该语言定义为,当,n=0,是，,L,n,=,。,当,n,1,时，,L,n,= L,n-1,L,。,正闭包,L,+,=L,L,2,L,3,L,4,克林闭包,L,*,= L,0,L,L,2,L,3,L,4,97,ppt课件,1.4.3 基本概念幂97ppt课件,1.5 小结,本章简单叙述了一些基础知识，一方面，希望读者通过对本章的阅读，熟悉集合、关系、图、形式语言等相关的一些基本知识点，为以后各章学习作适当的准备。另一方面，也使读者熟悉本书中一些符号的意义。,98,ppt课件,1.5 小结 本章简单叙述了一些基础知识，一方面,1.5 小结,(1),集合：集合的表示、集合之间的关系、集合的基本运算。,(2),关系：主要介绍了二元关系相关的内容。包括等价关系、等价分类、关系合成、关系闭包。,(3),递归定义与归纳证明。,99,ppt课件,1.5 小结 (1) 集合：集合的表示、集合之间的关系、集,1.5 小结,(4),图：无向图、有向图、树的基本概念。,(5),语言与形式语言：自然语言的描述，形式语言和自动机理论的出现，形式语言和自动机理论对计算机科学与技术学科人才能力培养的作用,(6),基本概念：字母表、字母、句子、字母表上的语言、语言的基本运算,100,ppt课件,1.5 小结(4) 图：无向图、有向图、树的基本概念。10,