2009-7-261形式语言与自动机理论FORMALLANGUAGESANDAUTOMATATHEORY蒋宗礼2009-7-262课程目的和基本要求课程性质–技术基础基础知识要求–数学分析（或者高等数学），离散数学主要特点–抽象和形式化–理论证明和构造性–基本模型的建立与性质2009-7-263课程目的和基本要求本专业人员4种基本的专业能力–计算思维能力–算法的设计与分析能力–程序设计和实现能力–计算机软硬件系统的认知、分析、设计与应用能力计算思维能力–逻辑思维能力和抽象思维能力–构造模型对问题进行形式化描述–理解和处理形式模型2009-7-264课程目的和基本要求知识–掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。能力–培养学生的形式化描述和抽象思维能力。–使学生了解和初步掌握,问题、形式化描述、自动化（计算机化）,这一最典型的计算机问题求解思路。2009-7-265主要内容语言的文法描述。RL–RG,FA,RE,RL的性质。CFL–CFG(CNF,GNF),PDA,CFL的性质。TM–基本TM,构造技术,TM的修改。CSL–CSG,LBA。2009-7-266教材及主要参考书目1.蒋宗礼,姜守旭,形式语言与自动机理论,北京：清华大学出版社,2003年2,JOHNEHOPCROFT,RAJEEVMOTWANI,JEFFREYDULLMAN,INTRODUCTIONTOAUTOMATATHEORY,LANGUAGES,ANDCOMPUTATION(2NDEDITION).ADDISON-WESLEYPUBLISHINGCOMPANY,20013,JOHNEHOPCROFT,JEFFREYDULLMAN,INTRODUCTIONTOAUTOMATATHEORY,LANGUAGES,ANDCOMPUTATION,ADDISON-WESLEYPUBLISHINGCOMPANY,19792009-7-267第1章绪论1.1集合的基础知识1.1.1集合及其表示–集合：一定范围内的,确定的,并且彼此可以区分的对象汇集在一起形成的整体叫做集合(SET)，简称为集(SET)。–元素：集合的成员为该集合的元素(ELEMENT)。–集合描述形式。–基数。–集合的分类。2009-7-2681.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的真子集(PROPERSUBSET),记作A?B2009-7-2691.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|。2009-7-26101.1.2集合之间的关系⑸如果A?B,则对?X∈A,有X∈B。⑹如果A?B,则对?X∈A,有X∈B并且X∈B,但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|。2009-7-26111.1.3集合的运算并(UNION)A与B的并(UNION)是一个集合,该集合中的元素要么是A的元素,要么是B的元素,记作A∪B。A∪B={A|A∈A或者A∈B}A1∪A2∪…∪AN={A|?I,1?I?N,使得A∈AI}A1∪A2∪…∪AN∪…={A|?I,I∈N,使得A∈AI}1IIA},|{AASAAASA2009-7-2612交(INTERSECTION)集合A和B中都有的所有元素放在一起构成的集合为A与B的交,记作A∩B。A∩B={A|A∈A且A∈B},∩,为交运算符,A∩B读作A交B。如果A∩B=Φ,则称A与B不相交。⑴A∩B=B∩A。⑵(A∩B)∩C=A∩(B∩C)。⑶A∩A=A。2009-7-2613交(INTERSECTION)⑷A∩B=AIFFA?B。⑸Φ∩A=Φ。⑹|A∩B|≤MIN{|A|,|B|}。⑺A∩(B∪C)=(A∩B)∪(A∩C)。⑻A∪(B∩C)=(A∪B)∩(A∪C)。⑼A∩(A∪B)=A。⑽A∪(A∩B)=A。2009-7-2614差(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=AIFFA∩B=Φ。⑸A∩(B-C)=(A∩B)-(A∩C)。⑹|A-B|≤|A|。2009-7-2615对称差(SYMMETRICDIFFERENCE)属于A但不属于B,属于B但不属于A的所有元素组成的集合叫A与B的对称差,记作A⊕B。A⊕B={A|A∈A且A?B或者A?A且A∈B},⊕,为对称差运算符。A⊕B读作A对称减B。A⊕B=(A∪B)-(A∩B)=(A-B)∪(B-A)。2009-7-2616笛卡儿积(CARTESIANPRODUCT)A与B的笛卡儿积(CARTESIANPRODUCT)是一个集合,该集合是由所有这样的有序对(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×Φ=Φ。2009-7-2617笛卡儿积(CARTESIANPRODUCT)⑸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|。2009-7-2618幂集(POWERSET)A幂集(POWERSET)是一个集合，该集合是由A的所有子集组成的，记作2A。2A={B|B?A}。2A读作A的幂集。2009-7-2619幂集(POWERSET)⑴Φ∈2A。⑵Φ?2A。⑶Φ?2A。⑷2Φ={Φ}。⑸A∈2A。⑹如果A是有穷集,则|2A|=2|A|。⑺2A∩B=2A∩2B。⑻如果A?B，则2A?2B。2009-7-2620补集(COMPLEMENTARYSET)A是论域U上的一个集合,A补集是由U中的、不在A中的所有元素组成的集合，记作AUAUU2009-7-2621补集(COMPLEMENTARYSET)AA?BAUBAAB&BABABABAAB?UAA如果A?B，则。。。。。。2009-7-26221.2关系二元关系递归定义与归纳证明关系的闭包2009-7-26231.2.1二元关系(BINARYRELATION)二元关系–任意的R?A×B,R是A到B的二元关系。–(A,B)∈R，也可表示为,ARB。–A称为定义域(DOMAIN),B称为值域(RANGE)。–当A=B时，则称R是A上的二元关系。二元关系的性质–自反(REFLEXIVE)性、反自反(IRREFLEXIVE)性、对称(SYMMETRIC)性、反对称(ASYMMETRIC)性、传递(TRANSITIVE)性。2009-7-26241.2.1二元关系(BINARYRELATION)三歧性–自反性、对称性、传递性。等价关系(EQUIVALENCERELATION)–具有三歧性的二元关系称为等价关系。2009-7-26251.2.1二元关系(BINARYRELATION)等价类(EQUIVALENCECLASS)S的满足如下要求的划分,S1,S2,S3,…,SN…称为S关于R的等价划分,SI称为等价类。⑴S=S1∪S2∪S3∪…∪SN∪…；⑵如果I≠J,则SI∩SJ=Φ；⑶对任意的I,SI中的任意两个元素A,B,ARB恒成立；⑷对任意的I,J,I≠J,SI中的任意元素A和SJ中的任意元素B,ARB恒不成立2009-7-26261.2.1二元关系(BINARYRELATION)指数(INDEX)–把R将S分成的等价类的个数称为是R在S上的指数。如果R将S分成有穷多个等价类，则称R具有有穷指数；如果R将S分成无穷多个等价类，则称R具有无穷指数。–给定集合S上的一个等价关系R,R就确定了S的一个等价分类，当给定另一个不同的等价关系时，它会确定S的一个新的等价分类。2009-7-26271.2.1二元关系(BINARYRELATION)关系的合成(COMPOSITION)设R1?A×B是A到B的关系,R2?B×C是B到C的关系,R1与R2的合成R1R2是A到C的关系：R1R2={(A,C)|?(A,B)∈R1且(B,C)∈R2。2009-7-26281.2.1二元关系(BINARYRELATION)⑴R1R2≠R2R1。⑵(R1R2)R3=R1(R2R3)。(结合率)⑶(R1∪R2)R3=R1R3∪R2R3。(右分配率)⑷R3(R1∪R2)=R3R1∪R3R2。(左分配率)⑸(R1∩R2)R3?R1R3∩R2R3。⑹R3(R1∩R2)?R3R1∩R3R2。2009-7-26291.2.1二元关系(BINARYRELATION)1,关系这一个概念用来反映对象——集合元素之间的联系和性质2,二元关系则是反映两个元素之间的关系,包括某个元素的某种属性。3,对二元关系的性质,要强调全称量词是对什么样的范围而言的。2009-7-26301.2.2等价关系与等价类（略）1.2.3关系的合成（略）2009-7-26311.2.4递归定义与归纳证明递归定义(RECURSIVEDEFINITION)–又称为归纳定义(INDUCTIVEDEFINITION)，它来定义一个集合。–集合的递归定义由三部分组成：基础(BASIS)：用来定义该集合的最基本的元素。归纳(INDUCTION)：指出用集合中的元素来构造集合的新元素的规则。极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来。2009-7-26321.2.4递归定义与归纳证明归纳证明–与递归定义相对应。–归纳证明方法包括三大步：基础(BASIS)：证明最基本元素具有相应性质。归纳(INDUCTION)：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法得到的新元素也具有相应的性质。根据归纳法原理，所有的元素具有相应的性质。2009-7-26331.2.4递归定义与归纳证明定义1-17设R是S上的关系,我们递归地定义RN的幂：⑴R0={(A,A)|A∈S}。⑵RI=RI-1R(I=1,2,3,4,5,…)。2009-7-26341.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,…2009-7-26351.2.4递归定义与归纳证明例1-18算术表达式⑴基础：常数是算术表达式,变量是算术表达式；⑵归纳：如果E1,E2是表达式,则+E1,-E1、E1+E2,E1-E2,E1*E2,E1/E2,E1**E2、FUN(E1)是算术表达式。其中FUN为函数名。⑶只有满足(1)和(2)的才是算术表达式。2009-7-26361.2.4递归定义与归纳证明例1-19对有穷集合A,证明|2A|=2|A|。证明：设A为一个有穷集合,施归纳于|A|：⑴基础：当|A|=0时,|2A|=|{Φ}|=1。⑵归纳：假设|A|=N时结论成立，这里N≥0，往证当|A|=N+1时结论成立2A=2B∪{C∪{A}|C∈2B}2B∩{C∪{A}|C∈2B}=Φ2009-7-26371.2.4递归定义与归纳证明|2A|=|2B∪{C∪{A}|C∈2B}|=|2B|+|{C∪{A}|C∈2B}|=|2B|+|2B|=2*|2B|=2*2|B|=2|B|+1=2|A|⑶由归纳法原理,结论对任意有穷集合成立。2009-7-26381.2.4递归定义与归纳证明例1-20表达式的前缀形式是指将运算符写在前面，后跟相应的运算对象。如,+E1的前缀形式为+E1,E1+E2的前缀形式为+E1E2,E1*E2的前缀形式为*E1E2,E1**E2的前缀形式为**E1,FUN(E1)的前缀形式为FUNE1。证明例1-18所定义的表达式可以用这里定义的前缀形式表示。2009-7-26391.2.4递归定义与归纳证明递归定义给出的概念有利于归纳证明。在计算机科学与技术学科中，有许多问题可以用递归定义描述或者用归纳方法进行证明，而且在许多时候，这样做会带来许多方便。主要是掌握递归定义与归纳证明的叙述格式。2009-7-26401.2.5关系的闭包闭包(CLOSURE)–设P是关于关系的性质的集合，关系R的P闭包(CLOSURE)是包含R并且具有P中所有性质的最小关系。正闭包(POSITIVECLOSURE)(1)R?R+。(2)如果(A,B),(B,C)∈R+则(A,C)∈R+。(3)除(1),(2)外,R+不再含有其他任何元素。2009-7-26411.2.5关系的闭包传递闭包(TRANSITIVECLOSURE)–具有传递性的闭包。–R+具有传递性。可以证明,对任意二元关系R，R+=R∪R2∪R3∪R4∪…而且当S为有穷集时：R+=R∪R2∪R3∪…∪R|S|2009-7-26421.2.5关系的闭包克林闭包(KLEENECLOSURE)R*(1)R0?R*,R?R*。(2)如果(A,B),(B,C)∈R*则(A,C)∈R*。(3)除(1),(2)外,R*不再含有其他任何元素。自反传递闭包(REFLEXIVEANDTRANSITIVECLOSURE)R*具有自反性、传递性。2009-7-26431.2.5关系的闭包可以证明,对任意二元关系R，R*=R0∪R+R*=R0∪R∪R2∪R3∪R4∪…而且当S为有穷集时：R*=R0∪R∪R2∪R3∪…∪R|S|2009-7-26441.2.5关系的闭包R1,R2是S上的两个二元关系(1)Φ+=Φ。(2)(R1+)+=R1+。(3)(R1*)*=R1*。(4)R1+∪R2+?(R1∪R2)+。(5)R1*∪R2*?(R1∪R2)*。2009-7-26451.3图数学家欧拉(L.EULER)解决著名的哥尼斯堡七桥。直观地讲，图是由一些点和一些连接两点的边组成。含无方向的边的图为无向图，含带有方向的边的图为有向图。2009-7-26461.3.1无向图无向图(UNDIRECTEDGRAPH)–设V是一个非空的有穷集合,E?V×V,G=(V，E)称为无向图(UNDIRECTEDGRAPH)。其中V中的元素称为顶点(VERTEX或NODE),V称为顶点集，E中的元素称为无向边(UNDIRECTEDEDGE),E为无向边集。图表示–V中称为顶点V的元素用标记为V的小圈表示,E中的元素(V1,V2)用标记为V1,V2的顶点之间的连线表示。2009-7-26471.3.1无向图路(PATH)–如果对于0≤I≤K-1,K≥1，均有(VI,VI+1)∈E，则称V0,V1,…,VK是G=(V,E)的一条长为K的路。回路或圈(CYCLE)–当路V0,V1,…,VK中V0=VK时,V0,V1,…,VK叫做一个回路或圈(CYCLE)。2009-7-26481.3.1无向图顶点的度数–对于V∈V,|{V|(V,W)∈E}|称为无向图G=(V，E)的顶点V的度数,记作DEG(V)。–对于任何一个图，图中所有顶点的度数之和为图中边的2倍。VVEV||*2)DEG(2009-7-2649DEG(V1)=3DEG(V2)=3DEG(V3)=4DEG(V4)=3DEG(V5)=3DEG(V1)+DEG(V2)+DEG(V3)+DEG(V4)+DEG(V5)=162009-7-26501.3.1无向图连通图–如果对于?V,W∈V,V≠W,V与W之间至少有一条路存在，则称G=(V,E)是连通图。–图G是连通的充要条件是G中存在一条包含图的所有顶点的路。2009-7-26511.3.2有向图有向图(DIRECTEDGRAPH)–G=(V,E)。–V,顶点(VERTEX或NODE)集。–(V1,V2)∈E,顶点V1到顶点V2的有向边(DIRECTEDEDGE)，或弧(ARC),V1称为前导(PREDECESSOR),V2称为后继(SUCCESSOR)。有向路(DIRECTEDPATH)–如果对于0?I?K-1,K?1，均有(VI,VI+1)∈E，则称V0,V1,…,VK是G的一条长为K的有向路。2009-7-26521.3.2有向图有向回路或有向圈(DIRECTEDCYCLE)–对于0?I?K-1,K?1，均有(VI,VI+1)∈E,且V0=VK，则称V0,V1,…,VK是G的一条长为K的有向路为一个有向回路。–有向回路又叫有向圈。有向图的图表示–图G的图表示是满足下列条件的,图,,其中V中称为顶点V的元素用标记为V的小圈表示,E中的元素(V1,V2)用从标记为V1的顶点到标记为V2的顶点的弧表示。2009-7-26531.3.2有向图顶点的度数–入度(数),IDEG(V)=|{V|(W,V)∈E}|。–出度(数),ODEG(V)=|{V|(V,W)∈E}|。对于任何一个有向图，图中所有顶点的入度之和与图中所有顶点的出度之和正好是图中边的个数VVVVEVOVI||)DEG()DEG(2009-7-2654两个不同的有向图2009-7-26551.3.3树满足如下条件的有向图G=(V,E)称为一棵(有序、有向)树(TREE)：–根(ROOT)V,没有前导，且V到树中其他顶点均有一条有向路。–每个非根顶点有且仅有一个前导。–每个顶点的后继按其拓扑关系从左到右排序。2009-7-26561.3.3树树的基本概念(1)顶点也可以成为结点。(2)结点的前导为该结点的父亲(父结点FATHER)。(3)结点的后继为它的儿子(SON)。(4)如果树中有一条从结点V1到结点V2的路，则称V1是V2的祖先(ANCESTOR),V2是V1的后代(DESCENDANT)。(5)无儿子的顶点叫做叶子(LEAF)。(6)非叶结点叫做中间结点(INTERIOR)。2009-7-26571.3.3树树的层–根处在树的第1层(LEVEL)。–如果结点V处在第I层(I?1)，则V的儿子处在第I+1层。–树的最大层号叫做该树的高度(HEIGHT)。2009-7-26581.3.3树二元树–如果对于?V∈V,V最多只有2个儿子，则称G=(V,E)为二元树(BINARYTREE)。–对一棵二元树，它的第N层最多有2N-1个结点。一棵N层二元树最多有个2N-1叶子。2009-7-26591.4语言1.4.1什么是语言例如：,学大一生是个我,；,我是一个大学生,。语言是一定的群体用来进行交流的工具。必须有着一系列的生成规则、理解(语义)规则。2009-7-26601.4.1什么是语言2009-7-26611.4.1什么是语言斯大林：从强调语言的作用出发，把语言定义为,为广大的人群所理解的字和组合这些字的方法,。语言学家韦波斯特(WEBSTER),为相当大的团体的人所懂得并使用的字和组合这些字的方法的统一体。要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。必须有更形式化的定义。2009-7-26621.4.2形式语言与自动机理论的产生与作用语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。1956年，他将语言L定义为一个字母表∑中的字母组成的一些串的集合,L?∑*。字母表上按照一定的规则定义一个文法(GRAMMAR)，该文法所能产生的所有句子组成的集合就是该文法产生的语言。1959年，乔姆斯基根据产生语言文法的特性，将语言划分成3大类。2009-7-26631.4.2形式语言与自动机理论的产生与作用1951年到1956年，克林(KLEENE)在研究神经细胞中，建立了识别语言的系统——有穷状态自动机。1959年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被认为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。2009-7-26641.4.2形式语言与自动机理论的产生与作用20世纪50年代，巴科斯范式(BACKUSNOURFORM或BACKUSNORMALFORM,BNF)实现了对高级语言ALGOL-60的成功描述。这一成功，使得形式语言在20世纪60年代得到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。相应的理论用于其他方面。2009-7-26651.4.2形式语言与自动机理论的产生与作用形式语言与自动机理论在计算机科学与技术学科的人才的计算思维的培养中占有极其重要的地位。计算学科的主题：,什么能被有效地自动化,。2009-7-26661.4.2形式语言与自动机理论的产生与作用计算机科学与技术学科人才专业能力构成–,计算思维能力,——抽象思维能力、逻辑思维能力。–算法设计与分析能力。–程序设计与实现能力。–计算机系统的认知、分析、设计和应用能力。2009-7-26671.4.2形式语言与自动机理论的产生与作用2009-7-26681.4.2形式语言与自动机理论的产生与作用考虑的对象的不同，所需要的思维方式和能力就不同，通过这一系统的教育，在不断升华的过程中，逐渐地培养出了学生的抽象思维能力和对逻辑思维方法的掌握。创新意识的建立和创新能力的培养也在这个教育过程中循序渐进地进行着。内容用于后续课程和今后的研究工作。是进行思维训练的最佳知识载体。是一个优秀的计算机科学工作者必修的一门课程。2009-7-26691.4.3基本概念对语言研究的三个方面–表示(REPRESENTATION)——无穷语言的表示。–有穷描述(FINITEDESCRIPTION)——研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。–结构(STRUCTURE)——语言的结构特征。2009-7-26701.4.3基本概念字母表(ALPHABET)–字母表是一个非空有穷集合，字母表中的元素称为该字母表的一个字母(LETTER)。又叫做符号(SYMBOL)、或者字符(CHARACTER)。–非空性。–有穷性。例如：{A,B,C,D}{A,B,C,…,Z}{0,1}2009-7-26711.4.3基本概念字符的两个特性–整体性(MONOLITH)，也叫不可分性。–可辨认性(DISTINGUISHABLE)，也叫可区分性。例（续）{A,A′,B,B′}{AA,AB,BB}{∞,∧,∨,≥,≤}2009-7-26721.4.3基本概念字母表的乘积(PRODUCT)∑1∑2={AB|A∈∑1,B∈∑2}例如：{0,1}{0,1}={00,01,10,00}{0,1}{A,B,C,D}={0A,0B,0C,0D,1A,1B，1C,1D}{A,B,C,D}{0,1}={A0,A1,B0,B1,C0,C1，D0,D1}{AA,AB,BB}{0,1}={AA0,AA1,AB0,AB1,BB0，BB1}2009-7-26731.4.3基本概念字母表∑的N次幂∑0={Ε}∑N=∑N-1∑Ε是由∑中的0个字符组成的。∑的正闭包∑+=∑∪∑2∪∑3∪∑4∪…∑的克林闭包∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪…2009-7-26741.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,…}2009-7-26751.4.3基本概念结论：∑*={X|X是∑中的若干个,包括0个字符,连接而成的一个字符串}。∑+={X|X是∑中的至少一个字符连接而成的字符串}。2009-7-26761.4.3基本概念句子(SENTENCE)∑是一个字母表,?X∈∑*,X叫做∑上的一个句子。句子相等。两个句子被称为相等的，如果它们对应位置上的字符都对应相等。别称字(WORD),(字符、符号)行(LINE),(字符、符号)串(STRING)。2009-7-26771.4.3基本概念出现(APPERANCE)–X,Y∈∑*,A∈∑，句子XAY中的A叫做A在该句子中的一个出现。–当X=Ε时,A的这个出现为字符串XAY的首字符–如果A的这个出现是字符串XAY的第N个字符，则Y的首字符的这个出现是字符串XAY的第N+1个字符。–当Y=Ε时,A的这个出现是字符串XAY的尾字符–例,ABAABB。2009-7-26781.4.3基本概念句子的长度(LENGTH)–?X∈∑*，句子X中字符出现的总个数叫做该句子的长度,记作|X|。–长度为0的字符串叫空句子,记作Ε。例如：|ABAABB|=6|BBAA|=4|Ε|=0|BBABAABBBAA|=112009-7-26791.4.3基本概念注意事项–Ε是一个句子。–{Ε}≠Φ。这是因为{Ε}不是一个空集，它是含有一个空句子Ε的集合。|{Ε}|=1，而|Φ|=0。2009-7-26801.4.3基本概念并置(CONCATENATION)–X,Y∈∑*,X,Y的并置是由串X直接相接串Y所组成的。记作XY。并置又叫做连结。串X的N次幂X0=ΕXN=XN-1X2009-7-26811.4.3基本概念例如：–对X=001,Y=1101X0=Y0=ΕX4=001001001001Y4=1101110111011101–对X=0101,Y=110110X2=01010101Y2=110110110110X4=0101010101010101Y4=1101101101101101101101102009-7-26821.4.3基本概念∑*上的并置运算性质⑴结合律,(XY)Z=X(YZ)。⑵左消去律：如果XY=XZ,则Y=Z。⑶右消去律：如果YX=ZX,则Y=Z。⑷惟一分解性：存在惟一确定的A1,A2,…,AN∈∑,使得X=A1A2…AN。⑸单位元素,ΕX=XΕ=X。2009-7-26831.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)。2009-7-26841.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的最大公共后缀。2009-7-26851.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,BAABB2009-7-26861.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。2009-7-26871.4.3基本概念结论⑹{W|W是X的后缀}={W|W是X的真后缀}∪{X}，|{W|W是X的后缀}|=|{W|W是X的真后缀}|+1。⑺对于任意字符串W,W是自身的前缀,但不是自身的真前缀；W是自身的后缀,但不是自身的真后缀。⑻对于任意字符串W,Ε是W的前缀，且是W的真前缀；Ε是W的后缀，且是W的真后缀2009-7-26881.4.3基本概念约定⑴用小写字母表中较为靠前的字母A,B，C,…表示字母表中的字母。⑵用小写字母表中较为靠后的字母X,Y，Z,…表示字母表上的句子。⑶用XT表示X的倒序。例如，如果X=ABC，则XT=CBA。2009-7-26891.4.3基本概念子串(SUBSTRING)–W,X,Y,Z∈∑*，且W=XYZ，则称Y是W的子串。公共子串(COMMONSUBSTRING)–T,U,V,W,X,Y,Z∈∑*，且T=UYV,W=XYZ，则称Y是T和W的公共子串(COMMONSUBSTRING)。如果Y1,Y2,……,YN是T和W的公共子串，且MAX{|Y1|,|Y2|,…,|YN|}=|YJ|，则称YJ是T和W的最大公共子串。–两个串的最大公共子串并不一定是惟一的。2009-7-26901.4.3基本概念语言(LANGUAGE)L?∑*,L称为字母表∑上的一个语言(LANGUAGE),?X∈L,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}*，{0}{0,1}*{1},{0,1}*{111}{0,1}*2009-7-26911.4.3基本概念语言的乘积(PRODUCT)L1?∑1*,L2?∑2*,语言L1与L2的乘积是一个语言,该语言定义为：L1L2={XY|X∈L1,Y∈L2}是字母表∑1∪∑2上的语言。2009-7-26921.4.3基本概念例⑴L1={0,1}。⑵L2={00,01,10,11}。⑶L3={0,1,00,01,10,11,000,…}=∑+。⑷L4={Ε,0,1,00,01,10,11,000,…}=∑*。⑸L5={0N|N≥1}。⑹L6={0N1N|N≥1}。⑺L7={1N|N≥1}。⑻L8={0N1M|N,M≥1}。⑼L9={0N1N0N|N≥1}。⑽L10={0N1M0K|N,M,K≥1}。⑾L11={X|X∈∑+且X中0和1的个数相同}。2009-7-26931.4.3基本概念上述几个语言的部分特点及相互关系上述所有语言都是L4的子集(子语言)；L1,L2是有穷语言；其他为无穷语言；其中L1是∑上的所有长度为1的句子组成的语言,L2是∑上的所有长度为2的句子组成的语言；L3,L4分别是∑的正闭包和克林闭包；L5L7≠L6，但L5L7=L8；同样L9≠L10，但是我们有,L6?L5L7,L9?L10。2009-7-26941.4.3基本概念L6={0N1N|N?1}中的句子中的0和1的个数是相同的,并且所有的0在所有的1的前面,L11={X|X∈∑+且X中0和1的个数相同}中的句子中虽然保持着0的个数和1的个数相等,但它并没要求所有的0在所有的1的前面。例如,0101,1100∈L11,但是0101?L6，1100?L6。而对?X∈L6,有X∈L11。所以,L6?L11。2009-7-26951.4.3基本概念L1?L12,L2?L12L5?L12,L6?L12L7?L12,L8?L12L9?L12,L10?L12L1?L10,L2?L10L5?L10,L6?L10L7?L10,L8?L10L9?L10,L10?L122009-7-26961.4.3基本概念例⑴{X|X=XT,X∈∑}。⑵{XXT|X∈∑+}。⑶{XXT|X∈∑*}。⑷{XWXT|X,W∈∑+}。⑸{XXTW|X,W∈∑+}。2009-7-26971.4.3基本概念幂L∈∑*,L的N次幂是一个语言，该语言定义为⑴当N=0是,LN={Ε}。⑵当N?1时,LN=LN-1L。正闭包L+=L∪L2∪L3∪L4∪…克林闭包L*=L0∪L∪L2∪L3∪L4∪…2009-7-26981.5小结本章简单叙述了一些基础知识，一方面，希望读者通过对本章的阅读，熟悉集合、关系、图、形式语言等相关的一些基本知识点，为以后各章学习作适当的准备。另一方面，也使读者熟悉本书中一些符号的意义。2009-7-26991.5小结(1)集合：集合的表示,集合之间的关系,集合的基本运算。(2)关系：主要介绍了二元关系相关的内容。包括等价关系,等价分类,关系合成,关系闭包。(3)递归定义与归纳证明。2009-7-261001.5小结(4)图：无向图,有向图,树的基本概念。(5)语言与形式语言：自然语言的描述,形式语言和自动机理论的出现,形式语言和自动机理论对计算机科学与技术学科人才能力培养的作用(6)基本概念：字母表,字母,句子,字母表上的语言,语言的基本运算2009-7-26101第2章文法对任何语言L，有一个字母表∑,使得L?∑*。L的具体组成结构是什么样的？一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？……。这些问题对有穷语言来说，比较容易解决。这些问题对无穷语言来说，不太容易解决。语言的有穷描述。2009-7-26102第2章文法主要内容文法的直观意义与形式定义,推导,文法产生的语言,句子,句型；乔姆斯基体系,左线性文法,右线性文法,文法的推导与归约；空语句。重点文法,推导,归约,模型的等价性证明。难点形式化的概念，文法的构造。2009-7-261032.1启示文法的概念最早是由语言学家们在研究自然语言理解中完成形式化。归纳如下句子的描述：⑴哈尔滨是美丽的城市。⑵北京是祖国的首都。⑶集合是数学的基础。⑷形式语言是很抽象的。⑸教育走在社会发展的前面。⑹中国进入WTO。2009-7-261042.1启示6个句子的主体结构={哈尔滨,北京,集合,形式语言,教育,中国}={是美丽的城市，是祖国的首都，是数学的基础，是很抽象的，走在社会发展的前面，进入WTO}={。}2009-7-261052.1启示可以是或者。={北京,哈尔滨,形式语言,中国,教育,集合,WTO,美丽的城市,祖国的首都,数学的基础,社会发展的前面}。={是,走在,进入}。={很抽象的}。把取名为。2009-7-261062.1启示2009-7-261072.1启示表示成Α?Β形式????是2009-7-261082.1启示?走在?进入?很抽象的?北京?哈尔滨?形式语言2009-7-261092.1启示?中国?教育?集合?WTO?美丽的城市?祖国的首都?数学的基础?社会发展的前面?。2009-7-261102.1启示表示一个语言，需要4种东西⑴形如的,符号,它们表示相应语言结构中某个位置上可以出现的一些内容。每个,符号,对应的是一个集合，在该语言的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种,符号,代表的是一个语法范畴。⑵所有的,规则,,都是为了说明的结构而存在，相当于说，定义的就是。2009-7-261112.1启示⑶形如北京的,符号,它们是所定义语言的合法句子中将出现的,符号,。仅仅表示自身，称为终极符号。⑷所有的,规则,都呈Α?Β的形式在产生语言的句子中被使用，称这些,规则,为产生式。2009-7-261122.2形式定义文法(GRAMMAR)G=(V,T,P,S)–V——为变量(VARIABLE)的非空有穷集。A∈V,A叫做一个语法变量(SYNTACTICVARIABLE)，简称为变量，也可叫做非终极符号(NONTERMINAL)。它表示一个语法范畴(SYNTACTICCATEGORY)。所以，本文中有时候又称之为语法范畴。2009-7-261132.2形式定义–T——为终极符(TERMINAL)的非空有穷集。A∈T,A叫做终极符。由于V中变量表示语法范畴,T中的字符是语言的句子中出现的字符，所以，有V∩T=Φ。–S——S∈V，为文法G的开始符号(STARTSYMBOL)。2009-7-261142.2形式定义–P——为产生式(PRODUCTION)的非空有穷集合。P中的元素均具有形式Α?Β,被称为产生式，读作,Α定义为Β。其中Α∈(V∪T)+，且Α中至少有V中元素的一个出现。Β∈(V∪T)*。Α称为产生式Α?Β的左部,Β称为产生式Α?Β的右部。产生式又叫做定义式或者语法规则。2009-7-261152.2形式定义例2-1以下四元组都是文法。⑴({A},{0,1},{A?01,A?0A1,A?1A0},A)。⑵({A},{0,1},{A?0,A?0A},A)。⑶({A,B},{0,1},{A?01,A?0A1,A?1A0,B?AB，B?0},A)。⑷({A,B},{0,1},{A?0,A?1,A?0A,A?1A}，A)。2009-7-261162.2形式定义⑸({S,A,B,C,D},{A,B,C,D,#},{S?ABCD，S?ABC#,A?AAA,AB?AABBB,BC?BBCCC，CC?CCCC,CD?CCD#,CD?D#,CD?#D},S)。⑹({S},{A,B},{S?00S,S?11S,S?00,S?11}，S)。2009-7-261172.2形式定义约定⑴对一组有相同左部的产生式Α?Β1,Α?Β2,…,Α?ΒN可以简单地记为：Α?Β1|Β2|…|ΒN读作,Α定义为Β1，或者Β2,…,或者ΒN。并且称它们为Α产生式。Β1,Β2,…,ΒN称为候选式(CANDIDATE)。2009-7-261182.2形式定义⑵使用符号英文字母表较为前面的大写字母，如A,B,C,…表示语法变量；英文字母表较为前面的小写字母,如A,B,C,…表示终极符号；英文字母表较为后面的大写字母,如X,Y,Z,…表示该符号是语法变量或者终极符号；英文字母表较为后面的小写字母,如X,Y,Z,…表示由终极符号组成的行；希腊字母Α,Β,Γ…表示由语法变量和终极符号组成的行2009-7-261192.2形式定义例2-3四元组是否满足文法的要求。–({A,B,C,E},{A,B,C},{S?ABC|ABC,D?E|A，FB?C,A?A,E?ABC|Ε},S)–4种修改(1)({A,B,C,E,S,D,F},{A,B,C,E}，{S?ABC|ABC,D?E|A,FB?C,A?A,E?ABC|Ε}，S)。(2)({A,B,C,E,S},{A,B,C},{S?ABC|ABC，A?A,E?ABC|Ε},S)。(3)({A,B,C,E},{A,B,C},{A?A,E?ABC|Ε},A)。(4)({A,B,C,E},{A,B,C},{A?A,E?ABC|Ε},E)。2009-7-261202.2形式定义推导(DERIVATION)设G=(V,T,P,S)是一个文法，如果Α?Β∈P，Γ,Δ∈(V∪T)*，则称ΓΑΔ在G中直接推导出ΓΒΔ。ΓΑΔ?GΓΒΔ读作,ΓΑΔ在文法G中直接推导出ΓΒΔ。,直接推导,可以简称为推导(DERIVATION)，也称推导为派生。2009-7-261212.2形式定义归约(REDUCTION)–ΓΑΔ?GΓΒΔ–称ΓΒΔ在文法G中直接归约成ΓΑΔ。在不特别强调归约的直接性时,,直接归约,可以简称为归约。2009-7-261222.2形式定义1,推导与归约表达的意思的异同。2,推导与归约和产生式不一样。所以,?G和?所表达的意思不一样。3,推导与归约是一一对应的。4,推导与归约的作用。2009-7-261232.2形式定义G,?G+,?G*当成(V∪T)*上的二元关系。(1)Α?GNΒ,表示Α在G中经过N步推导出Β；Β在G中经过N步归约成Α。即，存在Α1，Α2,…,ΑN-1∈(V∪T)*使得Α?GΑ1，Α1?GΑ2,…,ΑN-1?GΒ。(2)当N=0时，有Α=Β。即Α?G0Α。(3)Α?G+Β,表示Α在G中经过至少1步推导出Β；Β在G中经过至少1步归约成Α。2009-7-261242.2形式定义(4)Α?G*Β,表示Α在G中经过若干步推导出Β；Β在G中经过若干步归约成Α。分别用?,?+,?*,?N代替G,?G+,?G*,?GN。2009-7-261252.2形式定义例2-4设G=({A},{A},{A?A|AA},A)A?AA使用产生式A?AAAAA使用产生式A?AAAAAA使用产生式A?AAAAAAA使用产生式A?AA…A…AA使用产生式A?AAA…AA使用产生式A?A?2009-7-261262.2形式定义A?AA使用产生式A?AAAAA使用产生式A?AAAAAA使用产生式A?AAAAAAA使用产生式A?AA…A…AA使用产生式A?AAA…AAA使用产生式A?AA2009-7-261272.2形式定义AAAAAAA?AAAAAAAA使用产生式A?AAAAAAAAAAA使用产生式A?AAAAAAAAAAA使用产生式A?AAAAAAAAAA使用产生式A?AAAAAAAAAA使用产生式A?AAAAAAAAAAA使用产生式A?AAAAAAAAAAAA使用产生式A?AAAAAAAAAAA使用产生式A?A2009-7-261282.2形式定义例2-5设G=({S,A,B},{0,1}，{S?A|AB,A?0|0A,B?1|11},S)对于N?1，A?N0N首先连续N-1次使用产生式；A?0A,最后使用产生式A?0；A?N0NA连续N次使用产生式A?0A；B?1使用产生式B?1；B?11使用产生式B?11。2009-7-261292.2形式定义语法范畴A代表的集合L(A)={0,00,000,0000,……}={0N|N?1}；语法范畴B代表的集合L(B)={1,11}语法范畴S代表的集合L(S)=L(A)∪L(A)L(B)={0,00,000,0000,…}∪{0,00,000,0000,…}{1,11}={0,00,000,0000,…}∪∪{01,001,0001,00001,…}∪∪{011,0011,00011,000011,…}2009-7-261302.2形式定义例2-6设G=({A},{0,1},{A?01,A?0A1},A)，A?N0NA1NN?00NA1N?0N+1A1N+1N?00NA1N?0N+11N+1N?00NA1N?I0N+IA1N+IN?0,I?00NA1N?I0N+I1N+IN?0,I?00NA1N?*0MA1MN?0,M?N0NA1N?+0M1MN?0,M?N+10NA1N?+0MA1MN?0,M?N+10NA1N?+0M1MN?0,M?N+12009-7-261312.2形式定义几点结论–对任意的X∈∑+，我们要使语法范畴D代表的集合为{XN|N?0}，可用产生式组{D?Ε|XD}来实现。–对任意的X,Y∈∑+，我们要使语法范畴D代表的集合为{XNYN|N?1}，可用产生式组{D?XY|XDY}来实现。–对任意的X,Y∈∑+，我们要使语法范畴D代表的集合为{XNYN|N?0}，可用产生式组{D?Ε|XDY}来实现。2009-7-261322.2形式定义语言(LANGUAGE)L(G)={W|W∈T*且S?*W}句子(SENTENCE)W∈L(G),W称为G产生的一个句子。句型(SENTENTIALFORM)G=(V,T,P,S)，对于?Α∈(V∪T)*，如果S*Α,则称Α是G产生的一个句型。2009-7-261332.2形式定义句子W是从S开始，在G中可以推导出来的终极符号行，它不含语法变量。句型Α是从S开始，在G中可以推导出来的符号行，它可能含有语法变量。例2-7给定文法G=({S,A,B,C,D},{A，B,C,D,#},{S?ABCD|ABC#,A?AAA，AB?AABBB,BC?BBCCC,CC?CCCC，CD?CCD#,CD?D#,CD?#D},S)2009-7-261342.2形式定义S?ABCD使用产生式S?ABCDAAABCD使用产生式A?AAAAAAAABCD使用产生式A?AAAAAAAAABBBCD使用产生式AB?AABBBAAAAAABBBBCCCD使用产生式BC?BBCCCAAAAAABBBBCCCCCD使用产生式CC?CCCCAAAAAABBBBCCCC#D使用产生式CD?#D2009-7-261352.2形式定义S?ABCD使用产生式S?ABCDABBCCCD使用产生式BC?BBCCCAAABBCCCD使用产生式A?AAAAAABBCCCCD#使用产生式CD?CCD#AAAAABBCCCCD#使用产生式A?AAAAAAAAAABBCCCCD#使用产生式A?AAAAAAAAAAAABBCCCCD#使用产生式A?AAA2009-7-261362.2形式定义例2-8构造产生标识符的文法G=({,,,},{0，1,…,9,A,B,C,…,Z,A,B,C,…,Z},P,)P={?|，?||，?A|B|C|D|E|F|G|H|I|J|K|L|M|N|O，?P|Q|R|S|T|U|V|W|X|Y|Z,?A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z,?0|1|2|3|4|5|6|7|8|9}2009-7-261372.2形式定义G′=({,,},{0,1，2,…,9,A,B,C,…,Z,A,B，C,…,Z},P′,)P′={?，?A|B|C|D|E|F|G|H|I|J|K|L|M|N?O|P|Q|R|S|T|U|V|W|X|Y|Z,?A|B|C|D|E|F|G|H|I|J|K|L|M|N?O|P|Q|R|S|T|U|V|W|X|Y|Z,2009-7-261382.2形式定义?Ε|0|1|2|3|4|5,?6|7|8|9,?A|B|C|D|E|F，?G|H|I|J|K,?L|M|N|O|P|Q，?R|S|T|U|V,?W|X|Y|Z|A|B，?C|D|E|F|G,?H|I|J|K|L|M，?N|O|P|Q|R,?S|T|U|V|W|X?Y|Z}2009-7-261392.2形式定义?332323N23N238N238N23D8N23D8N23ID8N232009-7-261402.2形式定义标识符>?IIDID8ID8NID8N2ID823ID8N232009-7-261412.2形式定义使用符号使文法更简洁G′′=({},{B,A,D},{?B|A|B|A|D},)G′′′=({L},{B,A,D},{L?B|A|LB|LA|LD},L)G′′′′=({L,H,T},{B,A,D},{L?HT，H?B|A,T?Ε|BT|AT|DT},L)2009-7-261422.3文法的构造例2-9构造文法G，使L(G)={0,1,00,11}–将文法的开始符号定义为这4个句子。G1=({S},{0,1},{S?0,S?1,S?00,S?11},S)–先用变量A表示0，用变量B表示1。G2=({S,A,B},{0,1},{S?A,S?B,S?AA，S?BB,A?0,B?1},S)–基于G2，考虑,规范性,问题。G3=({S,A,B},{0,1},{S?0,S?1,S?0A，S?1B,A?0,B?1},S)2009-7-261432.3文法的构造–可以在V,T中增加一些元素，以获得,不同的,文法。G4=({S,A,B,C},{0,1,2},{S?A,S?B，S?AA,S?BB,A?0,B?1},S)G5=({S,A,B,C},{0,1,2},{S?A,S?B，S?AA,S?BB,A?0,B?1,CACS?21，C?11,C?2},S)L(G1)=L(G2)=L(G3)=L(G4)=L(G5)2009-7-261442.3文法的构造等价(EQUIVALENCE)–设有两个文法G1和G2，如果L(G1)=L(G2)，则称G1与G2等价。约定–对一个文法，只列出该文法的所有产生式，且所列第一个产生式的左部是该文法的开始符号。2009-7-261452.3文法的构造G1,S?0|1|00|11G2,S?A|B|AA|BB,A?0,B?1G3,S?0|1|0A|1B,A?0,B?1G4,S?A|B|AA|BB,A?0,B?1G5,S?A|B|BB,A?0,B?1,CACS?21，C?11,C?22009-7-261462.3文法的构造例2-10L={0N|N?1}G6,S?0|0SL={0N|N?0}G7,S?Ε|0SL={02N13N|N?0}G8,S?Ε|00S1112009-7-261472.3文法的构造例2-11构造文法G9，使L(G9)={W|W∈{A,B,…,Z}+}。G9,S?A|ASA?A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z用S?A|AS生成AN。不可以用A?A|B|C|…|Z表示。A?A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z不可以用A?A8表示A?AAAAAAAA。不能用A?AN表示A可以产生任意多个A。2009-7-261482.3文法的构造例2-12构造文法G10，使L(G10)={WWT|W∈{0,1,2,3}+}。文法S?HEH?0|1|2|3|0H|1H|2H|3HE?0|1|2|3|E0|E1|E2|E3难以生成L(G10)。2009-7-261492.3文法的构造{WWT|W∈{0,1,2,3}+}的句子的特点设W=A1A2…AN，从而有WT=AN…A2A1,故WWT=A1A2…ANAN…A2A1满足F(WWT,I)=F(WWT,|WWT|-I+1)。递归地定义L–⑴对?A∈{0,1,2,3},AA∈L；–⑵如果X∈L,则对?A∈{0,1,2,3},AXA∈L；–⑶L中不含不满足(1),(2)任何其他的串。2009-7-261502.3文法的构造根据递归定义中的第一条,有如下产生式组：S?00|11|22|33再根据递归定义第二条,又可得到如下产生式组：S?0S0|1S1|2S2|3S3从而,G10,S?00|11|22|33|0S0|1S1|2S2|3S32009-7-261512.3文法的构造例2-13构造文法G12，使L(G12)={W|W是我们习惯的十进制有理数}。G12,S?R|+R|-RR?N|BB?N.DN?0|AMD?0|MAA?1|2|3|4|5|6|7|8|9M?Ε|0M|1M|2M|3M|4M|5M|6M|7M|8M|9M2009-7-261522.3文法的构造例2-14构造产生算术表达式的文法：⑴基础：常数是算术表达式,变量是算术表达式；⑵归纳：如果E1,E2是表达式,则+E1,-E1、E1+E2,E1-E2,E1*E2,E1/E2,E1**E2,FUN(E1)是算术表达式。其中FUN为函数名。⑶只有满足(1)和(2)的才是算术表达式。G13,E?ID|C|+E|-E|E+E|E-E|E*E|E/E|E**E|FUN(E)2009-7-261532.3文法的构造例2-15构造产生语言{ANBNCN|N?1}的文法。文法G=({S1},{A,B},{S1?AB|AS1B},S1)产生的语言{ANBN|N?1}形式上看起来与语言{ANBNCN|N?1}比较接近。G=({S2},{C},{S2?C|CS2},S2)产生的语言是{CN|N?1}。{ANBNCN|N?1}≠{ANBN|N?1}{CN|N?1}2009-7-261542.3文法的构造文法S?S1S2S1?AB|AS1BS2?C|CS2不能产生语言{ANBNCN|N?1}而是产生语言{ANBN|N?1}{CN|N?1}2009-7-261552.3文法的构造文法G,S?ABC|ASBC产生的语言为：{AN(BC)N|N?1}焦点：交换B和C的位置。2009-7-261562.3文法的构造G14,S?ABC|ASBC，CB?BCAB?ABBB?BBBC?BCCC?CCG14′,S?ABC|ASBC，BB?BBCB?BC2009-7-26157文法的乔姆斯基体系文法G=(V,T,P,S)G叫做0型文法(TYPE0GRAMMAR)，也叫做短语结构文法(PHRASESTRUCTUREGRAMMAR,PSG)。L(G)叫做0型语言。也可以叫做短语结构语言(PSL)、递归可枚举集(RECURSIVELYENUMERABLE,R.E,)。2009-7-26158文法的乔姆斯基体系G是0型文法。如果对于?Α?Β∈P，均有|Β|?|Α|成立，则称G为1型文法(TYPE1GRAMMAR)，或上下文有关文法(CONTEXTSENSITIVEGRAMMAR,CSG)。L(G)叫做1型语言(TYPE1LANGUAGE)或者上下文有关语言(CONTEXTSENSITIVELANGUAGE,CSL)。2009-7-26159文法的乔姆斯基体系G是1型文法如果对于?Α?Β∈P，均有|Β|?|Α|，并且Α∈V成立，则称G为2型文法(TYPE2GRAMMAR)，或上下文无关文法(CONTEXTFREEGRAMMAR,CFG)。L(G)叫做2型语言(TYPE2LANGUAGE)或者上下文无关语言(CONTEXTFREELANGUAGE,CFL)。2009-7-26160文法的乔姆斯基体系G是2型文法如果对于?Α?Β∈P,Α?Β均具有形式A?WA?WB其中A,B∈V,W∈T+。则称G为3型文法(TYPE3GRAMMAR),也可称为正则文法(REGULARGRAMMAR,RG)或者正规文法。L(G)叫做3型语言(TYPE3LANGUAGE),也可称为正则语言或者正规语言(REGULARLANGUAGE,RL)。2009-7-26161文法的乔姆斯基体系⑴如果一个文法G是RG,则它也是CFG、CSG和短语结构文法。反之不一定成立。⑵如果一个文法G是CFG,则它也是CSG和短语结构文法。反之不一定成立。⑶如果一个文法G是CSG,则它也是短语结构文法。反之不一定成立。相应地：⑷RL也是CFL,CSL和短语结构语言。反之不一定成立。2009-7-26162文法的乔姆斯基体系⑸CFL也是CSL和短语结构语言。反之不一定成立。⑹CSL也是短语结构语言。反之不一定成立⑺当文法G是CFG时,L(G)却可以是RL。⑻当文法G是CSG时,L(G)可以是RL,CSL。⑼当文法G是短语结构文法时,L(G)可以是RL,CSL和CSL。2009-7-26163文法的乔姆斯基体系定理2-1L是RL的充要条件是存在一个文法，该文法产生语言L，并且它的产生式要么是形如,A?A的产生式，要么是形如A?AB的产生式。其中A,B为语法变量,A为终极符号。证明,–充分性：设有G′,L(G′)=L，且G′的产生式的形式满足定理要求。这种文法就是RG。所以，G′产生的语言就是RL，故L是RL。2009-7-26164文法的乔姆斯基体系必要性构造：用产生式组：A?A1A1A1?A2A2…AN-1?AN代替产生式A?A1A2…AN2009-7-26165文法的乔姆斯基体系用产生式组A?A1A1A1?A2A2…AN-1?ANB代替产生式A?A1A2…ANB2009-7-26166文法的乔姆斯基体系证明L(G′)=L(G)。施归纳于推导的步数，证明一个更一般的结论：对于?A∈V,A?G+X?A?G′+X。因为S∈V，所以结论自然对S成立。2009-7-26167文法的乔姆斯基体系几点注意事项⑴我们是按照RG的一般定义来构造一个与之等价的文法的,这与读者以前熟悉的根据一个具体的对象构造另一个对象是不同的。在这里,可以使用的是非常一般的条件——一个一般模型。这也是这类问题的证明所要求的。而且在本书的后面,将会有更多这样的情况。2009-7-26168文法的乔姆斯基体系⑵为了证明一个特殊的结论,可以通过证明一个更为一般的结论来完成。这从表面上好像是增加了我们要证明的内容,但实际上它会使我们能够更好地使用归纳假设,以便顺利地获得我们所需要的结论。2009-7-26169文法的乔姆斯基体系⑶施归纳于推导的步数是证明本书中不少问题的较为有效的途径。有时我们还会对字符串的长度施归纳。本证明的主要部分含两个方面,首先是构造,然后对构造的正确性进行证明。这种等价性证明的思路是非常重要的。2009-7-26170文法的乔姆斯基体系线性文法(LINERGRAMMAR)–设G=(V,T,P,S),如果对于?Α?Β∈P，Α?Β均具有如下形式：–A?W–A?WBX–其中A,B∈V,W,X∈T*，则称G为线性文法。线性语言(LINERLANGUAGE)–L(G)叫做线性语言2009-7-26171文法的乔姆斯基体系右线性文法(RIGHTLINERGRAMMAR)–设G=(V,T,P,S),如果对于?Α?Β∈P，Α?Β均具有如下形式：–A?W–A?WB–其中A,B∈V,W,X∈T*，则称G为线性文法。右线性语言(RIGHTLINERLANGUAGE)–L(G)叫做右线性语言。2009-7-26172文法的乔姆斯基体系左线性文法(LEFTLINERGRAMMAR)–设G=(V,T,P,S),如果对于?Α?Β∈P，Α?Β均具有如下形式：–A?W–A?BW–其中A,B∈V,W,X∈T*，则称G为线性文法。左线性语言(LEFTLINERLANGUAGE)–L(G)叫做右线性语言。2009-7-26173文法的乔姆斯基体系定理2-2L是一个左线性语言的充要条件是存在文法G,G中的产生式要么是形如,A?A的产生式，要么是形如A?BA的产生式，使得L(G)=L。其中A,B为语法变量,A为终极符号。2009-7-26174文法的乔姆斯基体系定理2-3左线性文法与右线性文法等价。按照定理2-1的证明经验,要想证明本定理,需要完成如下工作：–对任意右线性文法G,我们能够构造出对应的左线性文法G′,使得L(G′)=L(G)；–对任意左线性文法G,我们能够构造出对应的右线性文法G′,使得L(G′)=L(G)。2009-7-26175文法的乔姆斯基体系例2-17语言{0123456}的左线性文法和右线性文法的构造。右线性文法GR,SR?0ARAR?1BRBR?2CRCR?3DRDR?4ERER?5FRFR?62009-7-26176文法的乔姆斯基体系0123456在文法GR中的推导SR?0AR使用产生式SR?0AR01BR使用产生式AR?1BR012CR使用产生式BR?2CR0123DR使用产生式CR?3DR01234ER使用产生式DR?4ER012345FR使用产生式ER?5FR0123456使用产生式FR?62009-7-26177文法的乔姆斯基体系左线性文法GL,SL?AL6AL?BL5BL?CL4CL?DL3DL?EL2EL?FL1FL?02009-7-26178文法的乔姆斯基体系2009-7-26179文法的乔姆斯基体系0123456在文法GL中的推导SL?AL6使用产生式SL?AL6BL56使用产生式AL?BL5CL456使用产生式BL?CL4DL3456使用产生式CL?DL3EL23456使用产生式DL?EL2FL1234456使用产生式EL?FL10123456使用产生式FL?02009-7-26180文法的乔姆斯基体系0123456被归约成文法GL的开始符号S0123456FL1234456使用产生式FL?0EL23456使用产生式EL?FL1DL3456使用产生式DL?EL2CL456使用产生式CL?DL3BL56使用产生式BL?CL4AL6使用产生式AL?BL5SL使用产生式SL?AL62009-7-26181文法的乔姆斯基体系2009-7-26182文法的乔姆斯基体系定理2-4左线性文法的产生式与右线性文法的产生式混用所得到的文法不是RG。证明：设有文法G15,S?0AA?S1|1不难看出,L(G15)={0N1N|N?1}。我们构造不出RGG，使得L(G)=L(G15)={0N1N|N?1}。因为L(G15)={0N1N|N?1}不是RL。所以,G15不是RG。有关该语言不是RL的证明我们将留到研究RL的性质时去完成。2009-7-261832.5空语句形如A?Ε的产生式叫做空产生式，也可叫做Ε产生式。在RG,CFG,CSG中，都不能含有空产生式。所以，任何CSL中都不含有空语句Ε。从而CFL和RL中都不能含空语句Ε。空语句Ε在一个语言中的存在并不影响该语言的有穷描述的存在性，甚至除了为生成空语句Ε外，空产生式可以不被用于语言中其他任何句子的推导中。2009-7-261842.5空语句允许CSL,CFL,RL包含空语句Ε后，还会给我们进行问题的处理提供一些方便。允许在RG,CFG,CSG中含有空产生式允许CSL,CFL,RL包含空语句Ε。2009-7-261852.5空语句定理2-5设G=(V,T,P,S)为一文法，则存在与G同类型的文法G′=(V′,T,P′,S′)，使得L(G)=L(G′)，但G′的开始符号S′不出现在G′的任何产生式的右部。证明：构造当文法G=(V,T,P,S)的开始符号S不出现在P中的任何产生式的右部时,G就是所求G′=(V∪{S′},T,P′,S′)P′=P∪{S′?Α|S?Α∈P}2009-7-261862.5空语句证明L(G)?L(G′)对任意的X∈L(G′),由文法产生的语言的定义知,在G′中存在如下推导：S′?Α使用产生式S′?Α*X使用P′中的除S′?Α以外的其他产生式。在推导Α?*X中使用的产生式都是P中的产生式。因此，推导Α?*X在G中仍然成立。2009-7-261872.5空语句由P′的定义知，必有S?Α∈P所以，S?Α使用P中的产生式S?Α*X使用P中的产生式故，L(G′)?L(G)2009-7-261882.5空语句设G中存在如下推导：S?Α使用P中的产生式S?Α*X使用P中的产生式由P′=P∪{S′?Α|S?Α∈P},知道G′中,S′?Α使用产生式S′?Α*X使用P′所包含的P中的其他产生式。故,L(G)?L(G′)。2009-7-261892.5空语句设G=(V,T,P,S)是一个文法，如果S不出现在G的任何产生式的右部，则：⑴如果G是CSG,则仍然称G=(V,T,P∪{S?Ε}，S)为CSG；G产生的语言仍然称为CSL。⑵如果G是CFG,则仍然称G=(V,T,P∪{S?Ε}，S)为CFG；G产生的语言仍然称为CFL。⑶如果G是RG,则仍然称G=(V,T,P∪{S?Ε}，S)为RG。G产生的语言仍然称为RL。2009-7-261902.5空语句定理2-6下列命题成立：⑴如果L是CSL,则L∪{Ε}仍然是CSL。⑵如果L是CFL,则L∪{Ε}仍然是CFL。⑶如果L是RL,则L∪{Ε}仍然是RL。2009-7-261912.5空语句证明：对第1个命题：设L是CSL,则存在一个CSGG=(V,T,P,S),使得L(G)=L。由定理2-5-1,我们不妨假设S不出现在G的任何产生式的右部。取：G′=(V,T,P∪{S?Ε},S)由于S不出现在G的任何产生式的右部,所以,S?Ε不可能出现在任何长度不为0的句子的推导中。2009-7-261922.5空语句易证：L(G′)=L(G)∪{Ε}。由于G′是CSG，所以,L(G)∪{Ε}是CSL。同理可证第2和第3个命题。2009-7-261932.5空语句定理2-7下列命题成立⑴如果L是CSL,则L-{Ε}仍然是CSL。⑵如果L是CFL,则L-{Ε}仍然是CFL。⑶如果L是RL，则L-{Ε}仍然是RL。2009-7-261942.5空语句证明：对第1个命题：设L是CSL,则存在一个CSGG=(V,T,P,S),使得L(G)=L。如果Ε?L,则L-{Ε}=L,所以,L-{Ε}是CSL。如果Ε∈L,由定理2-5-1,我们不妨假设S不出现在G的任何产生式的右部。取：G′=(V,T,P-{S?Ε},S)2009-7-261952.5空语句由于S不出现在G的任何产生式的右部,所以,如果L(G)中存在长度非0的句子,S?Ε不可能出现在它们的推导中。也就是说,将S?Ε从G中去掉后,不会影响L(G)中任何长度非0的句子的推导。容易证明：L(G′)=L(G)-{Ε}由于G′是CSG,所以,L(G)-{Ε}是CSL。同理可证其他两个命题。2009-7-261962.5空语句对于任意文法G=(V,T,P,S)，对于G中的其他变量A，出现形如A?Ε的产生式是不会改变文法产生的语言的类型的，而且这样一来，对我们进行文法的构造等工作还提供了很多方便。所以，我们约定：对于G中的任何变量A，在需要的时候，可以出现形如A?Ε的产生式。2009-7-261972.6小结本章讨论了语言的文法描述。首先介绍文法的基本定义和推导、归约、文法定义的语言、句子、句型、文法的等价等重要概念。讨论了如何根据语言的特点、通过用语法变量去表示适当的集合（语法范畴）的方法进行文法构造，并按照乔姆斯基体系，将文法划分成PSG,CSG,CFG、RG等4类。在这些文法中，线性文法是一类重要的文法。2009-7-261982.6小结⑴文法G=(V,T,P,S)。任意A∈V表示集合L(A)={W|W∈T*且A?*W}。⑵推导与归约。文法中的推导是根据文法的产生式进行的。如果Α?Β∈P,Γ,Δ∈(V∪T)*,则称ΓΑΔ在G中直接推导出ΓΒΔ,ΓΑΔ?GΓΒΔ；也称ΓΒΔ在文法G中直接归约成ΓΑΔ。2009-7-261992.6小结⑶语言,句子和句型。文法G产生的语言L(G)={W|W∈T*且S?*W},W∈L(G)为句子。一般地,由开始符号推出来的任意符号行叫做G的句型。⑷一个语言可以被多个文法产生,产生相同语言的文法被称是等价的。2009-7-262002.6小结⑸右线性文法的产生式都可以是形如A?A和A?AB的产生式。左线性文法的产生式都可以是形如A?A和A?BA的产生式。左线性文法与右线性文法是等价的。然而，左线性文法的产生式与右线性文法的产生式混用所得到的文法不是正则文法。2009-7-26201第3章有穷状态自动机主要内容确定的有穷状态自动机(DFA)–作为对实际问题的抽象,直观物理模型,形式定义,DFA接受的句子,语言,状态转移图。不确定的有穷状态自动机(NFA)–定义；–NFA与DFA的等价性；2009-7-26202第3章有穷状态自动机带空移动的有穷状态自动机(Ε-NFA)–定义。–Ε-NFA与DFA的等价性。FA是正则语言的识别器–正则文法(RG)与FA的等价性。–相互转换方法。–带输出的有穷状态自动机。–双向有穷状态自动机。2009-7-26203第3章有穷状态自动机重点,DFA的概念,DFA,NFA,Ε-NFA,RG之间的等价转换思路与方法。难点：对DFA概念的理解,DFA,RG的构造方法,RG与FA的等价性证明。2009-7-262043.1语言的识别推导和归约中的回溯问题将对系统的效率产生极大的影响S?AA|ABA?AA|CB?AB|D分析句子AAAC的过程中可能需要回溯。2009-7-262053.1语言的识别系统识别语言{ANC|N≥1}∪{AND|N≥1}的字符串过程中状态的变化图示如下：2009-7-262063.1语言的识别识别系统(模型)⑴系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。⑵我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。2009-7-262073.1语言的识别⑶系统在任何一个状态(当前状态)下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。2009-7-262083.1语言的识别⑷系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定句子的处理。⑸系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。2009-7-262093.1语言的识别相应的物理模型一个右端无穷的输入带。一个有穷状态控制器(FINITESTATECONTROL,FSC)。一个读头。系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头向右移动一格。2009-7-262103.1语言的识别有穷状态自动机的物理模型2009-7-262113.2有穷状态自动机有穷状态自动机(FINITEAUTOMATON,FA)M=(Q,∑,Δ,Q0,F)Q——状态的非空有穷集合。Q∈Q,Q称为M的一个状态(STATE)。∑——输入字母表(INPUTALPHABET)。输入字符串都是∑上的字符串。Q0——Q0∈Q,是M的开始状态(INITIALSTATE)，也可叫做初始状态或者启动状态。2009-7-262123.2有穷状态自动机Δ——状态转移函数(TRANSITIONFUNCTION)，有时候又叫做状态转换函数或者移动函数。Δ,Q×∑?Q，对?(Q,A)∈Q×∑,Δ(Q，A)=P表示,M在状态Q读入字符A，将状态变成P，并将读头向右移动一个带方格而指向输入字符串的下一个字符。F——F?Q，是M的终止状态(FINALSTATE)集合。Q∈F,Q称为M的终止状态,又称为接受状态(ACCEPTSTATE)。2009-7-262133.2有穷状态自动机例3-1下面是一个有穷状态自动机M1=({Q0,Q1,Q2},{0},Δ1,Q0,{Q2})其中,Δ1(Q0,0)=Q1,Δ1(Q1,0)=Q2,Δ1(Q2,0)=Q1用表3-1表示Δ1。状态说明状态输入字符0开始状态Q0Q1Q1Q2终止状态Q2Q12009-7-262143.2有穷状态自动机M2=({Q0,Q1,Q2,Q3},{0,1,2},Δ2,Q0,{Q2})Δ2(Q0,0)=Q1,Δ2(Q1,0)=Q2Δ2(Q2,0)=Q1,Δ2(Q3,0)=Q3Δ2(Q0,1)=Q3,Δ2(Q1,1)=Q3Δ2(Q2,1)=Q3,Δ2(Q3,1)=Q3Δ2(Q0,2)=Q3,Δ2(Q1,2)=Q3Δ2(Q2,2)=Q3,Δ2(Q3,2)=Q32009-7-262153.2有穷状态自动机状态说明状态输入字符012开始状态Q0Q1Q3Q3Q1Q2Q3Q3终止状态Q2Q1Q3Q3Q3Q3Q3Q3表3-2Δ2转换函数2009-7-262163.2有穷状态自动机将Δ扩充为QQ*:对任意的Q∈Q,W∈∑*,A∈∑,定义)),,(?(),(?)2(),(?)1(AWQWAQQQ2009-7-262173.2有穷状态自动机),()),,(?(),(?),(?AQAQAQAQ两值相同，不用区分这两个符号。2009-7-262183.2有穷状态自动机确定的有穷状态自动机–由于对于任意的Q∈Q,A∈∑,Δ(Q,A)均有确定的值，所以，将这种FA称为确定的有穷状态自动机(DETERMINISTICFINITEAUTOMATON，DFA)2009-7-262193.2有穷状态自动机M接受(识别)的语言对于?X∈∑*如果Δ(Q,W)∈F,则称X被M接受,如果Δ(Q,W)?F,则称M不接受X。L(M)={X|X∈∑*且Δ(Q,W)∈F}称为由M接受(识别)的语言L(M1)=L(M2)={02N|N?1}如果L(M1)=L(M2)，则称M1与M2等价。2009-7-262203.2有穷状态自动机例3-2构造一个DFA，它接受的语言为{X000Y|X,Y∈{0,1}*}Q0——M的启动状态；Q1——M读到了一个0,这个0可能是子串,000”的第1个0；Q2——M在Q1后紧接着又读到了一个0,这个0可能是子串,000”的第2个0；Q3——M在Q2后紧接着又读到了一个0,发现输入字符串含有子串,000”；因此,这个状态应该是终止状态。2009-7-262213.2有穷状态自动机Δ(Q0,1)=Q0——M在Q0读到了一个1,它需要继续在Q0,等待,可能是子串,000”的第1个0的输入字符0；Δ(Q1,1)=Q0——M在刚刚读到了一个0后,读到了一个1,表明在读入这个1之前所读入的0并不是子串,000”的第1个0,因此,M需要重新回到状态Q0,以寻找子串,000”的第1个0；2009-7-262223.2有穷状态自动机Δ(Q2,1)=Q0——M在刚刚发现了00后,读到了一个1,表明在读入这个1之前所读入的00并不是子串,000”的前两个0,因此,M需要重新回到状态Q0,以寻找子串,000”的第1个0；Δ(Q3,0)=Q3——M找到了子串,000”,只用读入该串的剩余部分。Δ(Q3,1)=Q3——M找到了子串,000”,只用读入该串的剩余部分。2009-7-262233.2有穷状态自动机M=({Q0,Q1,Q2,Q3},{0,1},{(Q0,0)=Q1，Δ(Q1,0)=Q2,Δ(Q2,0)=Q3,Δ(Q0,1)=Q0，Δ(Q1,1)=Q0,Δ(Q2,1)=Q0,Δ(Q3,0)=Q3，Δ(Q3,1)=Q3},Q0,{Q3})状态说明状态输入字符01开始状态Q0Q1Q0Q1Q2Q0Q2Q3Q0终止状态Q3Q3Q32009-7-262243.2有穷状态自动机一种更为直观的表示2009-7-262253.2有穷状态自动机状态转移图(TRANSITIONDIAGRAM)⑴Q∈Q?Q是该有向图中的一个顶点；⑵Δ(Q,A)=P?图中有一条从顶点Q到顶点P的标记为A的弧；⑶Q∈F?标记为Q的顶点被用双层圈标出；⑷用标有S的箭头指出M的开始状态。状态转移图又可以叫做状态转换图。2009-7-262263.2有穷状态自动机例3-3构造一个DFA，它接受的语言为{X000|X∈{0,1}*}。–状态Q0读到的0可能是输入字符串的最后三个0的第1个0；–在状态Q1紧接着读到的0可能是输入字符串的最后三个0的第2个0；–在状态Q2紧接着读到的0可能是输入字符串的最后三个0的第3个0；2009-7-262273.2有穷状态自动机–在状态Q3紧接着读到的0也可能是输入字符串的最后三个0的第3个0；–如果在状态Q1,Q2,Q3读到的是1，则要重新检查输入串是否以三个0结尾。2009-7-262283.2有穷状态自动机几点值得注意⑴定义FA时，常常只给出FA相应的状态转移图就可以了。⑵对于DFA来说，并行的弧按其上的标记字符的个数计算，对于每个顶点来说，它的出度恰好等于输入字母表中所含的字符的个数。2009-7-262293.2有穷状态自动机⑶不难看出，字符串X被FAM接受的充分必要条件是，在M的状态转移图中存在一条从开始状态到某一个终止状态的有向路，该有向路上从第1条边到最后一条边的标记依次并置而构成的字符串X。简称此路的标记为X。⑷一个FA可以有多于1个的终止状态。2009-7-262303.2有穷状态自动机接受语言{X000|X∈{0,1}*}∪{X001|X∈{0,1}*}的FA2009-7-262313.2有穷状态自动机即时描述(INSTANTANEOUSDESCRIPTION，ID）–X,Y∈∑*,Δ(Q0,X)=Q,XQY称为M的一个即时描述,表示XY是M正在处理的一个字符串,X引导M从Q0启动并到达状态Q,M当前正注视着Y的首字符。–如果XQAY是M的一个即时描述,且Δ(Q,A)=P，则XQAY├MXAPY。2009-7-262323.2有穷状态自动机Α├MNΒ,表示M从即时描述Α经过N次移动到达即时描述Β。M存在即时描述Α1,Α2,……,ΑN-1，使得Α├MΑ1,Α1├MΑ2,…,ΑN-1├MΒ当N=0时，有Α=Β。即Α├M0Α。Α├M+Β：表示M从即时描述Α经过至少1次移动到达即时描述Β。Α├M*Β,表示M从即时描述Α经过若干步移动到达即时描述Β。2009-7-262333.2有穷状态自动机当意义清楚时，我们将符号├M,├MN、├M*,├M+中的M省去，分别用├,├N、├*,├+表示。2009-7-262343.2有穷状态自动机对下图所示的DFA有如下的ID转换：2009-7-262353.2有穷状态自动机Q01010010001├1Q0010010001├10Q110010001├101Q00010001├1010Q1010001├10100Q210001├101001Q00001├1010010Q1001├10100100Q2012009-7-262363.2有穷状态自动机├101001000Q31├1010010001Q0即Q01010010001├101010010001Q0Q01010010001├+1010010001Q0Q01010010001├*1010010001Q02009-7-262373.2有穷状态自动机对于X∈∑*,Q0X1├+X1Q0Q0X10├+X10Q1Q0X100├+X100Q2Q0X000├+X000Q32009-7-262383.2有穷状态自动机能引导FA从开始状态到达Q的字符串的集合为：SET(Q)={X|X∈∑*,Δ(Q0,X)=Q}对图3-3所给的DFA中的所有Q，求SET(Q)。2009-7-26239SET(Q0)={X|X∈∑*,X=Ε或者X以1结尾}SET(Q1)={X|X∈∑*,X=0或者X以10结尾}SET(Q2)={X|X∈∑*,X=00或者X以100结尾}SET(Q3)={X|X∈∑*,X以000结尾}SET(Q4)={X|X∈∑*,X以001结尾}这5个集合是两两互不相交。2009-7-262403.2有穷状态自动机对于任意一个FAM=(Q,∑,Δ,Q0,F)我们可以按照如下方式定义关系RM：对?X,Y∈∑*,XRMYQ∈Q,使得X∈SET(Q)和Y∈SET(Q)同时成立。按照这个定义所得到的关系实际上是∑*上的一个等价关系。利用这个关系，可以将∑*划分成不多于|Q|个等价类。2009-7-262413.2有穷状态自动机例3-4构造一个DFA，它接受的语言为{0N1M2K|N,M,K?1}。Q0——M的启动状态；Q1——M读到至少一个0,并等待读更多的0；Q2——M读到至少一个0后,读到了至少一个1,并等待读更多的1；Q3——M读到至少一个0后跟至少一个1后，并且接着读到了至少一个2。2009-7-262423.2有穷状态自动机先设计“主体框架”再补充细节2009-7-262433.2有穷状态自动机⑴当FA一旦进入状态QT，它就无法离开此状态。所以,QT相当于一个陷阱状态(TRAP)。一般地，我们将陷阱状态用作在其他状态下发现输入串不可能是该FA所识别的语言的句子时进入的状态。在此状态下,FA读完输入串中剩余的字符。2009-7-262443.2有穷状态自动机⑵在构造一个识别给定语言的FA时，用画图的方式比较方便、直观。我们可以先根据语言的主要特征画出该FA的,主体框架,,然后再去考虑画出一些细节要求的内容。2009-7-262453.2有穷状态自动机⑶FA的状态具有一定的记忆功能：不同的状态对应于不同的情况，由于FA只有有穷个状态，所以，在识别一个语言的过程中，如果有无穷种情况需要记忆，我们肯定是无法构造出相应的FA的。2009-7-262463.2有穷状态自动机例3-5构造一个DFA，它接受的语言为{X|X∈{0,1}*，且当把X看成二进制数时,X模3与0同余}。Q0——对应除以3余数为0的X组成的等价类；Q1——对应除以3余数为1的X组成的等价类；Q2——对应除以3余数为2的X组成的等价类；QS——M的开始状态。2009-7-262473.2有穷状态自动机QS——在此状态下读入0时，有X=0，所以应该进入状态Q0；读入1时，有X=1，所以应该进入状态Q1。即,Δ(QS,0)=Q0；Δ(QS，1)=Q1。2009-7-262483.2有穷状态自动机Q0——能引导M到达此状态的X除以3余0，所以有,X=3*N+0。读入0时,引导M到达下一个状态的字符串为X0,X0=2*(3*N+0)=3*2*N+0。所以,Δ(Q0,0)=Q0；读入1时,M到达下一个状态的字符串为X1，X1=2*(3*N+0)+1=3*2*N+1。所以,Δ(Q0，1)=Q1；2009-7-262493.2有穷状态自动机Q1——能引导M到达此状态的X除以3余1，所以有,X=3*N+1。读入0时,引导M到达下一个状态的字符串为X0,X0=2*(3*N+1)=3*2*N+2。所以即：Δ(Q1,0)=Q2；读入1时，引导M到达下一个状态的字符串为X1，X1=2*(3*N+1)+1=3*2*N+2+1=3*(2*N+1)。所以Δ(Q1,1)=Q02009-7-262503.2有穷状态自动机Q2——能引导M到达此状态的X除以3余2,所以：X=3*N+2。读入0时,引导M到达下一个状态的字符串为X0，X0=2*(3*N+2)=3*2*N+4=3*(2*N+1)+1。所以Δ(Q2，0)=Q1；读入1时，引导M到达下一个状态的字符串为X1，X1=2*(3*N+2)+1=3*2*N+4+1=3*(2*N+1)+2。所以，Δ(Q2,1)=Q2。2009-7-262513.2有穷状态自动机接受语言{X|X∈{0,1}*，且当把X看成二进制数时,X模3与0同余}的DFA如下：2009-7-262523.2有穷状态自动机例3-6构造一个DFA，它接受的语言L={X|X∈{0,1}*，且对X中任意一个长度不大于5的子串A1A2…AN，A1+A2+…+AN?3,N?5}。输入串为A1A2…AI…AI+4AI+5…AM2009-7-262533.2有穷状态自动机当I=1,2,3，也就是M读到输入串的第1、2,3个字符时，它需要将这些字符记下来。因为A1……AI可能需要用来判定输入串的最初4~5个字符组成的子串是否满足语言的要求。当I=4,5，也就是M读到输入串的第4,5个字符时，在A1+A2+……+AI?3的情况下,M需要将A1……AI记下来；在A1+A2+……+AI>3时,M应该进入陷阱状态QT。2009-7-262543.2有穷状态自动机当I=6，也就是M读到输入串的第6个字符，此时，以前读到的第1个字符A1就没有用了，此时它要看A2+A3+…+A6?3是否成立，如果成立,M需要将A2…A6记下来；在A2+A3+…+AI>3时,M应该进入陷阱状态QT。2009-7-262553.2有穷状态自动机当M完成对子串A1A2…AI…AI+4的考察，并发现它满足语言的要求时,M记下来的是AI…AI+4，此时它读入输入串的第I+5个字符AI+5，以前读到的第I个字符AI就没有用了，此时它要看AI+1+AI+2+…+AI+5?3是否成立，如果成立,M需要将AI+1,AI+2,…,AI+5记下来；在AI+1+AI+2+…+AI+5>3时,M应该进入陷阱状态QT。2009-7-262563.2有穷状态自动机M需要记忆的内容有：什么都未读入——20=1种；记录有1个字符——21=2种；记录有2个字符——22=4种；记录有3个字符——23=8种；记录有4个字符——24-1=15种；记录有5个字符——25-6=26种；记录当前的输入串不是句子——1种。2009-7-262573.2有穷状态自动机状态设置Q[Ε]——M还未读入任何字符；QT——陷阱状态；Q[A1A2…AI]——M记录有I个字符,1?I?5。A1，A2,…,AI∈{0,1}。取DFAM=(Q,{0,1},Δ,Q[Ε],F)F={Q[Ε]}∪{Q[A1A2…AI]|A1,A2,…,AI∈{0,1}且1?I?5且A1+A2+…+AI?3}Q={QT}∪F2009-7-262583.2有穷状态自动机Δ(Q[Ε],A1)=Q[A1]Δ(Q[A1],A2)=Q[A1A2]Δ(Q[A1A2],A3)=Q[A1A2A3]Q[A1A2A3A]如果A1+A2+A3+A?3Δ(Q[A1A2A3],A)=QT如果A1+A2+A3+A>32009-7-262593.2有穷状态自动机Q[A1A2A3A4A]如果A1+A2+A3+A4+A?3Δ(Q[A1A2A3A4],A)=QT如果A1+A2+A3+A4+A>3Q[A2A3A4A5A]A2+A3+A4+A5+A?3Δ(Q[A1A2A3A4A5],A)=QT如果A2+A3+A4+A5+A>3Δ(QT,A1)=QT2009-7-262603.3NFA3.3.1作为对DFA的修改希望是接受{X|X∈{0,1}*，且X含有子串00或11}的FA如下：2009-7-262613.3.1作为对DFA的修改希望是接受{X|X∈{0,1}*，且X的倒数第10个字符为1}的FA如下,2009-7-262623.3.1作为对DFA的修改这两个图所给的,FA”与前面我们所定义的FA,即DFA,的区别在于：⑴并不是对于所有的(Q,A)∈∑×Q,Δ(Q，A)都有一个状态与它对应；⑵并不是对于所有的(Q,A)∈∑×Q,Δ(Q，A)只对应一个状态。,FA”在任意时刻可以处于有穷多个状态。,FA”具有,智能,。2009-7-262633.3.2NFA的形式定义不确定的有穷状态自动机(NON-DETERMINISTICFINITEAUTOMATON,NFA)M是一个五元组M=(Q,∑,Δ,Q0,F)–Q,∑,Q0,F的意义同DFA。–Δ,Q×∑?2Q,对?(Q,A)∈Q×∑,Δ(Q,A)={P1,P2,…,PM}表示M在状态Q读入字符A,可以选择地将状态变成P1,或者P2,…,或者PM,并将读头向右移动一个带方格而指向输入字符串的下一个字符。2009-7-262643.3.2NFA的形式定义FA的状态转移图,FA的状态对应的等价类、FA的即时描述对NFA都有效。接受{X|X∈{0,1}*，且X含有子串00或11}的FA对应的移动函数定义表。2009-7-262653.3.2NFA的形式定义状态说明状态输入字符01启动状态Q0{Q0,Q1}{Q0,Q2}Q1{Q3}ΦQ2Φ{Q3}终止状态Q3{Q3}{Q3}2009-7-262663.3.2NFA的形式定义接受{X|X∈{0,1}*，且X的倒数第10个字符为1}的FA对应的移动函数定义表。2009-7-262673.3.2NFA的形式定义状态说明状态输入字符01启动状态Q0{Q0}{Q0,Q1}Q1{Q2}{Q2}Q2{Q3}{Q3}Q3{Q4}{Q4}Q4{Q5}{Q5}Q5{Q6}{Q6}Q6{Q7}{Q7}Q7{Q8}{Q8}Q8{Q9}{Q9}Q9{Q10}{Q10}终止状态Q10ΦΦ2009-7-262683.3.2NFA的形式定义将Δ扩充为QQ2:?*对任意的Q∈Q,W∈∑*,A∈∑,定义A)}，Δ(R∈P,使得W)，(Q∈$R|{P),(?)2(),(?)1(WAQQQ2009-7-262693.3.2NFA的形式定义A)(Q,A)}(Q,P|{PA)}Δ(R,∈P},{|{PA)}Δ(R,∈PΕ),(Q,∈R|{P),(),(QRAQAQ和关于DFA的结论一样，两值相同，也不用区分这两个符号。2009-7-262703.3.2NFA的形式定义进一步扩充Δ的定义域,Δ,2Q×∑*?2Q。对任意的P?Q,W∈∑*PQWQWP),(),(2009-7-262713.3.2NFA的形式定义由于，对?(Q,W)∈Q×∑*),(),()},({}{WQWQWQQQ所以，不一定严格地区分Δ的第1个分量是一个状态还是一个含有一个元素的集合。2009-7-262723.3.2NFA的形式定义对任意的Q∈Q,W∈∑*,A∈∑,Δ(Q,WA)=Δ(Δ(Q,W),A)对输入字符串A1A2…ANΔ(Q,A1A2…AN)=Δ((…Δ(Δ(Q,A1),A2),…),AN)。2009-7-262733.3.2NFA的形式定义M接受(识别)的语言–对于?X∈∑*,如果Δ(Q0,W)∩F≠Φ，则称X被M接受,如果Δ(Q0,W)∩F=Φ，则称M不接受X。–L(M)={X|X∈∑*且Δ(Q0,W)∩F≠Φ}，称为由M接受(识别)的语言。2009-7-262743.3.3NFA与DFA等价对于一个输入字符,NFA与DFA的差异是前者可以进入若干个状态，而后者只能进入一个惟一的状态。虽然从DFA看待问题的角度来说,NFA在某一时刻同时进入若干个状态，但是，这若干个状态合在一起的,总效果,相当于它处于这些状态对应的一个,综合状态,。因此，我们考虑让DFA用一个状态去对应NFA的一组状态。2009-7-262753.3.3NFA与DFA等价NFAM1=(Q,∑,Δ1,Q0,F1)与DFAM2=(Q2,∑,Δ2,Q0′,F2)的对应关系：–NFA从开始状态Q0启动，我们就让相应的DFA从状态[Q0]启动。所以Q0′=[Q0]。–对于NFA的一个状态组{Q1,Q2,…,QN}，如果NFA在此状态组时读入字符A后可以进入状态组{P1,P2,…,PM},则让相应的DFA在状态[Q1,Q2,…,QN]读入字符A时，进入状态[P1，P2,…,PM]。2009-7-262763.3.3NFA与DFA等价定理3-1NFA与DFA等价。证明：(1)构造与M1等价的DFAM2。M1=(Q,∑,Δ1,Q0,F1)M2=(Q2,∑,Δ2,[Q0],F2)Q2=2QF2={[P1,P2,…,PM]|{P1,P2,…,PM}?Q&{P1，P2,…,PM}∩F1≠Φ}2009-7-262773.3.3NFA与DFA等价Δ2([Q1,Q2,…,QN],A)=[P1,P2,…,PM]Δ1({Q1,Q2,…,QN},A)={P1,P2,…,PM}(2)证明Δ1(Q0,X)={P1,P2,…,PM}Δ2([Q0],X)=[P1,P2,…,PM]。设X∈∑*，施归纳于|X|X=Ε,Δ1(Q0,Ε)={Q0},Δ2([Q0],Ε)=[Q0]2009-7-262783.3.3NFA与DFA等价设当|X|=N是结论成立。下面证明当|X|=N+1是结论也成立。不妨设X=WA,|W|=N,A∈∑Δ1(Q0,WA)=Δ1(Δ1(Q0,W),A)=Δ1({Q1,Q2,…,QN},A)={P1,P2,…,PM}由归纳假设,Δ1(Q0,W)={Q1,Q2,…,QN}?Δ2([Q0]，W)=[Q1,Q2,…,QN]2009-7-262793.3.3NFA与DFA等价根据Δ2的定义，Δ2([Q1,Q2,…,QN],A)=[P1,P2,…,PM]Δ1({Q1,Q2,…,QN},A)={P1,P2,…,PM}所以,Δ2([Q0],WA)=Δ2(Δ2([Q0],W),A)=Δ2([Q1,Q2,…,QN],A)=[P1,P2,…,PM]2009-7-262803.3.3NFA与DFA等价故,如果Δ1(Q0,WA)={P1,P2,…,PM}则必有Δ2([Q0],WA)=[P1,P2,…,PM]。由上述推导可知,反向的推导也成立。这就是说,结论对|X|=N+1也成立。由归纳法原理，结论对?X∈∑*成立。2009-7-262813.3.3NFA与DFA等价(3)证明L(M1)=L(M2)设X∈L(M1),且Δ1(Q0,X)={P1,P2,…,PM}，从而Δ1(Q0,X)∩F1≠Φ,这就是说,{P1,P2,…,PM}∩F1≠Φ，由F2的定义,[P1,P2,…,PM]∈F2。2009-7-262823.3.3NFA与DFA等价再由(2)知,Δ2([Q0],X)=[P1,P2,…,PM]所以,X∈L(M2)。故L(M1)?L(M2)。反过来推,可得L(M2)?L(M1)。从而L(M1)=L(M2)得证。综上所述，定理成立。2009-7-26283例3-7图3-9所示的NFA对应的DFA的状态转移函数如表3-7所示。图3-92009-7-26284表3-7状态转移函数状态说明状态输入字符01启动?[Q0][Q0,Q1][Q0,Q2][Q1][Q3][Φ][Q2][Φ][Q3]终止[Q3][Q3][Q3][Q0,Q1][Q0,Q1,Q3][Q0,Q2][Q0,Q2][Q0,Q1][Q0,Q2,Q3]终止[Q0,Q3][Q0,Q1,Q3][Q0,Q2,Q3][Q1,Q2][Q3][Q3]终止[Q1,Q3][Q3][Q3]终止[Q2,Q3][Q3][Q3][Q0,Q1,Q2][Q0,Q1,Q3][Q0,Q2,Q3]终止?[Q0,Q1,Q3][Q0,Q1,Q3][Q0,Q2,Q3]终止?[Q0,Q2,Q3][Q0,Q1,Q3][Q0,Q2,Q3]终止[Q1,Q2,Q3][Q3][Q3]终止[Q0,Q1,Q2,Q3][Q0,Q1,Q3][Q0,Q2,Q3][Φ][Φ][Φ]2009-7-262853.3.3NFA与DFA等价不可达状态(INACCESSIBLESTATE),不存在从[Q0]对应的顶点出发，到达该状态对应的顶点的路。我们称此状态从开始状态是不可达的。表3-7中，所有标记,?”的状态是从开始状态可达的，其他是不可达的——无用的。2009-7-262863.3.3NFA与DFA等价构造给定NFA等价的DFA策略–先只把开始状态[Q0]填入表的状态列中，如果表中所列的状态列有未处理的，则任选一个未处理的状态[Q1,Q2,…,QN]，对∑中的每个字符A，计算Δ([Q1,Q2,…,QN],A)，并填入相应的表项中，如果Δ([Q1,Q2,…,QN],A)在表的状态列未出现过，则将它填入表的状态列。如此重复下去，直到表的状态列中不存在未处理的状态。2009-7-262873.3.3NFA与DFA等价图3-11图3-9所示NFA的等价DFA2009-7-262883.4带空移动的有穷状态自动机接受语言{0N1M2K|N,M,K≥0}的NFA2009-7-262893.4带空移动的有穷状态自动机接受语言{0N1M2K|N,M,K≥0}的NFA是否可以构造成下图所示的,Ε-NFA”？其构造显然比图1-13所示的NFA更容易。当然还希望它们是等价的。2009-7-262903.4带空移动的有穷状态自动机带空移动的不确定的有穷状态自动机(NON-DETERMINISTICFINITEAUTOMATONWITHΕ-MOVES,Ε-NFA)M=(Q,∑,Δ,Q0,F),Q,∑,Q0,F的意义同DFA。Δ,Q×(∑∪{Ε})?2Q2009-7-262913.4带空移动的有穷状态自动机非空移动–?(Q,A)∈Q×∑–Δ(Q,A)={P1,P2,…,PM}–表示M在状态Q读入字符A，可以选择地将状态变成P1,P2,…或者PM,并将读头向右移动一个带方格而指向输入字符串的下一个字符。2009-7-262923.4带空移动的有穷状态自动机空移动–?Q∈Q–Δ(Q,Ε)={P1,P2,…,PM}–表示M在状态Q不读入任何字符，可以选择地将状态变成P1,P2,…或者PM。也可以叫做M在状态Q做一个空移动(又可以称为Ε移动)，并且选择地将状态变成P1、P2,…或者PM。2009-7-262933.4带空移动的有穷状态自动机进一步扩充Δ的定义域,Δ,2Q×∑*?2Q。对任意的P?Q,W∈∑*。对任意的Q∈Q,W∈∑*,A∈∑。⑴Ε-CLOSURE(Q)={P|从Q到P有一条标记为Ε的路}。PPPCLOSUREPCLOSURE)()()2(2009-7-262943.4带空移动的有穷状态自动机)(),(?)3(QCLOSUREQ),(),()},(),(|{)(),()4(WRRARARPWQRPPPCLOSUREWAQ使得2009-7-262953.4带空移动的有穷状态自动机进一步扩展移动函数,2Q×∑?2Q。对任意(P,A)∈2Q×∑。PQAQAP),(),()5(PQWQWP),(?),(?)6(2009-7-262963.4带空移动的有穷状态自动机在Ε-NFA中，对任意A∈∑,Q∈Q，),(),(?AQAQ需要严格区分。2009-7-26297图3-14所示Ε-NFA状态ΔΕ012Ε012Q0{Q1}{Q0}ΦΦ{Q0,Q1,Q2}{Q0,Q1,Q2}{Q1,Q2}{Q2}Q1{Q2}Φ{Q1}Φ{Q1,Q2}Φ{Q1,Q2}{Q2}Q2ΦΦΦ{Q2}{Q2}ΦΦ{Q2}2009-7-262983.4带空移动的有穷状态自动机M接受(识别)的语言对于?X∈∑*,仅当FXQ?),(?0?时，称X被M接受。}),(?|{)(0*FXQXXML并且2009-7-262993.4带空移动的有穷状态自动机定理3-2Ε-NFA与NFA等价。证明：设有Ε-NFAM1=(Q,∑,Δ1,Q0，F)(1)构造与之等价的NFAM2。取NFAM2=(Q,∑,Δ2,Q0,F2)F∪{Q0}如果F∩Ε-CLOSURE(Q0)≠ΦF2=F如果F∩Ε-CLOSURE(Q0)=Φ),(?),(12AQAQ2009-7-263003.4带空移动的有穷状态自动机(2)施归纳于|X|，证明对?X∈∑+。),(?),(12XQXQΔ2(Q0,X)=Δ2(Q0,WA)=Δ2(Δ2(Q0,W),A)=Δ2((Q0,W),A)2009-7-263013.4带空移动的有穷状态自动机),(),(),(),,(|({)),((),(),(0101101),(1),(1),(2010101XQWAQAQPWQQPCLOSUREAQCLOSUREAQAQWQQWQQWQQ2009-7-263023.4带空移动的有穷状态自动机(3)证明,对?X∈∑+,Δ2(Q0,X)∩F2≠Φ的充分必要条件是FXQ?),(?1?⑷证明Ε∈L(M1)?Ε∈L(M2)。2009-7-263033.4带空移动的有穷状态自动机例3-4求与图3-14所示Ε-NFA等价的NFA。2009-7-263043.5FA是正则语言的识别器3.5.1FA与右线性文法DFAM=(Q,∑,Δ,Q0,F)，处理句子A1A2…AN的特性。⑴M按照句子A1A2…AN中字符的出现顺序，从开始状态Q0开始，依次处理字符A1、A2,…,AN，在这个处理过程中，每处理一的字符进入一个状态，最后停止在某个终止状态。2009-7-263053.5.1FA与右线性文法⑵它每次处理且仅处理一个字符：第I步处理输入字符AI。⑶对应于使用Δ(Q,A)=P的状态转移函数的处理,相当于是在状态Q完成对A的处理,然后由P接下去实现对后续字符的处理。⑷当Δ(Q,A)=P∈F，且A是输入串的最后一个字符时,M完成对此输入串的处理。2009-7-263063.5.1FA与右线性文法A0?A1A1对应产生式A0?A1A1A1A2A2对应产生式A1?A2A2…A1A2…AN-1AN-1对应产生式AN-2?AN-1AN-1A1A2…AN-1AN对应产生式AN-1?AN2009-7-263073.5.1FA与右线性文法Q0A1A2…AN-1AN├A1Q1A2…AN-1AN对应Δ(Q0,A1)=Q1├A1A2Q2…AN-1AN对应Δ(Q1,A2)=Q2……├A1A2…AN-1QN-1AN对应Δ(QN-2,AN-1)=QN-1├A1A2…AN-1ANQN对应Δ(QN-1,AN)=QN2009-7-263083.5.1FA与右线性文法其中QN为M的终止状态。考虑根据A1、A2,…,AN，让A0与Q0对应,A1与Q1对应、A2与Q2对应,…,AN-2与QN-2对应,AN-1与QN-1对应。这样，就有希望得到满足定理2-4-1的正则文法的推导与DFA的互相模拟的方式。2009-7-263093.5.1FA与右线性文法定理3-3FA接受的语言是正则语言。证明：(1)构造。基本思想是让RG的派生对应DFA的移动。设DFAM=(Q,∑,Δ,Q0,F)，取右线性文法G=(Q,∑,P,Q0)，P={Q?AP|Δ(Q,A)=P}∪{Q?A|Δ(Q,A)=P∈F}2009-7-263103.5.1FA与右线性文法（2）证明L(G)=L(M)-{Ε}。对于A1A2…AN-1AN∈∑+，Q0?+A1A2…AN-1ANQ0?A1Q1,Q1?A2Q2,…,QN-2?AN-1QN-1,QN-1?AN∈PΔ(Q0,A1)=Q1,Δ(Q1,A2)=Q2,…,Δ(QN-2,AN-1)=QN-1,Δ(QN-1,AN)=QN,且QN∈FΔ(Q0,A1A2…AN-1AN)=QN∈FA1A2…AN-1AN∈L(M)2009-7-263113.5.1FA与右线性文法（3）关于Ε句子。如果Q0?F,则Ε?L(M),L(G)=L(M)。如果Q0∈F,则由定理2-6和定理2-7,存在正则文法G′,使得L(G′)=L(G)∪{Ε}=L(M)。综上所述，对于任意DFAM，存在正则文法G，使得L(G)=L(M)。定理得证。2009-7-263123.5.1FA与右线性文法例3-9与图3-8所给DFA等价的正则文法QS?0|0Q0|1Q1Q0?0|0Q0|1Q1Q1?0Q2|1|1Q0Q2?0Q1|1Q22009-7-263133.5.1FA与右线性文法与图3-7所给的DFA等价的正则文法Q0?0Q1|1QT|2QTQ1?0Q1|1Q2|2QTQ2?0QT|1Q2|2Q3|2Q3?0QT|1QT|2Q3|2QT?0QT|1QT|2QT2009-7-263143.5.1FA与右线性文法定理3-4正则语言可以由FA接受。证明：（1）构造。基本思想：让FA模拟RG的派生。设G=(V,T,P,S),且Ε?L(G)，取FAM=(V∪{Z},T,Δ,S,{Z}),Z?V。2009-7-263153.5.1FA与右线性文法对?(A,A)∈T×V{B|A?AB∈P}∪{Z}如果A?A∈PΔ(A,A)={B|A?AB∈P}如果A?A?P用B∈Δ(A,A)与产生式A?AB对应用Z∈Δ(A,A)与产生式A?A对应。2009-7-263163.5.1FA与右线性文法（2）证明L(M)=L(G)对于A1A2…AN-1AN∈T+，A1A2…AN-1AN∈L(G)?S?+A1A2…AN-1ANS?A1A1?A1A2A2?…A1A2…AN-1AN-1?A1A2…AN-1ANS?A1A1,A1?A2A2,…,AN-2?AN-1AN-1,AN-1?AN∈P2009-7-263173.5.1FA与右线性文法A1∈Δ(S,A1),A2∈Δ(A1,A2),…,AN-1∈Δ(AN-2,AN-1),Z∈Δ(AN-1,AN)Z∈Δ(S,A1A2…AN-1AN)A1A2…AN-1AN∈L(M)对于Ε，按照定理2-5和定理2-6处理。2009-7-263183.5.1FA与右线性文法例3-10构造与所给正则文法等价的FA：G1,E?0A|1BA?1|1CB?0|0CC?0B|1A2009-7-263193.5.1FA与右线性文法Δ(E,0)={A}对应E?0AΔ(E,1)={B}对应E?1BΔ(A,1)={Z,C}对应A?1|1CΔ(B,0)={Z,C}对应B?0|0CΔ(C,0)={B}对应C?0BΔ(C,1)={A}对应C?1A2009-7-263203.5.1FA与右线性文法2009-7-263213.5.1FA与右线性文法推论3-1FA与正则文法等价。证明：根据定理3-3和定理3-4即可得到。2009-7-263223.5.1FA与左线性文法按照推导来说，句子A1A2…AN-1AN中的字符被推导出的先后顺序正好与它们在句子中出现的顺序相反；而按照归约来看，它们被归约成语法变量的顺序则正好与它们在句子中出现的顺序相同,A1,A2,…,AN-1，AN。可见，归约过程与FA处理句子字符的顺序是一致的，所以可考虑依照,归约,来研究FA的构造。2009-7-263233.5.1FA与左线性文法对于形如A?A的产生式：在推导中，一旦使用了这样的产生式，句型就变成了句子，而且A是该句子的第一个字符；按,归约,理解，对句子的第1个字符，根据形如A?A的产生式进行归约。对应到FA中,FA从开始状态出发，读到句子的第一个字符A，应将它,归约,为A。我们如果考虑用语法变量对应FA的状态，那么，此时我们需要引入一个开始状态，比如说,Z。这样，对应形如A?A的产生式，可以定义A∈Δ(Z,A)。2009-7-263243.5.1FA与左线性文法按照上面的分析，对应于形如A?BA的产生式,FA应该在状态B读入A时，将状态转换到A。也可以理解为：在状态B,FA已经将当前句子的、处理过的前缀,归约,成了B，在此时它读入A时，要将BA归约成A，因此，它进入状态A。2009-7-263253.5.1FA与左线性文法按照,归约,的说法，如果一个句子是文法G产生的语言的合法句子，它最终应该被归约成文法G的开始符号。所以,G的开始符号对应的状态就是相应的FA的终止状态。如何解决好开始符号只有一个，而DFA的终止状态可以有多个的问题。2009-7-263263.5.1FA与左线性文法例如：对文法G2,E?A0|B1A?1|C1B?0|C0C?B0|A1对应Δ(A,0)={E}Δ(B,1)={E}Δ(Z,1)={A}Δ(C，1)={A}Δ(Z,0)={B}Δ(C,0)={B}Δ(B,0)={C}Δ(A,1)={C}2009-7-263273.5.1FA与左线性文法G2,E?A0|B1A?1|C1B?0|C0C?B0|A12009-7-263283.5.1FA与左线性文法DFA(的状态转移图)作如下,预处理,,⑴删除DFA的陷阱状态(包括与之相关的弧)；⑵在图中加一个识别状态；⑶,复制,一条原来到达终止状态的弧,使它从原来的起点出发,到达新添加的识别状态。2009-7-263293.5.1FA与左线性文法⑴如果Δ(A,A)=B,则有产生式B?AA；⑵如果Δ(A,A)=B，且A是开始状态，则有产生式B?A。定理3-5左线性文法与FA等价。2009-7-263303.6FA的一些变形3.6.1双向有穷状态自动机确定的双向有穷状态自动机(TWO-WAYDETERMINISTICFINITEAUTOMATON,2DFA)M=(Q,∑,Δ,Q0,F)Q,∑,Q0,F的意义同DFA。2009-7-263313.6.1双向有穷状态自动机Δ,Q×∑?Q×{L,R,S}，对?(Q,A)∈Q×∑–如果Δ(Q,A)={P,L}，它表示M在状态Q读入字符A，将状态变成P，并将读头向左移动一个带方格而指向输入字符串的前一个字符。–如果Δ(Q,A)={P,R}，它表示M在状态Q读入字符A，将状态变成P，并将读头向右移动一个带方格而指向输入字符串中下一个字符。–如果Δ(Q,A)={P,S}，它表示M在状态Q读入字符A，将状态变成P，读头保持在原位不动。2009-7-263323.6.1双向有穷状态自动机M接受的语言L(M)={X|Q0X├*XP且P∈F}是2DFA接受的语言。定理3-62DFA与FA等价。2009-7-263333.6.1双向有穷状态自动机不确定的双向有穷状态自动机(TWO-WAYNONDETERMINISTICFINITEAUTOMATON，2NFA)M=(Q,∑,Δ,Q0,F)Q,∑,Q0,F的意义同DFA。Δ,Q×∑?2Q×{L,R,S}。2009-7-263343.6.1双向有穷状态自动机Δ(Q,A)={(P1,D1)(P2,D2)…,(PM,DM)}表示M在状态Q读入字符A，可以选择地将状态变成P1同时按D1实现对读头的移动、或者将状态变成P2同时按D2实现对读头的移动,……或者将状态变成PM同时按DM实现对读头的移动。其中D1,D2,…,DM∈{L,R,S}，表示的意义与2DFA的定义表示的意义相同。2009-7-263353.6.1双向有穷状态自动机定理3-72NFA与FA等价。2009-7-263363.6.2带输出的FAMOORE机M=(Q,∑,Δ,Δ,Λ,Q0)Q,∑,Q0,Δ的意义同DFA。Δ——输出字母表(OUTPUTALPHABET)。Λ,Q?Δ为输出函数。对?Q∈Q,Λ(Q)=A表示M在状态Q时输出A。2009-7-263373.6.2带输出的FA对于?A1A2…AN-1AN∈∑*,如果Δ(Q0,A1)=Q1,Δ(Q1,A2)=Q2,…,Δ(QN-2，AN-1)=QN-1,Δ(QN-1,AN)=QN，则M的输出为Λ(Q0,A1)Λ(Q1,A2)…Λ(QN-1,AN)2009-7-263383.6.2带输出的FAMEALY机M=(Q,∑,Δ,Δ,Λ,Q0)Δ——输出字母表。Λ,Q×∑?Δ为输出函数。对?(Q，A)∈Q×∑,Λ(Q,A)=D表示M在状态Q读入字符A时输出D。2009-7-263393.6.2带输出的FA对于?A1A2…AN-1AN∈∑*,M的输出串为：Λ(Q0,A1)Λ(Δ(Q0,A1),A2)…Λ((…Δ(Δ(Q0，A1),A2)…),AN)设Δ(Q0,A1)=Q1,Δ(Q1,A2)=Q2,…,Δ(QN-2，AN-1)=QN-1,Δ(QN-1,AN)=QN，则M的输出可以表示成：Λ(Q0,A1)Λ(Q1,A2)…Λ(QN-1,AN)2009-7-263403.6.2带输出的FAMOORE机处理该串时每经过一个状态,就输出一个字符：输出字符和状态一一对应；MEALY机处理该串时的每一个移动输出一个字符：输出字符和移动一一对应。2009-7-263413.6.2带输出的FA如果对于?X∈∑*,T1(X)=Λ1(Q0)T2(X),则MOORE机M1=(Q1,∑,Δ,Δ1,Λ1,Q01)与MEALY机M2=(Q2,∑,Δ,Δ2,Λ2，Q02),是等价的,其中,T1(X)和T2(X)分别表示M1和M2关于X的输出。定理3-8MOORE机与MEALY机等价。2009-7-263423.7小结本章讨论正则语言的识别器——FA。包括DFA,NFA,Ε-NFA。RG与FA的等价性。简单介绍带输出的FA和双向FA。⑴FAM是一个五元组,M=(Q,∑,Δ,Q0,F),它可以用状态转移图表示。⑵M接受的语言为{X|X∈∑*且Δ(Q，X)∈F}。如果L(M1)=L(M2),则称M1与M2等价。⑶FA的状态具有有穷的存储功能。这一特性可以用来构造接受一个给定语言的FA。2009-7-263433.7小结⑷NFA允许M在一个状态下读入一个字符时选择地进入某一个状态，对于?X∈∑*，如果Δ(Q0,X)∩F≠Φ，则称X被M接受，如果Δ(Q0,X)∩F=Φ，则称M不接受X。M接受的语言L(M)={X|X∈∑*且Δ(Q0,X)∩F≠Φ}。2009-7-263443.7小结⑸Ε-NFA是在NFA的基础上,允许直接根据当前状态变换到新的状态而不考虑输入带上的符号。对?Q∈Q,Δ(Q,Ε)={P1,P2,…,PM}表示M在状态Q不读入任何字符,可以选择地将状态变成P1,P2,…或者PM。这叫做M在状态Q做一个空移动。⑹NFA与DFA等价,Ε-NFA与NFA等价,统称它们为FA。2009-7-263453.7小结⑺根据需要,可以在FA中设置一种特殊的状态——陷阱状态。但是,不可达状态却是应该无条件地删除的。⑻FA是正则语言的识别模型。分别按照对推导和归约的模拟,可以证明FA和左线性文法,右线性文法等价。2009-7-263463.7小结⑼2DFA是FA的又一种变形,它不仅允许读头向前移动,还允许读头向后移动。通过这种扩充,2DFA仍然与FA等价。⑽MOORE机和MEALY机是两种等价的带输出的FA,MOORE机根据状态决定输出字符,MEALY机根据移动决定输出字符。2009-7-26347第4章正则表达式正则文法擅长语言的产生，有穷状态自动机擅长语言的识别。本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势，为正则语言的计算机处理提供了方便条件。–简洁、更接近语言的集合表示和语言的计算机表示等。2009-7-26348第4章正则表达式主要内容–典型RE的构造。–与RE等价FA的构造方法。–与DFA等价的RE的构造。重点–RE的概念。–RE与DFA的等价性。难点,RE与DFA的等价性证明。2009-7-263494.１启示产生语言{ANBMCK|N,M,K?1}∪{AICNBXAM|I?0,N?1,M?2,X为D和E组成的串}的正则文法为A?AA|AB|CEB?BB|BCC?CC|CE?CE|BFF?DF|EF|AHH?AH|A2009-7-263504.１启示接受此语言的NFAM2009-7-263514.１启示计算集合SET(Q)SET(A)={AN|N?0}={A}*SET(B)=SET(A){A}{BN|N?0}={ANABM|M,N?0}={A}*{A}{B}*={A}+{B}*SET(C)=SET(B){B}{C}*={A}*{A}{B}*{B}{C}*={A}+{B}+{C}*SET(D)=SET(C){C}={A}+{B}+{C}*{C}={A}+{B}+{C}+2009-7-263524.１启示SET(E)=SET(A){C}{C}*={A}*{C}{C}*={A}*{C}+SET(F)=SET(E){B}{D,E}*={A}*{C}+{B}{D,E}*SET(H)=SET(F){A}{A}*={A}*{C}+{D,E}*{A}{A}*={A}*{C}+{D,E}*{A}+SET(I)=SET(H){A}={A}*{C}+{D,E}*{A}+{A}L(M)=SET(D)∪SET(H)={A}+{B}+{C}+∪{A}*{C}+{D,E}*{A}+{A}2009-7-263534.１启示根据集合运算的定义,{D,E}={D}∪{E}。从而,{D,E}*=({D}∪{E})*。这样可以将L(M)写成如下形式：L(M)={A}+{B}+{C}+∪{A}*{C}+({D}∪{E})*{A}+{A}记作：A+B+C++A*C+(D+E)*A+A=AA*BB*CC*+A*CC*(D+E)*AAA*2009-7-263544.2RE的形式定义正则表达式(REGULAREXPRESSION,RE)⑴Φ是∑上的RE,它表示语言Φ；⑵Ε是∑上的RE,它表示语言{Ε}；⑶对于?A∈∑,A是∑上的RE,它表示语言{A}；2009-7-263554.2RE的形式定义⑷如果R和S分别是∑上表示语言R和S的RE,则：R与S的,和,(R+S)是∑上的RE,(R+S)表达的语言为R∪S；R与S的,乘积,(RS)是∑上的RE,(RS)表达的语言为RS；R的克林闭包(R*)是∑上的RE,(R*)表达的语言为R*。⑸只有满足⑴,⑵,⑶,⑷的才是∑上的RE。2009-7-263564.2RE的形式定义例4-1设∑={0,1}⑴0,表示语言{0}；⑵1,表示语言{1}；⑶(0+1),表示语言{0,1}；⑷(01),表示语言{01}；⑸((0+1)*),表示语言{0,1}*；⑹((00)((00)*)),表示语言{00}{00}*；2009-7-263574.2RE的形式定义⑺((((0+1)*)(0+1))((0+1)*)),表示语言{0,1}+；⑻((((0+1)*)000)((0+1)*)),表示{0,1}上的至少含有3个连续0的串组成的语言；⑼((((0+1)*)0)1),表示所有以01结尾的0,1字符串组成的语言；⑽(1(((0+1)*)0)),表示所有以1开头,并且以0结尾的0,1字符串组成的语言。2009-7-263584.2RE的形式定义约定⑴R的正闭包R+表示R与(R*)的乘积以及(R*)与R的乘积：R+=(R(R*))=((R*)R)⑵闭包运算的优先级最高，乘运算的优先级次之，加运算,+”的优先级最低。所以，在意义明确时，可以省略其中某些括号。((((0+1)*)000)((0+1)*))=(0+1)*000(0+1)*2009-7-263594.2RE的形式定义((((0+1)*)(0+1))((0+1)*))=(0+1)*(0+1)(0+1)*⑶在意义明确时,RER表示的语言记为L(R)，也可以直接地记为R。⑷加,乘,闭包运算均执行左结合规则。2009-7-263604.2RE的形式定义相等(EQUIVALENCE)–R,S是字母表∑上的一个RE，如果L(R)=L(S)，则称R与S相等,记作R=S。–相等也称为等价。几个基本结论⑴结合律,(RS)T=R(ST)(R+S)+T=R+(S+T)⑵分配律,R(S+T)=RS+RT(S+T)R=SR+TR2009-7-263614.2RE的形式定义⑶交换律,R+S=S+R。⑷幂等律,R+R=R。⑸加法运算零元素,R+Φ=R。⑹乘法运算单位元,RΕ=ΕR=R。⑺乘法运算零元素,RΦ=ΦR=Φ。⑻L(Φ)=Φ。⑼L(Ε)={Ε}。⑽L(A)={A}。2009-7-263624.2RE的形式定义⑾L(RS)=L(R)L(S)。⑿L(R+S)=L(R)∪L(S)。⒀L(R*)=(L(R))*。⒁L(Φ*)={Ε}。⒂L((R+Ε)*)=L(R*)。⒃L((R*)*)=L(R*)。⒄L((R*S*)*)=L((R+S)*)。⒅如果L(R)?L(S),则R+S=S。2009-7-263634.2RE的形式定义⒆L(RN)=(L(R))N。⒇RNRM=RN+M。一般地,R+Ε≠R,(RS)N≠RNSN,RS≠SR。幂R是字母表∑上的RE,R的N次幂定义为⑴R0=Ε。⑵RN=RN-1R。2009-7-263644.2RE的形式定义例4-2设∑={0,1}00表示语言{00}；(0+1)*00(0+1)*表示所有的至少含两个连续0的0,1串组成的语言；(0+1)*1(0+1)9表示所有的倒数第10个字符为1的串组成的语言；2009-7-263654.2RE的形式定义L((0+1)*011)={X|X是以011结尾的0,1串}；L(0+1+2+)={0N1M2K|M,N,K≥1}；L(0*1*2*)={0N1M2K|M,N,K≥0}；L(1(0+1)*1+0(0+1)*0))={X|X的开头字符与尾字符相同}。2009-7-263664.3RE与FA等价正则表达式R称为与FAM等价，如果L(R)=L(M)。从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给FA的各个状态Q对应的SET(Q)，并且最终得到相应的FA接受的语言的RE表示。寻找一种比较“机械”的方法，使得计算机系统能够自动完成FA与RE之间的转换。2009-7-263674.3.1RE到FA的等价变换0对应的FA01对应的FA2009-7-263684.3.1RE到FA的等价变换0+1对应的FA2009-7-263694.3.1RE到FA的等价变换0*对应的FA2009-7-263704.3.1RE到FA的等价变换定理4-1RE表示的语言是RL。证明：施归纳于正则表达式中所含的运算符的个数N，证明对于字母表∑上的任意正则表达式R，存在FAM，使得L(M)=L(R)。–M恰有一个终止状态。–M在终止状态下不作任何移动。2009-7-263714.3.1RE到FA的等价变换N=0R=ΕR=ΦR=A2009-7-263724.3.1RE到FA的等价变换设结论对于N=K时成立,此时有如下FA：M1=(Q1,∑,Δ1,Q01,{F1})M2=(Q2,∑,Δ2,Q02,{F2})L(M1)=L(R1),L(M2)=L(R2)。Q1∩Q2=Φ。N=K2009-7-263734.3.1RE到FA的等价变换N=K+1R=R1+R2取Q0,F?Q1∪Q2,令M=(Q1∪Q2∪{Q0,F},∑,Δ,Q0,{F})①Δ(Q0,Ε)={Q01,Q02}；②对?Q∈Q1,A∈∑∪{Ε},Δ(Q,A)=Δ1(Q,A);对?Q∈Q2,A∈∑∪{Ε},Δ(Q,A)=Δ2(Q,A)；③Δ(F1,Ε)={F}；④Δ(F2,Ε)={F}。2009-7-263744.3.1RE到FA的等价变换N=K+1R=R1+R22009-7-263754.3.1RE到FA的等价变换M=(Q1∪Q2,∑,Δ,Q01,{F2})①对?Q∈Q1-{F1},A∈∑∪{Ε}–Δ(Q,A)=Δ1(Q,A)；②对?Q∈Q2-{F2},A∈∑∪{Ε}–Δ(Q,A)=Δ2(Q,A)；③Δ(F1,Ε)={Q02}2009-7-263764.3.1RE到FA的等价变换R=R1R22009-7-263774.3.1RE到FA的等价变换M=(Q1∪{Q0,F},∑,Δ,Q0,{F})其中Q0,F?Q1,定义Δ为①对?Q∈Q1-{F1},A∈∑,Δ(Q,A)=Δ1(Q,A)。②Δ(F1,Ε)={Q01,F}。③Δ(Q0,Ε)={Q01,F}。2009-7-263784.3.1RE到FA的等价变换R=R1*2009-7-263794.3.1RE到FA的等价变换按照定理4-1证明给出的方法构造一个给定RE的等价FA时，该FA有可能含有许多的空移动。可以按照自己对给定RE的,理解,以及对FA的,理解,,直接地,构造出一个比较,简单,的FA。定理证明中所给的方法是机械的。由于,直接地,构造出的FA的正确性依赖于构造者的,理解,,所以它的正确性缺乏有力的保证。2009-7-263804.3.1RE到FA的等价变换例4-3构造与(0+1)*0+(00)*等价的FA。2009-7-263814.3.1RE到FA的等价变换按照对(0+1)*0+(00)*的,理解,,直接地,构造出的FA。2009-7-263824.3.2RL可以用RE表示计算DFA的每个状态对应的集合——字母表的克林闭包的等价分类，是具有启发意义的。这个计算过程难以,机械,地进行。计算Q1到Q2的一类串的集合,RKIJ。图上作业法。2009-7-263834.3.2RL可以用RE表示定理4-2RL可以用RE表示。设DFAM=({Q1,Q2,…,QN},∑,Δ,Q1,F)RKIJ={X|Δ(QI,X)=QJ而且对于X的任意前缀Y(Y≠X,Y≠Ε),如果Δ(QI,Y)=QL,则L?K}。2009-7-263844.3.2RL可以用RE表示R0IJ={A|Δ(QI,A)=QJ}如果I≠J{A|Δ(QI,A)=QJ}∪{Ε}如果I=JRKIJ=RK-1IK(RK-1KK)*RK-1KJRK-1IJFQNFFRML1)(2009-7-263854.3.2RL可以用RE表示图上作业法启示2009-7-263864.3.2RL可以用RE表示图上作业法操作步骤⑴预处理：①用标记为X和Y的状态将M“括起来,,在状态转移图中增加标记为X和Y的状态,从标记为X的状态到标记为Q0的状态引一条标记为Ε的弧；从标记为Q(Q∈F)的状态到标记为Y的状态分别引一条标记为Ε的弧。②去掉所有的不可达状态。2009-7-263874.3.2RL可以用RE表示⑵对通过步骤(1)处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为X和Y外的其他状态，并且这两个状态之间最多只有一条弧。并弧–将从Q到P的标记为R1,R2,…,RG并行弧用从Q到P的、标记为R1+R2+…+RG的弧取代这G个并行弧。2009-7-263884.3.2RL可以用RE表示去状态1–如果从Q到P有一条标记为R1的弧，从P到T有一条标记为R2的弧，不存在从状态P到状态P的弧，将状态P和与之关联的这两条弧去掉，用一条从Q到T的标记为R1R2的弧代替。去状态2–如果从Q到P有一条标记为R1的弧，从P到T有一条标记为R2的弧，从状态P到状态P标记为R3的弧，将状态P和与之关联的这三条弧去掉，用一条从Q到T的标记为R1R3*R2的弧代替。2009-7-263894.3.2RL可以用RE表示去状态3–如果图中只有三个状态，而且不存在从标记为X的状态到达标记为Y的状态的路，则将除标记为X的状态和标记为Y的状态之外的第3个状态及其相关的弧全部删除。2009-7-263904.3.2RL可以用RE表示⑶从标记为X的状态到标记为Y的状态的弧的标记为所求的正则表达式。如果此弧不存在，则所求的正则表达式为Φ。2009-7-263914.3.2RL可以用RE表示例4-4求图4-14所示的DFA等价的RE。2009-7-263924.3.2RL可以用RE表示预处理。2009-7-263934.3.2RL可以用RE表示去掉状态Q3。2009-7-263944.3.2RL可以用RE表示去掉状态Q4。2009-7-263954.3.2RL可以用RE表示合并从标记为Q2的状态到标记为Y的状态的两条并行弧。2009-7-263964.3.2RL可以用RE表示去掉状态Q0。2009-7-263974.3.2RL可以用RE表示并弧。2009-7-263984.3.2RL可以用RE表示去掉状态Q1。2009-7-263994.3.2RL可以用RE表示去掉状态Q2。1*0(11*0)*0((00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)就是所求。2009-7-264004.3.2RL可以用RE表示几点值得注意的问题⑴如果去状态的顺序不一样，则得到的RE可能在形式是不一样，但它们都是等价的。⑵当DFA的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。此时，相应的RE为Φ。⑶不计算自身到自身的弧，如果状态Q的入度为N，出度为M，则将状态Q及其相关的弧去掉之后，需要添加N*M条新弧。2009-7-264014.3.2RL可以用RE表示⑷对操作的步数施归纳，可以证明它的正确性。推论4-1正则表达式与FA、正则文法等价，是正则语言的表示模型。2009-7-264024.4正则语言等价模型的总结A?AB~B∈Δ(A,A)A?A~QF∈Δ(A，A)Δ(Q,A)=P~Q?APΔ(Q,A)=P∈F~Q?ARGGDFANFAREΕ-NFAΔDFA(P,A)=[ΔNFA(P,A)]ΔNFA(Q,A)=(Q,A)图上作业法归纳2009-7-264034.5小结本章讨论了RL及其与FA的等价性。⑴字母表∑上的RE用来表示∑上的RL。Φ、Ε,A（A∈∑），是∑上的最基本的RE，它们分别表示语言Φ,{Ε},{A}，以此为基础，如果R和S分别是∑上的表示语言R和S的RE，则R+S,RS,R*分别是∑上的表示语言R∪S,RS,R*的RE。如果L(R)=L(S)，则称R与S等价。2009-7-264044.5小结⑵RE对乘,加满足结合律；乘对加满足左,右分配律；加满足交换率和幂等率；Φ是加运算的零元素；Ε是乘运算的单位元；Φ是乘运算的零元素。⑶RE是RL的一种描述。容易根据RE构造出与它等价的FA。反过来，可以用图上作业法构造出与给定的DFA等价的RE。⑷RL的5种等价描述模型转换图。2009-7-26405第5章RL的性质RL性质–泵引理及其应用–并、乘积、闭包、补、交–正则代换、同态、逆同态的封闭性从RL固有特征寻求表示的一致性–MYHILL-NERODE定理–FA的极小化RL的几个判定问题–空否、有穷否、两个DFA等价否、成员关系2009-7-264065.1RL的泵引理泵引理(PUMPINGLEMMA)设L为一个RL,则存在仅依赖于L的正整数N,对于?Z∈L,如果|Z|≥N,则存在U,V、W,满足⑴Z=UVW；⑵|UV|≤N；⑶|V|≥1；⑷对于任意的整数I≥0,UVIW∈L；⑸N不大于接受L的最小DFAM的状态数。2009-7-264075.1RL的泵引理证明思想2009-7-264085.1RL的泵引理证明：DFA在处理一个足够长的句子的过程中,必定会重复地经过某一个状态。换句话说,在DFA的状态转移图中,必定存在一条含有回路的从启动状态到某个终止状态的路。由于是回路,所以,DFA可以根据实际需要沿着这个回路循环运行,相当于这个回路中弧上的标记构成的非空子串可以重复任意多次。2009-7-264095.1RL的泵引理M=(Q,∑,Δ,Q0,F)|Q|=NZ=A1A2…AMM≥NΔ(Q0,A1A2…AH)=QH状态序列Q0,Q1,…,QN中,至少有两个状态是相同,QK=QJ2009-7-264105.1RL的泵引理Δ(Q0,A1A2…AK)=QKΔ(QK,AK+1…AJ)=QJ=QKΔ(QJ,AJ+1…AM)=QM对于任意的整数I≥0Δ(QK,(AK+1…AJ)I)=Δ(QK,(AK+1…AJ)I-1)…=Δ(QK,AK+1…AJ)=QK2009-7-264115.1RL的泵引理故,Δ(Q0,A1A2…AK(AK+1…AJ)IAJ+1…AM)=QM也就是说,A1A2…AK(AK+1…AJ)IAJ+1…AM∈L(M)U=A1A2…AK，V=AK+1…AJ，W=AJ+1…AMUVIW∈L2009-7-264125.1RL的泵引理例5-1证明{0N1N|N≥1}不是RL。证明：假设L={0N1N|N≥1}是RLZ=0N1N按照泵引理所述V=0KK≥1此时有,U=0N-K-JW=0J1N2009-7-264135.1RL的泵引理从而有,UVIW=0N-K-J(0K)I0J1N=0N+(I-1)K1N当I=2时,我们有：UV2W=0N+(2-1)K1N=0N+K1N注意到K≥1,所以,N+K>N。这就是说,0N+K1N?L这与泵引理矛盾。所以,L不是RL。2009-7-264145.1RL的泵引理例5-2证明{0N|N为素数}不是RL。证明：假设L={0N|N为素数}是RL。取Z=0N+P∈L,不妨设V=0K,K≥1从而有,UVIW=0N+P-K-J(0K)I0J=0N+P+(I-1)K2009-7-264155.1RL的泵引理当I=N+P+1时,N+P+(I-1)K=N+P+(N+P+1-1)K=N+P+(N+P)K=(N+P)(1+K)注意到K≥1,所以N+P+(N+P+1-1)K=(N+P)(1+K)不是素数。故当I=N+P+1时,UVN+P+1W=0(N+P)(1+K)?L这与泵引理矛盾。所以,L不是RL。2009-7-264165.1RL的泵引理例5-3证明{0N1M2N+M|M,N≥1}不是RL。证明：假设L={0N1M2N+M|M,N≥1}是RL。取Z=0N1N22N设V=0KK≥1从而有,UVIW=0N-K-J(0K)I0J1N22N=0N+(I-1)K1N22N2009-7-264175.1RL的泵引理UV0W=0N+(0-1)K1N22N=0N-K1N22N注意到K≥1，N-K+N=2N-K<2N0N-K1N22N?L这个结论与泵引理矛盾。所以,L不是RL。2009-7-264185.1RL的泵引理用来证明一个语言不是RL不能用泵引理去证明一个语言是RL。⑴由于泵引理给出的是RL的必要条件，所以，在用它证明一个语言不是RL时，我们使用反证法。⑵泵引理说的是对RL都成立的条件，而我们是要用它证明给定语言不是RL,这就是说，相应语言的“仅仅依赖于L的正整数N”实际上是不存在的。所以，我们一定是无法给出一个具体的数的。因此，人们往往就用符号N来表示这个“假定存在”、而实际并不存在的数。2009-7-264195.1RL的泵引理⑶由于泵引理指出，如果L是RL,则对任意的Z∈L，只要|Z|≥N，一定会存在U,V、W，使UVIW∈L对所有的I成立。因此，我们在选择Z时，就需要注意到论证时的简洁和方便。⑷当一个特意被选来用作“发现矛盾”的Z确定以后，就必须依照|UV|≤N和|V|≥1的要求，说明V不存在(对“存在U,V,W”的否定)。2009-7-264205.1RL的泵引理⑸与选Z时类似,在寻找I时,我们也仅需要找到一个表明矛盾的,具体,值就可以了(对,所有I”的否定)。⑹一般地,在证明一个语言不是RL的时候,我们并不使用泵引理的第(5)条。⑺事实上,引理所要求的|UV|≤N并不是必须的。这个限制为我们简化相应的证明提供了良好支撑——扩充了的泵引理。2009-7-264215.2RL的封闭性封闭性(CLOSUREPROPERTY)如果任意的、属于同一语言类的语言在某一特定运算下所得的结果仍然是该类语言，则称该语言类对此运算是封闭的有效封闭性(VALIDCLOSUREPROPERTY)给定一个语言类的若干个语言的描述，如果存在一个算法，它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述，则称此语言类对相应的运算是有效封闭的。2009-7-264225.2RL的封闭性定理5-1RL在并、乘积、闭包运算下是封闭的。根据RE的定义，立即可以得到此定理。2009-7-264235.2RL的封闭性定理5-2RL在补运算下是封闭的。证明,M=(Q,∑,Δ,Q0,F)L(M)=L，取DFAM′=(Q,∑,Δ,Q0,Q-F)显然,对于任意的X∈∑*，Δ(Q0,X)=F∈F?Δ(Q0,X)=F?Q-F即,X∈L(M)?X?L(M′)，L(M′)=∑*-L(M)。所以,RL在补运算下是封闭的。定理得到证明。2009-7-264245.2RL的封闭性定理5-3RL在交运算下封闭。证明思路2009-7-264255.2RL的封闭性正则代换(REGULARSUBSTITUTION)设∑,Δ是两个字母表，映射*2,F被称为是从∑到Δ的代换。如果对于?A∈∑,F(A)是Δ上的RL,则称F为正则代换。2009-7-264265.2RL的封闭性先将F的定义域扩展到∑*上：*2,*F⑴F(Ε)={Ε}；⑵F(XA)=F(X)F(A)。2009-7-264275.2RL的封闭性再将F的定义域扩展到*2?**22,F对于?L?∑*LXXFLF)()(2009-7-264285.2RL的封闭性例5-4设∑={0,1},Δ={A,B},F(0)=A,F(1)=B*，则F(010)=F(0)F(1)F(0)=AB*AF({11,00})=F(11)∪F(00)=F(1)F(1)∪F(0)F(0)=B*B*+AA=B*+AAF(L(0*(0+1)1*))=L(A*(A+B*)(B*)*)=L(A*(A+B*)B*)=L(A*AB*+A*B*B*)=L(A*B*)2009-7-264295.2RL的封闭性F是正则代换,则⑴F(Φ)=Φ；⑵F(Ε)=Ε；⑶对于?A∈∑,F(A)是Δ上的RE；⑷如果R,S是∑上的RE,则F(R+S)=F(R)+F(S)F(RS)=F(R)F(S)F(R*)=F(R)*是Δ上的RE。2009-7-264305.2RL的封闭性定理5-4设L是∑上的一个RL*2,F是正则代换，则F(L)也是RL。证明：描述工具,RE。对R中运算符的个数N施以归纳，证明F(R)是表示F(L)的RE。2009-7-264315.2RL的封闭性当N=0时,结论成立。当N?K时定理成立,即当R中运算符的个数不大于K时,F(L(R))=L(F?。当N=K+1时，2009-7-264325.2RL的封闭性⑴R=R1+R2。F(L)=F(L(R))=F(L(R1+R2))=F(L(R1)∪L(R2))RE的定义=F(L(R1))∪F(L(R2))正则代换的定义=L(F(R1))∪L(F(R2))归纳假设=L(F(R1)+F(R2))RE的定义=L(F(R1+R2))RE的正则代换的定义=L(F(R))2009-7-264335.2RL的封闭性⑵R=R1R2。F(L)=F(L(R))=F(L(R1R2))=F(L(R1)L(R2))RE的定义=F(L(R1))F(L(R2))正则代换的定义=L(F(R1))L(F(R2))归纳假设=L(F(R1)F(R2))RE的定义=L(F(R1R2))RE的正则代换的定义=L(F(R))2009-7-264345.2RL的封闭性⑶R=R1*。F(L)=F(L(R))=F(L(R1*))=F(L(R1)*)RE的定义=(F(L(R1)))*正则代换的定义=(L(F(R1)))*归纳假设=L(F(R1)*)RE的定义=L(F(R1*))RE的正则代换的定义=L(F(R))2009-7-264355.2RL的封闭性例5-5设∑={0,1,2},Δ={A,B}，正则代换F定义为：F(0)=AB；F(1)=B*A*；F(2)=A*(A+B)则：⑴F(00)=ABAB；⑵F(010)=ABB*A*AB=AB+A+B；2009-7-264365.2RL的封闭性⑶F((0+1+2)*)=(AB+B*A*+A*(A+B))*=(B*A*+A*(A+B))*=(A+B)*；⑷F(0(0+1+2)*)=AB(AB+B*A*+A*(A+B))*=AB(A+B)*；⑸F(012)=ABB*A*A*(A+B)=AB+A*(A+B)；⑹F((0+1)*)=(AB+B*A*)*=(AB+B+A+B*A*)*=(A+B)*。2009-7-264375.2RL的封闭性同态映射(HOMOMORPHISM)设∑,Δ是两个字母表,*,FF为映射，如果对于?X,Y∈∑*，F(XY)=F(X)F(Y)，则称F为从∑到Δ*的同态映射。2009-7-264385.2RL的封闭性对于?L?∑*,L的同态像LXXFLF)()(对于?W?Δ*,W的同态原像是一个集合}&)(|{)(*1XWXFXWF对于?L?Δ*,L的同态原像是一个集合})(|{)(1LXFXLF2009-7-264395.2RL的封闭性例5-6设∑={0,1},Δ={A,B}，同态映射F定义为F(0)=AAF(1)=ABA则：⑴F(01)=AAABA；⑵F((01)*)=(AAABA)*；⑶F-1(AAB)=Φ；2009-7-264405.2RL的封闭性⑷F-1(AA)={0}；⑸F-1({AAA,ABA,ABAAAAA,ABAAAAAA})={1,100}；⑹F-1((AB+BA)*A)={1}；⑺F(F-1((AB+BA)*A))=F({1})={ABA}。令L=(AB+BA)*A,上述(7)表明,F(F-1(L))≠LF(F-1(L))?L2009-7-264415.2RL的封闭性推论5-1RL的同态像是RL。证明：注意到同态映射是正则代换的特例，可以直接的到此结论。该定理表明,RL在同态映射下是封闭的。2009-7-264425.2RL的封闭性定理5-5RL的同态原像是RL。证明：使用DFA作为描述工具。(1)接受RL的同态原像的FA的构造思想。让新构造出的FAM′用一个移动去模拟M处理F(A)所用的一系列移动。对于∑中的任意字符A，如果M从状态Q开始处理F(A)，并且当它处理完F(A)时到达状态P，则让M′在状态Q读入A时，将状态变成P。2009-7-264435.2RL的封闭性M′具有与M相同的状态，并且，在M′对应的状态转移图中，从状态Q到状态P有一条标记为A的弧当且仅当在M的状态转移图中，有一条从状态Q到状态P的标记为F(A)的路。(2)接受RL的同态原像的FA的形式描述。设DFAM=(Q,Δ,Δ,Q0,F),L(M)=L，取DFAM′=(Q,∑,Δ′,Q0,F)Δ′(Q,A)=Δ(Q,F(A))2009-7-264445.2RL的封闭性(3)等价证明。施归纳于|X|，证明对于?X∈∑*，Δ′(Q0,X)=Δ(Q0,F(X))当|X|=0时，结论显然成立。设当|X|=K是结论成立，往证当|X|=K+1时结论成立。不妨设X=YA，其中|Y|=K2009-7-264455.2RL的封闭性Δ′(Q0,X)=Δ′(Q0,YA)=Δ′(Δ′(Q0,Y),A)=Δ′(Δ(Q0,F(Y)),A)归纳假设=Δ(Δ(Q0,F(Y)),F(A))Δ′的定义=Δ(Q0,F(Y)F(A))Δ的意义=Δ(Q0,F(YA))同态映射性质=Δ(Q0,F(X))2009-7-264465.2RL的封闭性这表明,结论对|X|=K+1成立。由归纳法原理,结论对?X∈∑*成立。X∈∑*,Δ′(Q0,X)∈F?Δ(Q0,F(X))∈F。由于对?X∈∑*,Δ′(Q0,X)=Δ(Q0,F(X))，所以,Δ′(Q0,X)∈F?Δ(Q0,F(X))∈F。故L(M′)=F-1(L(M))定理得证。2009-7-264475.2RL的封闭性商(QUOTIENT)设L1,L2?∑*,L2除以L1的商定义为：L1/L2={X|?Y∈L2使得XY∈L1}。计算语言的商主要是考虑语言句子的后缀。只有当L1的句子的后缀在L2中时，其相应的前缀才属于L1/L2。所以，当Ε∈L2时，L1?L1/L2。2009-7-264485.2RL的封闭性注意以下有意思的情况：取L1={000},L2={Ε},L3={Ε,0}L4={Ε,0,00},L5={Ε,0,00,000}L1/L2={000}=L1L1/L3={000,00}L1/L4={000,00,0}L1/L5={000,00,0,Ε}2009-7-264495.2RL的封闭性定理5-6L1,L2?∑*,如果L1是RL,则L1/L2也是RL。证明：设L1?∑*,是RL,DFAM=(Q,∑,Δ,Q0,F),L(M)=L1DFAM′=(Q,∑,Δ,Q0,F′)F′={Q|?Y∈L2,Δ(Q,Y)∈F}显然,L(M′)=L1/L2。定理得证。2009-7-264505.3MYHILL-NERODE定理与DFA的极小化对给定RLL,DFAM接受L,M不同，由RM确定的∑*上的等价类也可能不同。如果M是最小DFA，则M所给出的等价类的个数应该是最少的。最小DFA是不是惟一的？如果是，如何构造？最小DFA的状态对应的集合与其他DFA的状态对应的集合有什么样的关系，用这种关系是否能从一般的DFA出发，求出最小DFA？2009-7-264515.3.1MYHILL-NERODE定理DFAM确定的等价关系。M=(Q,∑,Δ,Q0,F),对于?X,Y∈∑*XRMY?Δ(Q0,X)=Δ(Q0,Y)。显然,XRMYQ∈Q,X,Y∈SET(Q)2009-7-264525.3.1MYHILL-NERODE定理例5-8设L=0*10*，它对应的DFAM如下图。2009-7-264535.3.1MYHILL-NERODE定理对应于Q0,(00)NRM(00)MN,M?0；对应于Q1,0(00)NRM0(00)MN,M?0；对应于Q2,(00)N1RM(00)M1N,M?0；对应于Q3,0(00)N1RM0(00)M1N,M?0；对应于Q4,0(00)N10KRM0(00)M10HN,M?0,K,H?1；(00)N10KRM(00)M10HN,M?0,K,H?1；0(00)N10KRM(00)M10HN,M?0,K,H?1；也就是,0N10KRM0M10HN,M?0,K,H?1；对应于Q5,XRMY——X,Y为至少含两个1的串。2009-7-264545.3.1MYHILL-NERODE定理L确定的∑*上的关系RL。对于?X,Y∈∑*，XRLY?(对?Z∈∑*,XZ∈L?ZY∈L)对于?X,Y∈∑*，如果XRLY，则在X和Y后无论接∑*中的任何串Z,XZ和YZ要么都是L的句子，要么都不是L的句子。2009-7-264555.3.1MYHILL-NERODE定理任意X,Y∈SET(Q),Δ(Q0,X)=Δ(Q0,Y)=Q对于?Z∈∑*，Δ(Q0,XZ)=Δ(Δ(Q0,X),Z))=Δ(Q,Z)=Δ(Δ(Q0,Y),Z)=Δ(Q0,YZ)这就是说,Δ(Q0,XZ)∈F?Δ(Q0,YZ)∈F2009-7-264565.3.1MYHILL-NERODE定理即,对于?Z∈∑*，XZ∈L?YZ∈L。表明,XRLY，也就是XRL(M)Y。2009-7-264575.3.1MYHILL-NERODE定理右不变的(RIGHTLNVARIANT)等价关系设R是∑*上的等价关系，对于?X，Y∈∑*，如果XRLY，则必有XZRLYZ对于?Z∈∑*成立，则称R是右不变的等价关系。2009-7-264585.3.1MYHILL-NERODE定理命题5-1对于任意DFAM=(Q,∑,Δ,Q0,F)，M所确定的∑*上的关系RM为右不变的等价关系。证明：⑴RM是等价关系。自反性显然。对称性,?X,Y∈∑*，XRMY?Δ(Q0,X)=Δ(Q0,Y)根据RM的定义；Δ(Q0,Y)=Δ(Q0,Z),=”的对称性；YRMX根据RM的定义。2009-7-264595.3.1MYHILL-NERODE定理传递性：设XRMY,YRMZ。由于XRMY,Δ(Q0,X)=Δ(Q0,Y)由于YRMZ,Δ(Q0,Y)=Δ(Q0,Z)由,=”的传递性知,Δ(Q0,X)=Δ(Q0,Z)再由RM的定义得：XRMZ即RM是等价关系。2009-7-264605.3.1MYHILL-NERODE定理⑵RM是右不变的设XRMY。则Δ(Q0,X)=Δ(Q0,Y)=Q所以,对于?Z∈∑*，Δ(Q0,XZ)=Δ(Δ(Q0,X),Z))=Δ(Q,Z)=Δ(Δ(Q0,Y),Z)=Δ(Q0,YZ)这就是说,Δ(Q0,XZ)=Δ(Q0,YZ),再由RM的定义,XZRMYZ所以,RM是右不变的等价关系。2009-7-264615.3.1MYHILL-NERODE定理命题5-2对于任意L?∑*,L所确定的∑*上的关系RL为右不变的等价关系。证明：⑴RL是等价关系。自反性显然。对称性：不难看出,XRLY?(对?Z∈∑*，XZ∈L?YZ∈L)?YRLX2009-7-264625.3.1MYHILL-NERODE定理传递性：设XRLY,YRLZ。XRLY?(对?W∈∑*,XW∈L?YW∈L)YRLZ?(对?W∈∑*,YW∈L?ZW∈L)所以,(?W∈∑*,XW∈L?YW∈L且YW∈L?ZW∈L)即：(对?W∈∑*,XW∈L?ZW∈L)故：XRLZ即RL是等价关系。2009-7-264635.3.1MYHILL-NERODE定理⑵RL是右不变的。设XRLY。由RL的定义,对?W,V∈∑*，XWV∈L?ZWV∈L,注意到V的任意性,知,XWRLYW。所以,RL是右不变的等价关系。2009-7-264645.3.1MYHILL-NERODE定理指数(INDEX)设R是∑*上的等价关系，则称|∑*/R|是R关于∑*的指数。简称为R的指数。简称∑*的关于R的一个等价类，也就是∑*/R的任意一个元素，为R的一个等价类2009-7-264655.3.1MYHILL-NERODE定理例5-9图5-4所给DFAM所确定的RM的指数为6。RM将∑*分成6个等价类：SET(Q0)={(00)N|N?0}；SET(Q1)={0(00)N|N?0}；SET(Q2)={(00)N1|N,M?0}；SET(Q3)={0(00)N1|N?0}；SET(Q4)={0N10K|N?0,K?1}；SET(Q5)={X|X为至少含两个1的串}。2009-7-264665.3.1MYHILL-NERODE定理RM是RL(M)的,加细,(REFINEMENT)–?X,Y∈∑*，如果XRMY，必有XRL(M)Y成立。即对于任意DFAM=(Q,∑,Δ,Q0,F)。|∑*/RL(M)|?|∑*/RM|?|Q|–按照RM中被分在同一等价类的串，在按照RL(M)分类时，一定会被分在同一个等价类。–RM对∑*的划分比RL(M)对∑*的划分更,细,。称RM是RL(M)的,加细,(REFINEMENT)。2009-7-264675.3.1MYHILL-NERODE定理∑*/RM={SET(Q0),SET(Q1),SET(Q2),SET(Q3)，SET(Q4),SET(Q5)}⑴取00∈SET(Q0),000∈SET(Q1)。对于任意的X∈∑*，当X含且只含一个1时，00X∈L(M),000X∈L(M)；当X不含1或者含多个1时,00X?L(M),000X?L(M)。这就是说，对于任意的X∈∑*,00X∈L(M)?000X∈L(M)。即按照RL(M),00与000被分在同一个等价类中。从而SET(Q0)和SET(Q1)被包含在RL(M)的同一个等价类中。2009-7-264685.3.1MYHILL-NERODE定理⑵取00∈SET(Q0),001∈SET(Q2)。取特殊的字符串1∈∑*,001∈L(M),但0011?L(M)。所以,根据RL(M),SET(Q0)和SET(Q2)不能被,合并,到一个等价类中。类似地，根据RL(M),SET(Q3),SET(Q4),SET(Q5)也都不能被,合并,到SET(Q0)的句子所在的等价类中。2009-7-264695.3.1MYHILL-NERODE定理⑶取001∈SET(Q2),01∈SET(Q3)。对于任意的X∈∑*,X要么不含1，要么含有1。当X不含1时,001X∈L(M),01X∈L(M)；当X含有1时,001X?L(M),01X?L(M)。这就是说，对于任意的X∈∑*,001X∈L(M)01X∈L(M)。即按照RL(M),001与01属于RL(M)的同一个等价类中。从而SET(Q2)和SET(Q3)被包含在RL(M)的同一个等价类中。2009-7-264705.3.1MYHILL-NERODE定理⑷取1∈SET(Q2),10∈SET(Q4)。对于任意的X∈∑*,X要么不含1，要么含有1。当X不含1时,1X∈L(M),10X∈L(M)；当X含有1时,1X?L(M),10X?L(M)。这就是说，对于任意的X∈∑*,1X∈L(M)?10X∈L(M)。即按照RL(M),1与10被分在RL(M)的同一个等价类中。从而在SET(Q2)和SET(Q4)被包含在RL(M)的同一个等价类中。2009-7-264715.3.1MYHILL-NERODE定理⑸取1∈SET(Q2),11∈SET(Q5)。注意到1Ε=1,11Ε=11；而1∈L(M)，11?L(M)。即1和11不满足关系RL(M)，所以,SET(Q2)和SET(Q5)不能被,合并,到RL(M)的同一个等价类中。在这里,Ε∈∑*是一个特殊的字符串。2009-7-264725.3.1MYHILL-NERODE定理∑*/RL(M)={SET(Q0)∪SET(Q1)，SET(Q2)∪SET(Q3)∪SET(Q4),SET(Q5)}不含1,[0]=SET(Q0)∪SET(Q1)=0*；含一个1,[1]=SET(Q2)∪SET(Q3)∪SET(Q4)=0*10*；含多个1,[11]=SET(Q5)=0*10*1(0+1)*。2009-7-264735.3.1MYHILL-NERODE定理定理5-1(MYHILL-NERODE定理)如下三个命题等价：⑴L?∑*是RL；⑵L是∑*上的某一个具有有穷指数的右不变等价关系R的某些等价类的并；⑶RL具有有穷指数。2009-7-264745.3.1MYHILL-NERODE定理证明：由(1)可以推出(2)设L?∑*是RL,所以，存在DFAM=(Q,∑,Δ,Q0,F)，使得L(M)=L。由命题5-3-1,RM是∑*上的右不变等价关系，而且|∑*/RM|?|Q|，所以，RM具有有穷指数。而FQQSETL)(L是∑*上的具有有穷指数的右不变等价关系RM的、对应于M的终止状态的等价类的并。2009-7-264755.3.1MYHILL-NERODE定理由(2)可以推出(3)。设XRY，由R的右不变性可知，对于任意Z∈∑*，XZRYZ而L是R的某些等价类的并,所以,XZ∈L?YZ∈L根据RL的定义,XRLY故R是RL的加细。由于R具有有穷指数，所以,RL具有有穷指。2009-7-264765.3.1MYHILL-NERODE定理由(3)可以推出(1)。令M′=(∑*/RL,∑,Δ′,[Ε],{[X]|X∈L})[Ε]表示Ε所在的等价类对应的状态；[X]表示X所在的等价类对应的状态。对于?([X],A)∈(∑*/RL)×∑,Δ′([X],A)=[XA]Δ′定义的相容性L(M′)=L2009-7-264775.3.1MYHILL-NERODE定理例5-10用定理5-7证明{0N1N|N?0}不是RL–根据L的句子的特征来寻找RL的等价类。–L的句子的主要特点有两个：⑴句子中所含的字符0的个数与所含的字符1的个数相同。⑵所有的0都在所有的1的前面–可以得到如下一些等价类。2009-7-264785.3.1MYHILL-NERODE定理[10]={X|X=0N1M(M?N+1)或者X中含子串10}[Ε]——Ε所在的等价类；[1]——0所在的等价类；[2]——00所在的等价类；[3]——000所在的等价类；…[N]——0N所在的等价类；…所以,RL的指数是无穷的。因此,L不是RL。2009-7-264795.3.1MYHILL-NERODE定理推论5-1对于任意的RLL，如果DFAM=(Q，∑,Δ,Q0,F)满足L(M)=L，则|∑*/RL|?|Q|。表明，对于任意DFAM=(Q,∑,Δ,Q0，F),|Q|?|∑*/RL(M)|。也表明，对任意一个RLL，按照定理中所给的方法构造出来的DFAM′是一个接受L的最小DFA。这个DFA是惟一的么？2009-7-264805.3.1MYHILL-NERODE定理推论5-2对于任意的RLL，在同构意义下，接受L的最小DFA是惟一的。证明：接受L的最小DFAM=(Q,∑,Δ,Q0,F)的状态数与RL的指数相同，也就是说，这个最小DFA的状态数与MYHILL-NERODE定理证明中构造的M′=(∑*/RL,∑,Δ′,[Ε]，{[X]|X∈L})的状态数是相同的。2009-7-264815.3.1MYHILL-NERODE定理DFA同构是指这两个DFA的状态之间有一个一一对应，而且这个一一对应还保持状态转移也是相应一一对应的。也就是说，如果Q与[W]对应,P与[Z]对应，当Δ(Q，A)=P时，必定有Δ([W],A)=[Z]。这两个DFA是同构。定义映射FF(Q)=F(Δ(Q0,X))=Δ′([Ε],X)=[X]Δ(Q0,X)=Q2009-7-264825.3.1MYHILL-NERODE定理F为Q与∑*/RL之间的一一对应–如果Δ(Q0,X)=Δ(Q0,Y)，则XRMY–由于RM是RL的加细,所以,XRLY–故,[X]=[Y],即,Δ′([Ε],X)=Δ′([Ε],Y)。–如果,Δ(Q0,X)≠Δ(Q0,Y)–则,Δ′([Ε],X)≠Δ′([Ε],Y)–即,[X]≠[Y]–否则,|∑*/RM|>|∑*/RL|。2009-7-264835.3.1MYHILL-NERODE定理如果Δ(Q,A)=P,F(Q)=[X]，必有F(P)=[XA]–?Q∈Q,如果,F(Q)=F(Δ(Q0,X))=[X]–所以,?A∈∑,如果,–P=Δ(Q,A)=Δ(Δ(Q0,X),A)=Δ(Q0,XA)–则F(P)=F(Δ(Q,A))=F(Δ(Δ(Q0,X),A))=F(Δ(Q0,XA))=[XA]–即,如果M在状态Q读入字符A时进入状态P，则M在Q对应的状态F(Δ(Q0,X))=[X]读入字符A时,进入P对应的状态F(Δ(Q0,XA))=[XA]。所以,F是M和M′之间的同构映射。2009-7-264845.3.2DFA的极小化可以区分的(DISTINGUISHABLE)状态设DFAM=(Q,∑,Δ,Q0,F)，如果X∈∑*,对Q中的两个状态Q和P，使得Δ(Q,X)∈F和Δ(P,X)∈F中，有且仅有一个成立，则称P和Q是可以区分的。否则，称Q和P等价。并记作Q≡P。2009-7-264855.3.2DFA的极小化算法5-1DFA的极小化算法算法思想：扫描所有的状态对,找出所有的可区分的状态对,不可取分的状态对一定是等价的。输入：给定的DFA。输出：可区分状态表。主要数据结构：状态对的关联链表；可区分状态表。2009-7-264865.3.2DFA的极小化主要步骤⑴FOR?(Q,P)∈F×(Q-F)DO标记可区分状态表中的表项(Q,P)；⑵FOR?(Q,P)∈F×F∪(Q-F)×(Q-F)&Q≠PDO⑶IF?A∈∑,可区分状态表中的表项(Δ(Q,A),Δ(P,A))已被标记THENBEGIN⑷标记可区分状态表中的表项(Q,P)；⑸递归地标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对应表项END2009-7-264875.3.2DFA的极小化⑹ELSEFOR?A∈∑,DO⑺IFΔ(Q,A)≠Δ(P,A)&(Q,P)与(Δ(Q，A),Δ(P,A))不是同一个状态对THEN将(Q,P)放在(Δ(Q,A),Δ(P,A))的关联链表上。2009-7-264885.3.2DFA的极小化定理5-8对于任意DFAM=(Q,∑,Δ,Q0，F),Q中的两个状态Q和P是可区分的充要条件是(Q,P)在DFA的极小化算法中被标记。证明：先证必要性。设Q和P是可区分的,X是区分Q和P的最短字符串。现施归纳于X的长度，证明(Q,P)一定被算法标记。2009-7-264895.3.2DFA的极小化当|X|=0时Ε区分Q和P,表明Q和P有且仅有一个为M的终止状态,所以,(Q,P)∈F×(Q-F)因此，它在算法的第(1)行被标记。设当|X|=N时结论成立X是区分Q和P的长度为N的字符串，则(Q,P)被算法标记。2009-7-264905.3.2DFA的极小化当|X|=N+1时设X=AY,其中|Y|=N。由于X是区分Q和P的最短的字符串,所以,Δ(Q,X)∈F和Δ(P，X)∈F中,有且仅有一个成立。不妨假设：Δ(Q,X)?F,Δ(P,X)∈F即Δ(Δ(Q,A),Y)?F,Δ(Δ(P,A),Y)∈F设Δ(Q,A)=U,Δ(P,A)=VY是区分U和V的长度为N的字符串。2009-7-264915.3.2DFA的极小化由归纳假设,(U,V)可以被算法标记。如果在考察(Q,P)时,(U,V)已经被标记，则(Q,P)在算法的第(4)行被标记；如果在考察(Q,P)时,(U,V)还没有被标记，则(Q,P)在算法的第(7)行被放入到(U,V)的关联链表中，而当(U,V)被标记时，在算法的第(5)行在,递归,过程中(Q,P)被标记。结论对|X|=N+1成立。2009-7-264925.3.2DFA的极小化充分性。设(Q,P)在算法中被标记。对它被标记的顺序N施归纳，证明Q和P是可区分的。令|F×(Q-F)|=M,显然,当1?N?M时,(Q，P)是在算法的第(1)行被标记的,此时,Ε是区分Q和P的字符串：Δ(Q,Ε)∈F和Δ(P,Ε)∈F有且仅有一个成立。2009-7-264935.3.2DFA的极小化设N?K(K?M)时结论成立。即,如果(Q,P)是被算法在第K个或者第K个之前标记的,则存在字符串X,X区分Q和P。即,Δ(Q,X)∈F和Δ(P，X)∈F有且仅有一个成立。当N=K+1时,如果(Q,P)是在算法的第(4)行被标记的,此时,(Δ(Q,A),Δ(P,A))一定是在第K个之前被标记的。设Δ(Q,A)=U,Δ(P,A)=V，由归纳假设,存在字符串X,X区分U和V：Δ(U,X)∈F和Δ(V,X)∈F有且仅有一个成立,从而,Δ(Q,AX)∈F和Δ(P,AX)∈F有且仅有一个成立。即,AX是区分Q和P的字符串。2009-7-264945.3.2DFA的极小化如果(Q,P)是在算法的第(5)行被标记的,则它必在某个状态对(U,V)的关联链表中,而(U,V)必在(Q,P)之前被标记。由归纳假设,存在X区分(U,V)；存在A∈∑,Δ(Q,A)=U,Δ(P,A)=V使得(Q,P)被放在(U,V)的关联链表中；AX是区分Q和P的字符串。所以，结论对N=K+1成立。由归纳法原理，结论对所有的N成立。2009-7-264955.3.2DFA的极小化定理5-9由算法5-1构造的DFA在去掉不可达状态是最小DFA。证明：设M=(Q,∑,Δ,Q0,F)为算法5-1的输入DFA，M′=(Q/≡,∑,Δ′,[Q0],F′)是相应的输出DFA。F′={[Q]|Q∈F}。对于?[Q]∈Q/≡,?A∈∑,定义Δ′([Q],A)=[Δ(Q,A)]2009-7-264965.3.2DFA的极小化Δ′的相容性。–设[Q]=[P],也就是说,Q和P等价,Q≡P。即根据算法5-1，状态Q和P是不可区分的(未被算法标记)。此时，对于?A∈∑,必须有[Δ(Q，A)]≡[Δ(P,A)]。否则，状态对(Δ(Q,A)，Δ(P,A))必定被算法标记，从而最终导致(Q，P)被算法标记。此与Q≡P矛盾。所以，状态[Δ(Q,A)]和状态[Δ(P,A)]等价,Δ(Q，A)=Δ(P,A)。所以,Δ′的定义是相容的。2009-7-264975.3.2DFA的极小化L(M′)=L(M)。–对?X∈∑*，现施归纳于|X|，证明Δ′([Q0],X)=[Δ(Q0,X)]–|X|=0Δ′([Q0],Ε)=[Q0]=[Δ(Q0,Ε)]–?X∈∑*并且|X|=N，Δ′([Q0],XA)=Δ′(Δ′([Q0],X),A)=Δ′([Δ(Q0,X)],A)=[Δ([Δ(Q0,X)],A)]=[Δ(Q0,XA)]–由归纳法原理，结论对?X∈∑*成立。2009-7-264985.3.2DFA的极小化再由F′的定义,Δ′([Q0],X)=[Δ(Q0,X)]∈F′?Δ(Q0，X)∈F。所以,X∈L(M′)?X∈L(M)。即：L(M′)=L(M)。2009-7-264995.3.2DFA的极小化证明所构造的M′去掉不可达状态后是最小DFA。–如果[Q]≠[P]，则对于?X∈SET([Q])，Y∈SET([P]),XRLY不成立。事实上，如果[Q]≠[P]，则存在Z∈∑*,Z区分Q和P，有Δ(Q，Z)=Q′和Δ(P,Z)=P′有且仅有一个是终止状态，这就是说,XZ和YZ有且仅有一个是L的句子。所以,XRLY是不成立的。2009-7-265005.3.2DFA的极小化例5-11用算法5-1对图5-4所给的DFA进行极小化。Q1Q2××Q3××Q4××Q5×××××Q0Q1Q2Q3Q42009-7-265015.3.2DFA的极小化2009-7-265025.3.2DFA的极小化例5-11用算法5-1对图5-7所给的DFA进行极小化。2009-7-265035.3.2DFA的极小化Q1×Q2××Q3×××Q4××××Q5×××××Q6××××××Q7×××××××Q8××××××××Q0Q1Q2Q3Q4Q5Q6Q72009-7-265045.4关于正则语言的判定算法定理5-10设DFAM=(Q,∑,Δ,Q0,F)，L=L(M)非空的充分必要条件是：存在X∈∑*,|X||M接受W}–
更多文章
友情链接