形式语言课件：第1章 集合、函数及语言

1、1.1、集合、集合 集合集合：对象的汇集。 如：L=a,b,c,d 就是四个字母的汇集形成的集合。 元素或成员元素或成员：构成集合的所有对象。 如：b是集合L的一个元素，表示成：bL 另一方面z不是L的元素，记作：z L 单元素集单元素集：集合中只有一个元素，即有一个元素构成的集合。 空集空集：集合中没有一个元素，用表示。 集合元素性质定义：设集合A已经定义，P是A的元素具有的性质，则可以定义一个新集合B如下： B=x:x A且x具有性质P 子集子集：如果集合A的每一个元素都是集合B的元素，则称A是B的子集，记作：A B 真子集真子集： 如果A B，但AB，则称A是B的真子集。集合的性质集合的

2、性质：设A、B和C是集合，则下述算律成立1、幂等率 AA=A AA=A2、交换律 AB=BA AB=BA3、结合律 (AB)C= A(BC) (AB)C= A(BC)4、分配律 (AB)C=（AC)(BC) (AB)C=（AC)(BC)5、吸收律 (AB)A=A (AB)A=A6、De Morgan律 A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C)幂集：集合A的所有子集所有子集的汇集本身是一个集合，叫做A的幂集 记作：2A非空集合的非空集合的划分划分：如果是A的一些子集的集合，使得满足 (1) 的每一个元素非空，即非空集合； (2) 的不同元素是不相交的； (3) =A

3、，其中表示中所有元素的汇集 则是A的一个划分。例如：(a,b),c,d是a,b,c,d的一个划分； 奇自然数集合和偶自然数集合构成自然数N的一个划分。1.2、关系与函数、关系与函数 ：由两个元素构成的对，前后有别。 如a和b的有序对记作(a,b)，a和b叫做它的。 ：两个集合A和B的迪卡儿积是aA且bB的所有有序对(a,b)构成的集合，记作AB。 ：两个集合A和B的二元关系是AB的子集。 ：设n是任一自然数，如果a1,a2,an是任意n个对象，也可以有相同对象，则(a1,a2,an)是一个。n叫做序列长度长度。 从而就有：有序2元组、有序3元组、。有序n元组 ：集合A1,An上的n元关系就是A

4、1。An一个子集。 即有序n元组的集合。 ：集合A到集合B的函数是A和B上的具有下述特殊性质的二元关系R: 对于每一个元素aA，在R中恰好存在一个有序对以a为第一分量， 第二分量bB。 一般的，设f: A1An|B是一个函数，f(a1,an)=b， 其中： aiAi，且bB，有时称a1,an是f的自变量，b是f对应的值。：如果对任意两个不同的值a,aA，f(a) f(a) 则称函数f: A|B是一对一的。：如果B的每一个元素都是A的某一个元素在f下的值或叫象， 则称函数f: A|B满射到B。： 如果函数f: A|B既是一对一的，又是满射到B的， 则称f是A与B之间的双射。：记作R-1， R-1

5、 =(a,b): (b,a)R 显然，若R AB，则R-1 BA。：设Q和R是两个二元关系，他们的合成Q。R(简记QR)为: QR=(a,b): 对于某个c，(a,c)Q且(c,b)R 注意：两个函数f: A|B和g: B|C的合成是一个函数h: A|C， 使得对每一个aA，h(a)=g( f(a) )1.3、特殊类型的二元关系、特殊类型的二元关系 1、AA的二元关系二元关系 设A是一个集合，R AA是A上的一个二元关系，可以用一个有向图表示关系R。 A的每一个元素用一个小圆圈表示(叫做有向图的顶点)，从a到b画一个箭头当且仅当(a,b)R，这些箭头是该有向图的边。 例如：用图1-1中图表示关

