形式语言与自动机理论--第一章(蒋宗礼)

形式语言与自动机理论FormalLanguagesandAutomataTheory蒋宗礼课程目的和基本要求•课程性质–技术基础•基础知识要求–数学分析（或者高等数学），离散数学•主要特点–抽象和形式化–理论证明和构造性–基本模型的建立与性质课程目的和基本要求•本专业人员4种基本的专业能力–计算思维能力–算法的设计与分析能力–程序设计和实现能力–计算机软硬件系统的认知、分析、设计与应用能力•计算思维能力–逻辑思维能力和抽象思维能力–构造模型对问题进行形式化描述–理解和处理形式模型课程目的和基本要求•知识–掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。•能力–培养学生的形式化描述和抽象思维能力。–使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容•语言的文法描述。•RL–RG、FA、RE、RL的性质。•CFL–CFG(CNF、GNF)、PDA、CFL的性质。•TM–基本TM、构造技术、TM的修改。•CSL–CSG、LBA。教材及主要参考书目1.蒋宗礼，姜守旭.形式语言与自动机理论.北京：清华大学出版社，2003年2.JohnEHopcroft,RajeevMotwani,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation(2ndEdition).Addison-WesleyPublishingCompany,20013.JohnEHopcroft,JeffreyDUllman.IntroductiontoAutomataTheory,Languages,andComputation.Addison-WesleyPublishingCompany,1979第1章绪论•1.1集合的基础知识•1.1.1集合及其表示–集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set)，简称为集(set)。–元素：集合的成员为该集合的元素(element)。–集合描述形式。–基数。–集合的分类。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的真子集(propersubset)，记作AB1.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|。1.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|。1.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},|{AaSAaASA交(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。交(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。差(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|。对称差(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)。笛卡儿积(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×Φ=Φ。笛卡儿积(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|。幂集(powerset)•A幂集(powerset)是一个集合，该集合是由A的所有子集组成的，记作2A。•2A={B|BA}。•2A读作A的幂集。幂集(powerset)⑴Φ∈2A。⑵Φ2A。⑶Φ2A。⑷2Φ={Φ}。⑸A∈2A。⑹如果A是有穷集，则|2A|=2|A|。⑺2A∩B=2A∩2B。⑻如果AB，则2A2B。补集(complementaryset)A是论域U上的一个集合，A补集是由U中的、不在A中的所有元素组成的集合，记作AUAUU补集(complementaryset)AABAUBAAB&BABABABAABUAA如果AB，则。。。。。。1.2关系•二元关系•递归定义与归纳证明•关系的闭包1.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)性。1.2.1二元关系(binaryrelation)•三歧性–自反性、对称性、传递性。•等价关系(equivalencerelation)–具有三歧性的二元关系称为等价关系。1.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恒不成立1.2.1二元关系(binaryrelation)•指数(index)–把R将S分成的等价类的个数称为是R在S上的指数。如果R将S分成有穷多个等价类，则称R具有有穷指数；如果R将S分成无穷多个等价类，则称R具有无穷指数。–给定集合S上的一个等价关系R，R就确定了S的一个等价分类，当给定另一个不同的等价关系时，它会确定S的一个新的等价分类。1.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。1.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。1.2.1二元关系(binaryrelation)1.关系这一个概念用来反映对象——集合元素之间的联系和性质2.二元关系则是反映两个元素之间的关系，包括某个元素的某种属性。3.对二元关系的性质，要强调全称量词是对什么样的范围而言的。1.2.2等价关系与等价类（略）1.2.3关系的合成（略）1.2.4递归定义与归纳证明•递归定义(recursivedefinition)–又称为归纳定义(inductivedefinition)，它来定义一个集合。–集合的递归定义由三部分组成：•基础(basis)：用来定义该集合的最基本的元素。•归纳(induction)：指出用集合中的元素来构造集合的新元素的规则。•极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来。1.2.4递归定义与归纳证明•归纳证明–与递归定义相对应。–归纳证明方法包括三大步：•基础(basis)：证明最基本元素具有相应性质。•归纳(induction)：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法得到的新元素也具有相应的性质。•根据归纳法原理，所有的元素具有相应的性质。1.2.4递归定义与归纳证明•定义1-17设R是S上的关系，我们递归地定义Rn的幂：⑴R0={(a，a)|a∈S}。⑵Ri=Ri-1R(i=1,2,3,4,5,…)。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，…1.2.4递归定义与归纳证明例1-18算术表达式⑴基础：常数是算术表达式，变量是算术表达式；⑵归纳：如果E1、E2是表达式，则+E1、-E1、E1+E2、E1-E2、E1*E2、E1/E2、E1**E2、Fun(E1)是算术表达式。其中Fun为函数名。⑶只有满足(1)和(2)的才是算术表达式。1.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}=Φ1.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|⑶由归纳法原理，结论对任意有穷集合成立。1.2.4递归定义与归纳证明例1-20表达式的前缀形式是指将运算符写在前面，后跟相应的运算对象。如：+E1的前缀形式为+E1，E1+E2的前缀形式为+E1E2，E1*E2的前缀形式为*E1E2，E1**E2的前缀形式为**E1，Fun(E1)的前缀形式为F