离散数学复习提纲.doc

集合论一、基本概念集合(set)：做为整体识别的、确定的、互相区别的一些对象的总体。规定集合的三种方式：列举法、描述法、归纳法集合论的三大基本原理外延公理：两个集合A和B相等当且仅当它们具有相同的元素（无序性）概括公理：对于任意个体域U，任一谓词公式P都确定一个以该域中的对象为元素的集合S（确定性）正规公理：不存在集合A1,A2,A3,使得A3A2A1（有限可分，集合不能是自己的元素）注意：隶属、包含的判断（有时两者兼有）定理1：对于任意集合A和B，A=B当且仅当A Í B且B Í AÍ传递性，对全集、空集的Í关系等定理5：空集是唯一的子集、真子集、子集个数等运算：并、交、补、差、幂集，及一些运算性质、公式幂集：对任意集合A，(A)称作A的幂集，定义为：(A)=x|xÍA，所有子集的集合设A,B为任意集合， AAB当且仅当(A) Í(B)集合族：如果集合C中的每个元素都是集合，称C为集合族集合族的标志集：如果集合族C可以表示为某种下标的形，C=Sd|dD，那么这些下标组成的集合称作集合族C的标志集广义并、广义交，及相关运算性质、公式归纳定义：基础条款：规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则终极条款：规定待定义集合只含有基础条款和归纳条款所确定的成员基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象例：自然数的归纳定义、数学归纳法等（建议看一下课件例子了解一下思路）二、关系有序组（二元）：设a,b为任意对象，称集合族a,a,b为二元有序组，简记为<a,b>称a为<a,b>的第一分量，b为第二分量递归定义：n=2时，<a1,a2>=a1,a1,a2n>2时，<a1,an>=<< a1,an-1>, an>集合的笛卡儿积：对任意集合A,A2,A，A1×A2称作集合A1，A2的笛卡儿积，定义如下：A1×A2 = <u,v> | uA1,vA2A1×A2× ×An =(A1×A2× ×An-1) ×An定理：对于任意有限集合A1,An，有|A1××An|=|A1|*|An|一些运算性质关系是各个对象之间的联系和对应R称为集合A1,A2,An-1到An的n元关系，如果R是A1×A2××An的一个子集。当A1=A2=An-1=An时，也称R为A上的n元关系几个特殊二元关系：空关系、全关系、相等关系定义：设R为A到B的二元关系(RÍA×B)xRy表示<x,y>R， ¬xRy表示<x,y>ÏR定义域domain：Dom(R)=x|xA$y(<x,y>R)R的值域range：Ran(R)=y|yB$x(<x,y>R)称A为R的前域，B为R的陪域注意：前域与定义域，陪域与值域的差别。尤其是定义域与前域，与函数的差别关系表示法：集合表示法关系图表示法（有向箭头，主要是前域陪域相同的关系图）关系矩阵（mij=1当且仅当aiRbj；mij=0当且仅当¬aiRbj）关系相等：相同前域陪域，且"x"y(xRyxSy)运算：要有相同前域、陪域。但总可以对关系的前域和陪域做适当的扩充，使之满足条件并（矩阵分量析取）交（矩阵分量合取）差（前一个关系和后一个关系的补矩阵做合取）补（矩阵做否定）逆运算：R=<y,x>|xRy，RÍA×B，是B×A上的关系，关系矩阵转置合成：RÍA×B，SÍB×C，R和S的合成关系R°S定义为：R°S=<x,z>|xAzC$y(yBxRyySz)，R°S ÍA×C矩阵乘法，其中乘法用合取，加法用析取幂运算：定义为自身的n次合成Rn=R°°R（n个R合成），R0=EA幂关系有限定理：设集合A的基数为n，R是A上的二元关系，则存在自然数i,j使得0 ij2n2，有Ri=Rj（鸽笼原理，A×A有n2个元素，子集个数为2n2个）自反关系：（就是每个元素都和自己有关系）"x(xAxRx)关系图：每个节点都有环关系矩阵：对角线全为1反自反关系：（每个元素都和自己没关系）"x(xA ¬xRx)关系图：每个节点都没有环关系矩阵：对角线全为0对称关系：（每对关系都是相互的）"x"y(x,yAxRyyRx)关系图：两个节点之间有边的就有反向边关系矩阵：对称矩阵反对称关系：（若有相互关系则只能是同一个元素，不同元素间不能有相互关系）"x"y(x,yAxRyyRxx=y)关系图：两个节点之间只能有一条单向边关系矩阵：ci,j=1(ij)时cj,i=0传递关系："x"y"z(x,y,zAxRyyRzxRz)关系图：如果有边v1v2,vn-1vn，则有边v1vn注意：A上的空关系Æ是反自反的，不是自反的（此外是对称的、反对称的、传递的）如果A=Æ，那么A上的空关系就是自反的，同时也是反自反的，因为注意定义谓词的前件xA始终为假A上的相等关系EA既是对称的，又是反对称的即对于特殊集合、关系的判断要从定义式出发，注意前件的真假R自反当且仅当EAÍRR反自反当且仅当EARÆÍR对称当且仅当RÍRR反对称当且仅当RRÍEAR传递当且仅当R2ÍR运算的封闭性：如果关系R的某个性质经过关系运算后仍然保持，则称该性质对这个运算封闭（以上5个特性对交和求逆运算都封闭，自反对合成封闭）等价关系：等价关系R为A上的自反、对称、传递的二元关系等价类：设R为A上的等价关系，对于每个aA，a的等价类记做aR(简记a)，定义为：aR=x|xA xRa，a称作aR的代表元素划分：满足下列条件的集合A的子集族"B(B BÆ)（划分单元里没有空集）=A（所有划分单元合起来是全集）"B "B(BBBB B B=Æ)（划分单元两两不相交）中的元素称为划分的单元特别约定A=Æ时只有划分ÆA上的等价关系R的所有等价类的集合，构成A的一个划分，称作等价关系R对应的划分反过来，集合A的一个划分，也对应A上的一个等价关系R，称作划分对应的等价关系等价关系和划分的一一对应划分的“粗细”概念：如果1的每一个单元都包含于2的某个单元，称1细于2，表示为12；如果12而且12 ，则表示为12，称作“真细于”定理：1，2分别是等价关系R1，R2对应的划分，那么R1ÍR2 12定理说明，越“小”（包含二元组较少）的等价关系对应越细的划分；最小的等价关系是相等关系EA；最大的等价关系是全关系划分的运算：（结合图来很好理解）积划分运算：划分1和2的积划分12是满足如下条件的划分：12细于1和2；如果某个划分细于1和2，则一定细于12；也就是说， 12是细于1和2的最粗划分（”最小公倍数”）积划分对应于等价关系交运算和划分运算：划分1和2的和划分1+2是满足如下条件的划分：1和2均细于1+2；如果有划分， 1和2均细于，则1+2细于。也就是说， 1+2是粗于1和2的最细划分（“最大公约数”）和划分不对应于等价关系的并运算，而是对应于等价关系并运算结果的传递闭包二元关系R的传递闭包t(R)：t(R) 是传递的，RÍt(R)，对于A上的任意一个具有传递性质且包含R的关系R，t(R)ÍR商集：R是A上的等价关系，称A的划分aR|aA为A的R商集，记做A/RA/(R1R2 )=A/R1A/R2A/t(R1R2)=A/R1+A/R2序关系：R为集合A上的自反、反对称、传递的二元关系存在序关系R的集合A称作有序集（ordered set），用二元有序组<A, R>表示，一般的有序集表示成<A, >哈斯图：对序关系关系图的一种简化画法由于序关系自反，各结点都有环，省去；由于序关系反对称且传递，所以关系图中任何两个不同的结点直接不会有双向的边或通路，所以省去边的箭头，把向上的方向定为箭头方向由于序关系传递，所以省去所有推定的边，即ab,bc有ac，省去ac边元素排序：ab，称a先于或等于b；a小于或等于b；如果¬(ab)，则称a,b不可比较或者不可排序最大（小）元、极大（小）元（必须是B中元素）：<A, >为有序集，BÍAB的最小元b：bB"x(xBbx)（必须比每个B的元素都小于或等于）B的最大元b：bB"x(xBxb)（必须每个B的元素都比它小于或等于）B的极小元b：bB¬$x(xBxbxb)（比B中每个可比元都小于或等于）B的极大元b：bB¬$x(xBxbbx)（B中每个可比元都比它小于或等于）极大和最大的差别在于B中是否包含不可比较的元素最大（小）元必为极大（小）元；最大（小）元若有则唯一；极大（小）元恒存在未必唯一上（下）界，上（下）确界（只要是A中元素）：<A, >为有序集，BÍAB的上界a：aA"x(xBxa)（必须每个B的元素都比它小于或等于）B的下界a：aA"x(xBax)（必须比每个B的元素都小于或等于）B的上确界a：a是B的所有上界的集合最小元B的下确界a：a是B的所有下界的集合最大元最大（小）元是上（下）确界；属于B的上（下）界为最大（小）元；都未必存在链、反链半序关系：R为集合A上的反自反、反对称、传递的二元关系（即序关系除去每个元素与自己的关系）三、函数定义：如果X到Y的二元关系fÍX×Y，对于每个xX，都有唯一的yY，使得<x,y>f，则称f为X到Y的函数，记做：f:XY前域和定义域重合；单值性：<x,y>f<x,y>f y=yy=f(x)，称x为自变元，y为函数在x处的值，y为x的像点，x为y的源点（基于映射）XÆ时，空关系Æ不是函数，当XÆ时，空关系Æ是函数，称作空函数函数的规定方法：列表法、图标法、解析法、递归定义函数相等与包含函数个数：如果|X|=m，|Y|=n，则f|f:XY的基数为nm，共有nm个X到Y的函数。X到Y的全体函数集合表示为YX定义域子集的映象：f(A)=y|$x(xAy=f(x)（即定义域的一个子集A的值域）函数合成（恩，不写了。）单射：如果任意x1x2有f(x1)f(x2)。如果f和g都是单射函数，则其合成g°f也是单射函数。如果g°f是单射函数，则f是单射函数满射：如果任意y都有x使得y=f(x)，即Ran(f)=Y。如果f和g都是满射函数，则其合成g°f也是满射函数。如果g°f是满射函数，则g是满射函数双射函数：如果f既是单射函数又是满射函数，称作双射函数。如果f和g都是双射函数，则其合成g°f也是双射函数。如果g°f是双射函数，则f是单射函数，g是满射函数逆函数：只有双射函数存在逆函数左逆函数：如果g °f=EX，则称g为f的左逆函数右逆函数：如果f °g=EY，则称g为f的右逆函数f可逆当且仅当f既有左逆函数，又有右逆函数，而且左逆函数和右逆函数相等图论图：由结点和联结结点的边所构成的离散结构G=<V,E>结点集V（非空），边集E（多重集，可以有多个相同边）有向边：结点的二元有序组表示无向边：结点的两元素多重集表示有限图：V,E都有限集重边：重数大于1的边有重边的为重图，否则为单图简单图：无环无重边的无向图完全图：任意两个不同结点间都有边，Kn孤立结点、零图（只有孤立结点）赋权图：G=<V,E,f,g>，结点权函数：f:VW，边权函数：g:EW结点的度：d(v)定义为关联端点v的边的数目注意对有向图来说度d(v)=d+(v)+d-(v)度的总和为偶数，边数目的两倍；有向图出度等于入度悬挂点：一度的顶点正则图：所有顶点的度均相同的图称为正则图，按照顶点的度数k称作k-正则图，Kn是n-1正则图子图、真子图：边集结点集都必须为子集生成子图：结点集相同的子图补图：结点集相同，边集交集为空，并集为完全图图的同构：可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2（同分异构体）拟路径：v1,e1,v2,e2,v3,vl-1,el-1,vl，其中ei=<vi,vi+1>或者vi,vi+1，拟路径中的边数目称作拟路径的长度路径：拟路径中的边各不相同闭路径：v1=vl的路径通路：路径中的顶点各不相同回路：v1=vl的通路路径和通路定理：在有n个顶点的图G中，如果有顶点u到v的拟路径，那么u到v必有路径，并且必有长度不大于n-1的通路闭路径和回路定理：在有n个顶点的图G中，如果有顶点v到v的闭路径，那么必定有一条从v到v的长度不大于n的回路可达：u=v，或者存在一条u到v的路径连通的无向图：无向图中任意两个顶点都是可达的强连通的有向图：有向图中任意两个顶点都是互相可达的单向连通的有向图：任意两个顶点，至少从一个顶点到另一个是可达的弱连通的有向图：将有向图看作无向图时是连通的连通分支：图G的连通子图G，而且G不是任何其它连通子图的真子图（最大性）欧拉图：如果图G上有一条经过所有顶点、所有边的闭路径（允许顶点重复） 无向图：G连通，所有顶点的度都是偶数 有向图：G弱连通，每个顶点的出度与入度相等欧拉路径：如果图G上有一条经过所有顶点、所有边的路径（非闭）（允许顶点重复） 无向图：G连通，恰有两个顶点的度是奇数 有向图：G连通，恰有两个顶点出度与入度不相等，其中一个出度比入度多1，另一个入度比出度多1哈密顿图：如果图G上有一条经过所有顶点的回路（不要求经过所有边）哈密顿通路：如果图G上有一条经过所有顶点的通路（非回路）判定定理（充分非必要）：如果具有n个顶点的图G的每一对顶点的度数之和都不小于n-1，那么G中有一条哈密顿通路。如果G的每一对顶点度数之和不小于n，且n>=3，则G为一哈密顿图邻接矩阵：无重边的有向图G=<V,E>，其邻接矩阵AG定义为，aij=1, 当<vi,vj>E，aij=0, 当<vi,vj>ÏE注意：与关系矩阵的联系。拟路径，邻接矩阵自乘L次：AL，则乘积结果矩阵中每个分量aij(L)的含义为G中顶点vi到vj的长度为L的拟路径条数路径矩阵B=A A(2) A(3) A(|V|)，其中A(m)=A A AB的每个分量bij表示vi到vj是否有路径可达性矩阵：P=I B，加上顶点的自身可达性关联矩阵（简单无向图）：表示顶点和边的关联关系，n*m矩阵。通过矩阵的秩来判定图的连通分支个数二分图：满足如下条件的无向图G=<V,E>有非空集合X,Y, X Y=V, X Y= Æ每个vi,vjE，都有viXvjY或者viYvjX可以用G=<X,E,Y>表示二分图bipartite graph如果X,Y中任意两个顶点之间都有边，则称为完全二分图。记作K|X|,|Y|二分图的等价条件：G至少要有两个顶点，而且G中所有回路的长度都是偶数匹配：将E的子集M称作一个匹配，如果M中的任意两条边都没有公共端点。边数最多的匹配称作最大匹配。如果X(Y)中的所有的顶点都出现在匹配M中，则称M是X(Y)-完全匹配。如果M既是X-完全匹配，又是Y-完全匹配，称M是完全匹配*匈牙利算法：任取一个匹配，取非饱和点走交错路（边交替属于不属于已有匹配），若终点是非饱和点，则令匹配为原匹配和增广路的（即属于这两个集合但不属于交集部分）；若终点是饱和点，则将起点去掉不再考虑（我猜不会考）平面图：如果无向图G可以在一个平面上图示出来，并且各边仅在顶点处相交，称作平面图。K5和K3,3都不是平面图，K5是顶点数最少的非平面图，K3,3是边数最少的非平面图平面图等价条件：G或者G的子图作任何同胚操作（在原图的边上增加或者删除二度节点）后得到的图均不能以K5及K3,3为子图树：连通无回路的无向图称为树树中的悬挂点称作树叶非树叶节点称作分支点仅有单个孤立节点的树称作空树每个连通分支都是树的图称作森林（树也是森林）性质：简单、二分、平面顶点数比边数多1删去任意一条边就不连通生成树：如果图T是G的生成子图，且T是树。任意连通图G都至少有一棵生成树根树rooted tree递归定义一个孤立节点v0是根树，v0称为树根如果T1,T2,Tk是根树，其树根分别是v1,v2,vk，则V=V(T1) V(T2) V(Tk) v0；E=E(T1) E(T2) E(Tk) v0,v1 v0,v2 v0,vkT=<V,E>也是根树，v0称为树根Tn称为T的子树subtree，树根称为父节点parent，而子树的树根称为子节点childv1,v2,vk互称兄弟节点sibling根树中每个节点都是某个子树的根n元树：每个节点都至多有n个子节点的根树称作n元树二元有序树可以用来表示任何n元有序树：左子节点表示第一个子节点，右子节点表示下一个兄弟节点二元树的遍历：先根、中根、后根应用：表达式树、排序搜索树等抽象代数算术：研究整数、有理数、实数和复数的加、减、乘、除等运算代数：算术的一般化，允许用字母等符号来代替数进行运算代数结构：在一个对象集合上定义若干运算，并设定若干公理描述运算的性质非空集合S，称作代数结构的载体载体S上的若干运算一组刻画载体上各运算性质的公理抽象代数：抛弃代数结构中对象集合与运算的具体意义，研究运算的一般规律（交换、结合、分配），并对代数结构进行分类，研究其一般性质运算：Sn到S的一个函数，称为n元运算，常用*表示二元运算，常用表示一元运算运算的基本性质：（必须要满足）普遍性：S中的所有元素都可参加运算单值性：相同的元素运算结果也相同且唯一封闭性：任何元素参加运算的结果也是S中的元素二元运算一般性质：（可以不满足）结合律："x"y"z(x,y,zS x*(y*z)=(x*y)*z)交换律："x"y(x,yS x*y=y*x)*运算对#运算满足分配律："x"y"z(x,y,zS x*(y#z)=(x*y)#(x*z)幺元：<S,*>中的元素e，如果对任意x，满足"x(x*e=e*x=x)右幺元："x(x*er=x)左幺元："x(el*x=x)一般情况下，左右幺元可能是不同元素，也可能有多个如果存在幺元，那么幺元是唯一的，而且同时是左右幺元零元：<S,*>中的元素o，如果对任意x，满足"x(x*o=o*x=o)右零元："x(x*or=or)左零元："x(ol*x=ol)如果存在零元则唯一逆元：<S,*>中有幺元e，如果x*y=e，那么x称作y的左逆元，y为x的右逆元如果x*y=y*x=e，那么x,y互称逆元多于1个元素的载体集上零元没有逆元满足结合律的代数结构中，逆元唯一可约cancelable元素：<S,*>中元素a，如果对任意x,yS有a*x=a*y蕴涵x=y（左可约）x*a=y*a蕴涵x=y（右可约）那么a称为可约的满足结合律的代数结构中，有逆元的元素可约同类型代数结构：|S|=|S|；运算的元数相同同构的代数结构：存在S->S的一一映射h；S中运算的像等于运算数像在S的运算结果h(x*y)= h(x)*h(y)同态映射：对于代数结构<S,#>和<S,#>，如果有函数h:SS，对S中任意元素a,bh(a)= (h(a)，h(a#b)=h(a)#h(b)，这个函数h就称作代数结构S到S的同态映射如果h是单射函数，称作单一同态如果h是满射函数，称作满同态如果h是双射函数，称做同构映射同余关系：代数结构<S,*>中S上的一个等价关系，如果满足ab蕴涵ab，称是S上关于一元运算的同余关系；ab,cd蕴涵a*cb*d，称是S上关于二元运算*的同余关系。如果是代数结构上所有的运算的同余关系，则称是<S,*>上的同余关系半群：运算满足结合律的代数结构独异点：含有幺元的半群群：半群；有幺元；每个元素都有逆元交换群：满足交换律的群环：<R,+,*>，有两个二元运算，<R,+>是阿贝尔群，<R,*>是半群，*对+可分配：a*(b+c)=a*b+a*c域：<F,+,*>，<F,+,*>是环，<F-0,*>为交换群形式语言与自动机语言的定义：Chomsky:按照一定规律构成的句子和符号串的有限或者无限的集合形式语言主要研究语言描述的问题穷举法：只适合句子数目有限的语言语法描述：通过有限的替换规则，生成语言中合格的句子自动机：对输入的句子进行检验，区别哪些是语言中的句子，哪些不是语言中的句子字符串：设V是有限集合，其中元素称为“字符”由V中字符相连而成的有限序列称为“字符串”不含任何字符的串称为“空串”，记做字符串所包含的字符个数称为“长度”，记做|s|，|=0包括空串的V上的字符串全体记做V*字符串连接：s=ab,t=gg连接st=abgg字符串n次幂：s自身连接n次，s0=字符串集合的运算：乘积：AB=st|sA,tB幂运算：A0=，An=An-1A=AAn-1闭包：A*=A0A1A2正闭包：A+=A1A2=A*-正则表达式： RE1:是正则式，正则集 RE2:xV，x是正则式，正则集x RE3:如果、是正则式，则是正则式，正则集AB（字符串集合乘积） RE4:如果、是正则式，则(|)是正则式，正则集AB RE5:如果是正则式，则()*是正则式，正则集A*V上的正则表达式对应了V*的一个子集（正则子集）短语结构语法：是一个四元组G(V,S,v0,)V是字符集SÍV，称作终结符，N=V-S称作非终结符称作产生式关系，由ww这样的产生式构成，表示w可以替换成w，分别称为左部和右部v0N，称作初始符（句子符），是替换的起点直接导出关系（xy）：x=lwr, y=lwr, 且ww是产生式, l,rV*关系的传递闭包，wS*是语法正确的句子当且仅当v0 w导出的结果称作符合语法G的句子利用语法G产生的所有的正确构造的句子的集合称作为G的语言，记做L(G)导出树：用多元有向树表示语言导出过程。起始符v0作为树根，每个子树的树根是某个生成式的左部，子节点分别是生成式右部包含的符号，适合所有产生式的左部仅有一个非终结符情形乔姆斯基形式语法分类：0型语法：如果对产生式没有任何约束（无限制语法，短语结构语法PSG）产生递归可枚举语言，被图灵机识别1型语法：如果所有产生式形如A （A是非终结符，,是任意串，但不能为空串）（上下文相关语法CSG）产生上下文相关语言，被线性有界自动机识别2型语法：如果所有产生式左部是一个非终结符，形如A（可以是任意串），（上下文无关语法CFG）产生上下文无关语言，被下推自动机识别为大多数程序设计语言的语法提供理论基础3型语法：如果所有产生式左部是一个非终结符，右部最多有一个非终结符，而且只能在最右端（正则语法RG）产生正则语言，被有限状态自动机识别，也可以用正则表达式表示通常用来定义检索模式或者程序设计语言中的词法结构如果某个语言可以用某型语法产生，则称作某型语言。L3 Ì L2 Ì L1 Ì L0语言导出的逆过程：从一个句子得到导出树或导出过程BNF（Backus-Naur Form）范式：形式简单，仅包含三个符号：“:=”，定义为；“|”，或；“<>”，用来区分非终结符可以表示2、3型语法（上下文无关、正则）产生式左部仅有一个非终结符相同左部的产生式合并用“|”隔开非终结符用“<>”标记注意：课件上的例子，便于直接记忆递归出现一次，并在最右，称为正规的，3型语法中的递归产生式都是正规的BNF例子：“十进制数” <十进制数>:=<无符号整数> | <小数> | <无符号整数><小数> <无符号整数>:=<数字> | <数字><无符号整数> <小数>:=.<无符号整数> <数字>:=0|1|2|3|4|5|6|7|8|9扩展BNF：可选项：用“”表示，如<if语句>:=if <逻辑表达式> then <语句> else <语句> end if;重复项：用“”表示重复0次或者多次，如<标识符>:=<字母><字母>|<数字>便于区分单个符号的终结符，加引号，如<语句序列>:=<语句> “;” <语句> 有时也用粗体字表示终结符，非终结符不加尖括号，可读性更好语法图：用方框表示非终结符，用圆表示终结符用带箭头线表示连接关系和连接顺序也注意看课件上例子右图：十进制数的例子正则语法和正则表达式：S是有限集合，LÍS*。则L是正则集合，当且仅当对某个正则语法G，有L=L(G)从正则语法G构造对应正则集合的正则表达式主导图：将G的语法组合为一个大图，其中仅包含v0和终结符。图中终结符对应正则表达式中的终结符 串联子图，对应子表达式12 并联子图，对应子表达式1|2 回路子图，对应子表达式*有限状态机FSM：机器是一个系统，接受输入，改变自身的状态，产生输出。状态指为了完成机器的任务而对输入序列进行的归类，如果状态的数目有限，称为有限状态机有限状态机FSM是一个五元组M(A,S,Y,s0,F) A:输入字符串的字母表 S:机器的有限状态集合 YÍS:被称作“接受”的一些状态 s0S:初始状态 F:S×AS：状态转移函数，指明在某个状态下接受输入字符所引起的状态变迁状态图：状态图D=D(M)是带标记的有向图，节点为状态，转移函数决定边的走向和标记接受状态用双圈表示如果F(sj,a)=sk，则从节点si做标记为a的有向边到节点sk初始状态s0用一个特殊的无源箭头标识有限状态机M决定的语言L：M所识别的A上的所有字符串。也就是确定拟路径P=(s0,a1,s1,a2,s2,am,sm)，如果smY则称M识别wKleen定理：字母表A上的形式语言L是正则的当且仅当存在一个有限状态机M使得L=L(M)泵Pumping引理：长度超过状态数目的接受串w，都可以表示成w=xyz形式，而xynz都会被M接受（鸽笼原理）*应用：证明：L=ambm:m>0不是正则语言 假设L是正则语言，则有有限状态机M接受L，假设M状态个数为k 令w=akbk，则一定有|w|>k，根据泵引理，w=xyz，其中y非空，而且xy2z也被M接受 如果y仅含有a或仅含有b，那么xy2z中a,b的个数就不相等了，应该不属于L 如果y同时含有a和b那么y2中一定会出现a在b之后的情况， xy2z也应该不属于L 两个矛盾说明假设错误，L不是正则语言机器同余：是一个等价关系R对于任意的s,tS，如果sRt，能导出对于任意的输入符号xA，都有F(x,s)RF(x,t)。即：同一个等价类的状态对于任意的输入都转移到属于同一个等价类的状态。机器同余表现了状态之间的某种等效性商机器：相对于有限状态机M(A,S,F)和M上的机器同余R。S=S/R=s|sS是S关于等价关系R的划分，F= <s, F(x,s)> | sS,xA。M(A,S,F)称为M关于R的商机器M/R机器化简：状态数目最少的机器为最简，通过构造机器同余及商机器来合并这些冗余状态，减少状态数目。字符串相容的状态：s,tS，wA*，如果F(s,w)Y并且F(t,w)Y；或者F(s,w)ÏY并且F(t,w)ÏY，称s,t是关于w相容的等价关系：S上的关系R，如果s,tS对于任何wA*都相容，则sRt，说明s,t其实是等效的状态R是机器同余，M/R即M化简的结果R的迭代算法：S的初始划分P0=Y, Y假设目前已有划分Pk=S1,S2,Sm，考察每个等价类Si，如果Si中的两个状态s,t在所有的输入x作用下都转移到同一个状态分块Aj（取决于x），则据此构造Si的进一步细分将所有Si的细分合在一起，成为新的划分Pk+1如果Pk+1=Pk，算法停止，否则回到第2步注意课件例子，有助理解计算的实现：带输出的机器：在有限状态机M(A,S,Y,s0,F)的基础上，去掉接受状态集合Y，增加 输出字符的有限集合Z 输出函数G:S×AZ（在状态转移的同时，输出一个字符）M的工作方式：输入字符串u=a1a2am印在一条输入带上，机器M逐个读入输入带的字符，进行状态转移V=s0s1s2sm，同时在输出带上逐个打印输出字符w=z1z2zm例：二进制加法有限状态机有限状态机的局限：不存在能作二进制乘法的有限状态机计算机的内存有限，属于一种有限状态机如果宇宙是有限的，理论上也是有限状态机图灵机：（计算概论讲过）基本结构 一条分格的无限长的纸带，每格可容纳一个字符 一个读写头，可以在纸带上移动，读出当前格子的字符，重写格子上的内容，改变自己的内部状态 一系列关于读写头动作的规则（程序）输入、计算和输出 纸带上的内容（包括空白B）是计算前的输入和计算完成后的输出 计算从读写头的初始状态s0、初始位置和输入的纸带格局开始 按照规则进行读写头的移动、纸带字符的修改，直到进入停机状态（SH/SY/SN） 在停机状态时纸带的内容就是输出计算规则规则q=si,ak,al,sj,d，si,sjS（内部状态），ak,alA（纸带字符），dL,R,N（左移，右移，不动）。表示如果读写头当前状态为si，读到当前格子字符为ak，则： 改写格子内容为al 转变状态为sj 进行d指定的动作（读写头左移、右移或不动）计算规则的限制有限条规则任意两条规则前两项不能相同（动作的确定性）没有规则第一项是SH/SY/SN（保证这三个状态是停机状态）形式语言与图灵机当WÍA*，将W中的任意字符串w作为输入，M都停止在接受状态SY，A-W的字符串M停止在拒绝状态SN或者永不停机，称M接受/识别语言W=L(M)形式语言L能被图灵机M识别，当且仅当L是一个0型形式语言*图灵机例子：ambm课件识别与判定识别：属于语言的串在有限步被接受，不属于语言的串被拒绝或者永不停机枚举：枚举生成所有属于语言的串，对于无限集合语言，这个生成过程可能永不停止，可识别可枚举判定：属于语言的串被接受，且不属于语言的串被拒绝（只有L和L的补语言都是图灵可识别的情况下，L才是图灵可判定的。）存在语言是图灵机可识别但不可判定的可计算函数：函数f:NN是可计算的，如果存在一个图灵机M使得对每个自然数n停机，输出为f(n)如果f,g都是可计算的，那么复合函数h=g°f也是可计算的可计算函数递归函数保证能停机并得到结果原始递归函数包括了多数可形式化的计算从0函数、后继函数、投影函数进行有限次的复合、原始递归存在非原始递归的可计算函数可计算函数Ì图灵可计算函数（存在图灵可计算但不是递归函数，和停机问题相关）哥德尔编码：将任何形式语言L编码为自然数的集合（将语言上的运算变换为自然数的运算，形式系统的问题变换为数论问题）哥德尔编码过程：定义p(n)=第n个素数，n>0LÍA*，A=a1,a2,an，任意w=am1am2.amkL，G(w)=Õi=1kp(i)mi通用图灵机：能模拟任意图灵机的执行，对相应的输入得到相应的结果图灵机的编码：图灵机的定义包含有限字符集A、有限状态集S和读写头的运动规则对图灵机的描述就是一个ASL,R,N上的字符串将这个字符串进行哥德尔编码，得到哥德尔数G(M)输入、输出的编码：对图灵机的输入、输出是A上的字符串，也可以进行哥德尔编码通用图灵机U存在：接受两个输入整数a, k（a是图灵机的哥德尔数，k是图灵机输入的哥德尔数）计算结果是M(a)在输入I(k)下的输出结果的哥德尔数G(o)U所计算的函数是U(a,k)N有趣的是，U本身也可以进行哥德尔编码，作为输入参数在U中进行计算（可以产生能够自我复制的图灵机）停机问题：是否有算法能够判定某个图灵机M在输入I下是否停机？答案是否定的，不存在这样的算法，停机问题是不可计算问题哥德尔不完备定理：任何包含自然数定义的形式系统都是不完全的，也就是存在不能证明为真也不能证明为假的命题重点是证明，一个开始于公理，结束于此命题的公理-定理有限序列也就是，系统可能存在一些命题，它们是定理，却无法给出证明序列可证明 v.s. 计算停机不可判定的命题 v.s. 永不停机的计算