6、系R= (a,b),(b,a),(a,d),(d,c),(c,c),(c,a) adcb图1-1 二元关系的有向图表示自反关系自反关系：如果对于每一个aA，(a,a)R，则称关系R AA 是自反自反的对称关系对称关系：如果只要(a,b)R就有(b,a)R，则称关系R AA 是对称对称的 没有(a,a)形式的有序对的对称关系可以表示成或称。反对称关系反对称关系：如果当(a,b)R且ab时，(b,a)R，则称关系R是反对称反对称的传递关系传递关系：如果只要(a,b)R且(b,c)R就有(a,c)R ，则称关系R是传递传递的等价关系等价关系：把自反、对称、传递的关系叫做等价关系等价关系。如书上图1-

7、6。等价类等价类：表示等价关系的无向图由若干个集团组成，把等价关系的这种集团 叫做等价类等价类。定理1.3.1 设R是非空集合A上的等价关系，则R的等价类构成A的一个划分。 （证明：利用等价关系性质采用反证法，略）另外，由于二元关系R可以表示成图，所以也有类似于图的、。1.4、有穷集合与无穷集合：如果存在双射函数f: A|B，则称集合A与B等势。：一般的，如果对某个自然数n，一个集合与1,2,n等势， 则称这个集合是有穷的有穷的。：如果一个集合不是有穷的，则称它是无穷的无穷的。 例如：自然数集合N是无穷的；整数集合、实数集合都是无穷的。：称与N等势的集合是可数无穷的可数无穷的。：称有穷集合或可

8、数无穷集合是可数的可数的。（可枚举的） 相反，不是可数的集合称为。另外，要证明集合A是可数无穷的，必须给出A与N之间的一个双射函数f。见书1.5、三个基本的证明技术、三个基本的证明技术 1、的原理的原理 如果A是一个自然数的集合使得： （1）0A； （2）对于每一个自然数n，0,1,n A蕴函n+1A; 则A=N 非形式地非形式地说(数学归纳法的原理)： 任何一个包含0的自然数集合，如果它具有下述性质：它只要包含所有小于等于n的自然数就包含n+1，则它实际上就是全体自然数的集合。 一般的一般的，用归纳法证明下述断言：“对于所有的自然数n，性质P成立。” 用下述方式把数学归纳法原理应用于集合A=

9、n: 对于n，P为真： （1）基础步骤：证明0A，即对于0，P成立。 （2）归纳假设：假设对任意固定的n0，P对于0,1,n成立。 （3）归纳步骤：利用归纳假设证明P对于n+1成立，于是根据归纳原理，A等于N，即P对于每一个自然数成立。换句话说，如果企图把换句话说，如果企图把A的元素的元素(“鸽子鸽子”)与与B的元素的元素(“鸽巢鸽巢”)配对，迟配对，迟早不得不把一只以上的鸽子放入一个巢里。早不得不把一只以上的鸽子放入一个巢里。 鸽巢原理可以用第一个基本原理鸽巢原理可以用第一个基本原理-数学归纳法证明。数学归纳法证明。(见书上见书上)设设R是有穷集合是有穷集合A上的二元关系，上的二元关系，a,

10、bA。如果在R中有一条从a到b的通路，则有一条长度不超过|A|的通路。：假设(a1,a2,an)是从a1=a到an=b的最短通路，即长度最小的通路，又假设n|A|。由鸽巢原理，A有一个元素重复出现在这条通路上，比如说ai=aj，1ij n。于是， (a1,a2,ai,aj+1,an)是另一条更短的从a到b的通路，这与假设(a1,a2,an)是从a到b的最短通路相矛盾。(完毕)3、 ：设设R是集合是集合A上的二元关系，上的二元关系，D=a: aA且(a,a) R称为R的对角线集合。对于每一个aA，令Ra=b: bA且(a,b)R，则D与每一个Ra都不相同。 即，把R看成一个正方阵列，对角线的补与

11、每一行都不同。 （见书上例1.5.3） 理由：关于a是否是元素的问题，对角线集合D与Ra集合总是不同的。 若aD，则必然(a,a)R；若aRa，则必然(a,a)R;矛盾！ 即对角线上无关系的元素所在行自然不相等；对角线上有关系的元素又多余该对角线上元素。定理定理1.5.2 集合集合2N是不可数的。是不可数的。（自然数的幂集自然数的幂集）证明：(大概思路)利用反证法假设它是可数无穷的，再利用对角线原理证明假设不成立。略，见书。 1.6、闭包与算法、闭包与算法 设RA2是集合A上的有向图。R的是关系 R*= (a,b): a,bA且在R中存在从a到b的通路 例子见书图1-9，构造算法见P17下 定

12、义1.6.1函数的增长率函数的增长率：算法随问题规模变化的增长规律。 (1) 所有次数相同的多项式具有相同的增长率。 (2) nd2n nn 例子：以R关系的自反传递闭包计算为例，说明函数增长率。 p17定义1.6.1算法复杂度O(nn+1) p20改进后新算法复杂度O(n5) p21再改进后新算法复杂度O(n3) 本科生算法分析和数据结构课程中已经介绍过。略。封闭性：封闭性： 定义定义 1.6.3 设D是一个集合，R Dn+1是D上的一个n+1元关系，其中n0。又设B是D的子集。如果只要b1,bnB且(b1,bn,bn+1)R，就有bn+1B，则称B在R下是封闭的。 任何“集合B在关系R1,

13、R2,Rm下是封闭的”形式的性质称为B的封闭性。定理定理1.6.1 设P是由集合D上的关系定义的封闭性，A是D的子集，则有唯一的包含A具有性质P的极小集合B。 （证明：略）闭包闭包：定理1.6.1中的B是A在关系R1,Rm下的闭包闭包。关于形式语言及表示我们前面已经讨论过。下面我们简单地讨论一下语言的有穷表示-正则表达式与正则语言 计算理论中一个核心问题：用有穷的规定有穷的规定说明表示无穷语言无穷语言。例1.8.1 令L=w0,1* ：在w中1出现两次或三次，并且第一次和第二次不相邻 这个语言可以只用单元集和语言运算符号、。、*描述如下： 0* 。1 。 0* 。 0 。 1 。 0* ( (

14、1 。0* ) *) 进一步简单地写成： L=0*10*010*(10* ) - 正则表达式正则表达式正则表达式定义定义： 字母表上的正则表达式是字母表 (,), , , * 上可以如下获得的所有字符串： (1)、 和的每一个成员是正则表达式。 (2)、如果和是正则表达式，则()也是正则表达式。 (3)、如果和是正则表达式，则()也是正则表达式。 (4)、如果是正则表达式，则*也是正则表达式。 (5)、除上述(1)-(4)得到之外，没有任何别的正则表达式。 如果如果是任意一个正则表达式，则是任意一个正则表达式，则L()是是表示的语言。即表示的语言。即L是从字是从字符串到语言的函数。符串到语言的

15、函数。函数L的定义： (1)、L( )=空集；对于每一个a，L(a)=a (2)、如果和是正则表达式，则L( () ) = L()L() (3)、如果和是正则表达式，则L( () ) = L()L() (4)、如果是正则表达式，则L( * ) = L()* 例1.8.2 L( ( (ab)* a ) 是什么？计算如下： L( ( (ab)* a ) = L( (ab)* ) L(a) - 由(2)得到 = L( (ab)* ) a - 由(1)得到 = L( (ab) )* a - 由(4)得到 = ( L(a)L(b) )* a - 由(3)得到 = ( ab )* a - 由(1)两次得到 = a, b* a = wa, b*：w以a结束 。例1.8.3 ( c*(a(bc*)* )表示的语言是什么？- 该正则表达式表示a,b,c上不含子串ac的所有字符串的集合。正则语言正则语言： 定义字母表上的正则语言正则语言类由所有可写成L=L()的语言L组成，其中是上的任一正则表达式。 即，正则语言是所有能够用正则表达式描述的语言。 也就是， 上的正则语言正则语言类恰好是语言集合 a：a 关于并、连接和Kleene星号函数的