《形式语言与自动机理论 》考研全册配套完整教学课件1

《形式语言与自动机理论》考研全册配套完整教学 课件 超市陈列培训课件免费下载搭石ppt课件免费下载公安保密教育课件下载病媒生物防治课件 可下载高中数学必修四课件打包下载 1《形式语言与自动机理论》第0章引言0.1、课程绪论0.2、语言及其 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示0.3、文法0.4、文法分类0.5、识别程序----自动机0.6、课程内容介绍0.1、课程绪论：形式语言：大约于1956年问世，NoamChomsky给出了一种文法的数学模型，而后，用CFG文法描述ALGOL语言，最后导致了形式语言与自动机理论的研究。形式语言---研究字符串集合及其性质的学科计算机处理的主要对象语言自然语言(字符串)人工语言（符号串）自然语言：人与人之间交流的基本手段。如：汉语、英语、俄语、法语、…等人工语言：主要用于人与计算机之间的交流。如：程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 语言（也有例外，如世界语）形式语言：研究自然语言和人工语言都必须遵循的一般规律自动机：语言（形式语言）识别器可见，本课程是计算机科学的基本理论1、编译理论的发展过程：汇编==〉编译或解释==〉CCCompiler(YACC)上述过程中无不运用某些形式语言的理论结果。2、形式语言的研究价值。（1）程序语言的设计（2）Compiler技术方法改进（3）计算复杂性：算法与自动机（4）NP问题（多项式时间复杂度问题）（4）人工智能技术发展：专家系统中知识表示（规则表示）及推理（规则推导）程序正确性证明，前置条件==〉结果分析软件自动生成，如CCCompiler、应用软件自动构造技术等自然语言理解，语言识别及分析技术3、形式语言与自动机关系形式语言研究引入了自动机进行语言识别。自动机就是一种自动识别句子的构造或程序。形式语言中的文法与自动机之间存在不可分割的关系。每一种文法（四种典型文法）《=====》一种自动机4、本课程只介绍一般的形式语言基本概念和理论“入门性”《参考书》1、《计算理论基础》（第二版），HarryR.L.,ChristosH.P.，清华大学出版社，1999年9月2、《计算理论基础》（第2版）中文翻译版，张立昂、刘田译，清华大学出版社，2000年7月3、《形式语言与自动机理论》吴哲辉，吴振寰编著，机械工业出版社，2007年4月4、《形式语言与自动机理论教学参考书》，蒋宗礼，清华大学出版社，2007年7月5、《形式语言及其与自动机的关系》，[美]J.E.霍普克罗夫特，J.D.厄儿曼著；莫绍揆、段祥、顾秀芳译，科学出版社出版，1979年6、《形式语言及其句法分析》，[美]A.V.阿霍，J.D.厄儿曼著，石青云译科学出版社出版，1987年7、无论其它有关形式语言与自动机理论的书。0.2、语言及其表示提要：本节将从一般的观点来讨论定义语言的两种主要方法：产生程序和识别程序。产生程序主要介绍Chomsky文法，而识别程序则介绍各种已研究过的识别程序。1、过程和算法在讨论有穷表示的概念以前，我们非形式地介绍一下过程和算法。一个过程就是一个能被机械地执行的指令有穷系列。如一个计算机的程序。总是要终止的过程叫做算法。2、语言的表示语言定义：（非形式）一个语言L是在某个有限字母表∑上的有限长符号串的集合。1）罗列法：当L由有限符号串组成时，则一个显然的表示法是把L中所有的符号串罗列出来。L为无穷集时，怎么表示？假定要求（规定）语言的表示是有限的。2）产生系统：也称为文法系统。即可给予一种算法或过程，它依某种次序可系统地依次产生语言的句子。优点：文法==〉句子结构≡≡≡≡〉句法分析和翻译简单3）识别法：给出一个过程，当输入一个任意的符号串时，它能判定该符号串（或句子）是否在语言中。实际上，我们必须要求该过程是一个算法。什么是语言理论？语言理论就是对符号行的集合、它们的表示法、结构以及特性的研究。0.3、文法1、启示自然语言研究：文法的概念由语言学家在研究自然语言的过程中形式化了的。他们不但关心正确句子的识别，而且也关心提供句子的结构性描述。目的：目标之一是发展一种能够描述自然语言(英语)的形式文法，从而解决自然语言的计算机化理解、翻译和解决文字问题。但目前自然语言研究还不成熟，而计算机语言形式化已经成熟。例1.1Thelittleboyranquickly。<句子><名词短语><动词短语><名词短语><形容词><形容词><单名词><单动词><副词>ThelittleboyranQuickly.图1、句子分析图解句子分析分析上述句子的规则如下：<句子>→<名词短语><动词短语><名词短语>→<形容词><名词短语><名词短语>→<形容词><单个名词><动词短语>→<单个动词><副词><形容词>→The<形容词>→little<单个名词>→boy<单个动词>→ran<副词>→quickly注意：①目的：我们不但要能够检查句子的语法是否正确，而且还要能产生语法上正确的句子。②方法：从<句子>开始，利用规则到结束。这样可以导出无穷多个句子中任何一个句子。③一般形式：{The,little}+╳{boyranquickly}例如：littleTheTheboyranquickly.这里，虽然大部分句子都没有意义，然而在广义上说还是语法上正确的句子。2、文法的形式概念文法是语言的产生程序中最重要的一类，一个文法是定义语言的一个数学系统。这里，我们先考察一类文法，也称为乔姆斯基文法或短语结构文法。（0型文法）1）一个语言的文法需要用两个不想交的符号集：终结符∑与非终结符N2）文法的核心是产生式规则集P：（N∪∑）*N（N∪∑）*╳（N∪∑）*3）文法定义：约定：如果(α，β)是一个产生式，则用缩写α→β来表示。定义：一个文法是一个四元组G=（N，∑，P，S），其中：（1）N是非终结符的有限集（变量集或句法种类集）。（2）∑是终结符的有限集，与N不相交。（3）P是（N∪∑）*N（N∪∑）*╳（N∪∑）*的有限子集，（α，β）∈P，可以写成：α→β；称为一个产生式。（4）S是N的一个特定符号，称为句子符或起始符。例子1.2G1=（{A,S}，{0,1}，P，S）是一个文法，其中：P有下列产生式组成：S→0A10A→00A1A→e这里，非终结符是A和S；终结符是0和1。问题：1、该语言是什么样？2、如何修改更简单？[讨论]句子形式：一个文法按递归方式定义语言。递归地定义如下：（1）S是一个句子形式。（2）如果αβγ是一个句子形式，且β→δ是P中的产生式则αδγ也是一个句子形式。或，则α叫作句型。其中α∈（N∪∑）*句子：文法G的不含非终结符的一个句子形式称由G生成的一个句子。语言：由文法G生成的语言记为L(G)，它是由G生成的所有句子的集合。即：L(G)={w|w∈∑∧}S==>α*S==>w*G0.4、文法分类按文法的产生式形式可以对文法进行分类。乔姆斯基（Chomsky）文法分为四类：即0型、1型、2型、3型[0型][1型][2型][3型]-------依次条件强硬[0型文法]设G=（N,∑,P,S）为一文法，若其产生式均为如下结构：α→β其中:α（N×）*，且至少含有一个非终结符。β（N×）*则称此文法为0型文法。或称短语文法，或无(条件)限制文法。如果对0型文法分别加上下列第i条限制，则就可得到相应的i型文法：1、若α→β∈P，则，仅S→e例外（空句子）。2、对于任何α→β∈P，则α=A∈N，β∈（N×）*3、P中任何产生式均为A→αB，A→α；其中：α∈*，A,B∈N文法分类：0型文法：若α→β∈P，其中α,β（N×）*，称为无限制文法，或称短语文法。1型文法：若α→β∈P，则，称为上下文敏感的，或前后文有关文法。2型文法：若α→β∈P，则α=A∈N，β∈（N×）*，称为上下文无关的，或前后文无关文法。3型文法：若P中产生式均为A→αB，A→α；其中：α∈*，A,B∈N；称为右线性的，或正规文法。例子1.2是一个上下文有关的文法，即1型文法。(可改造成3型)例子1.3一个文法具有下列产生式规则：S→0S|1S|e此文法生成的语言是{0，1}*。该文法是一个右线性文法，即3型文法。约定：如果语言L能由x型的文法生成，就称L是x型语言。比如：L(3)就由3型文法生成的语言，也就是3型语言。语言集合之关系：L(3)L(2)L(1)L(0)0.5、识别程序----自动机自动机与文法、语言的关系。对语言提供有限规定的另一种常用方法：对语言定义一个识别程序。也就是定义一个集合的高度格式化过程。1、识别程序的组成识别程序有三个部分：a）一个输入磁带（字母表的线性序列）b）一个有限状态控制c）一个辅助存储（按某种结构组织的存储字母集合）a0a1a2a3……an…有限状态控制辅助存储输入头输入磁带图示一个识别程序其中：输入头，一次可读一个字母（方格）识别程序的一次移动：左移一格、不动、右移一格辅助存储：可由两个函数（即存函数和取函数）来刻画其性能。例如：下推表。取函数f：---为存储字母表f（Z1Z2…Zn）=Z1-----唯一能取最上端符号存函数：假定用一个有限长符号串代替下推表最上端的符号。g：**g（Z1Z2…Zn,Y1…Yk）=Y1…YkZ2…Zn辅助存储的类型决定一个识别程序的名称。如：以下推表为辅助存储的识别程序称为：下推识别程序（或叫下推自动机）。识别程序的核心是一个有限状态控制。可表示为状态的一个有限集，连同一个描述状态如何随当前输入符号（输入头处符号）和取自辅助存储的当前信息而改变的映射。同时，也决定输入头移动及存储什么信息。识别程序的运算是作一系列移动。移动：①输入头向左移、向右移、保持不动。②将信息存入辅助存储。③改变控制的状态。组态：一个识别程序的行为可由其组态来描述。组态描述：①有限控制的状态。②输入磁带的内容，以及输入头的位置。③辅助存储的内容。确定性的：在每一组态中最多存在一个可能的移动。有限控制：非确定性的：在每一组态，移动不只一种，而属于一个有限集。①有限控制处于特定的初始状态。初始组态：②输入头处在最左边的符号。③辅存中有特定的初始内容。①有限控制处于特定的最终状态集中一个状态。最终组态：②输入头处在右边的结束标记。③辅助存储也满足一定的条件（最终）。接受符号串w：在输入串w的条件下，能够从初始组态开始作一系列移动，（确定性）并结束于一个最终组态，则称该识别程序接受输入符号串w。接受符号串w：识别程序从初始组态开始，作许多不同的移动序列。只要其中（非确定性）至少有一个序列结束于一个最终组态，则认为符号串w被接受。例1.4设M是确定型有穷自动机(K,,,s,F)，没有存储能力。其中：K={q0，q1}，={a，b}，s=q0，F={q0}，是状态转移由右表给出的函数。可以看出L(M)是有偶数个b的{a,b}*串。如果给Ｍ输入aabba，则它的初始格局为(q0，aabba)。于是(q0，aabba)├M(q0，abba)　　├M(q0，bba)　　├M(q1，ba)　├M(q0，a)　├M(q0，e)因此(q0，aabba)├*M(q0，e),从而aabba被Ｍ接受。一般的，转移函数可以表示成状态图形式，右上表对应的状态图如右下。qσ(σ)q0aq0q0bq1q1aq1q1bq0aabbq0q1状态图语言：由一个识别程序定义的语言就是它所接受的输入符号串的集合。Chomsky语言有下列特性：1、语言L是右线性的[3型]，当且仅当L由一个（单向确定性）有限自动机所定义。2、语言L是上下文无关的[2型]，当且仅当L由一个（单向非确定性）下推自动机所定义。3、语言L是上下文敏感的[1型]，当且仅当L由一个（双向非确定性）线性有界自动机所定义。4、语言L是递归可数的[0型]，当且仅当L由一个图灵机所定义。最后，关于识别程序的精确定义可在我们课程教材中详细讨论。本课程主要教学内容第一章集合、关系和语言第二章有穷自动机。主要介绍“确定型有穷自动机”、非确定型有穷自动机及其与正则语言关系。讨论了状态最小化和有关算法。第三章上下文无关语言。介绍“下推自动机”与上下文无关文法、语言；讨论有关算法、确定性与语法分析等。第四章图灵机（Turing）。介绍一般图灵机，引入随机存取图灵机和非确定型图灵机，讨论了图灵机计算、文法与数值函数。第五章不可判定性。讨论停机问题、与图灵机和文法有关的不可解问题、递归函数论等。第六章计算复杂性。介绍P类（多项式可判定的语言类）和NP类的复杂性问题，建立形式化数学理论来刻画算法的实际可行性。第七章NP完全性。（相对独立章）讨论有关NP完全性问题。第1章集合、关系和语言1.1、集合1.2、关系与函数1.3、特殊类型的二元关系1.4、有穷集合与无穷集合1.5、三个基本的证明技术1.6、闭包与算法1.1、集合集合：对象的汇集。如：L={a,b,c,d}就是四个字母的汇集形成的集合。元素或成员：构成集合的所有对象。如：b是集合L的一个元素，表示成：b∈L另一方面z不是L的元素，记作：zL单元素集：集合中只有一个元素，即有一个元素构成的集合。空集：集合中没有一个元素，用○表示。集合元素性质定义：设集合A已经定义，P是A的元素具有的性质，则可以定义一个新集合B如下：B={x:x∈A且x具有性质P}子集：如果集合A的每一个元素都是集合B的元素，则称A是B的子集，记作：AB真子集：如果AB，但A≠B，则称A是B的真子集。集合的性质：设A、B和C是集合，则下述算律成立1、幂等率A∪A=AA∩A=A2、交换律A∪B=B∪AA∩B=B∩A3、结合律(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)4、分配律(A∪B)∩C=（A∩C)∪(B∩C)(A∩B)∪C=（A∪C)∩(B∪C)5、吸收律(A∪B)∩A=A(A∩B)∪A=A6、DeMorgan律A-(B∪C)=(A-B)∩(A-C)A-(B∩C)=(A-B)∪(A-C)幂集：集合A的所有子集的汇集本身是一个集合，叫做A的幂集记作：2A非空集合的划分：如果∏是A的一些子集的集合，使得满足(1)∏的每一个元素非空，即非空集合；(2)∏的不同元素是不相交的；(3)∪∏=A，其中∪∏表示∏中所有元素的汇集则∏是A的一个划分。例如：{(a,b),{c},{d}}是{a,b,c,d}的一个划分；奇自然数集合和偶自然数集合构成自然数N的一个划分。1.2、关系与函数有序对：由两个元素构成的对，前后有别。如a和b的有序对记作(a,b)，a和b叫做它的分量。迪卡儿积：两个集合A和B的迪卡儿积是a∈A且b∈B的所有有序对(a,b)构成的集合，记作A×B。二元关系：两个集合A和B的二元关系是A×B的子集。有序组：设n是任一自然数，如果a1,a2,…,an是任意n个对象，也可以有相同对象，则(a1,a2,…,an)是一个有序组。n叫做序列长度。从而就有：有序2元组、有序3元组、。。。有序n元组n元关系：集合A1,…,An上的n元关系就是A1×。。。×An一个子集。即有序n元组的集合。函数：集合A到集合B的函数是A和B上的具有下述特殊性质的二元关系R:对于每一个元素a∈A，在R中恰好存在一个有序对以a为第一分量，第二分量b∈B。一般的，设f:A1×…×An|—B是一个函数，f(a1,…,an)=b，其中：ai∈Ai，且b∈B，有时称a1,…,an是f的自变量，b是f对应的值。一对一：如果对任意两个不同的值a,a’∈A，f(a)≠f(a’)则称函数f:A|—B是一对一的。满射：如果B的每一个元素都是A的某一个元素在f下的值或叫象，则称函数f:A|—B满射到B。双射：如果函数f:A|—B既是一对一的，又是满射到B的，则称f是A与B之间的双射。二元关系R的逆：记作R-1，R-1={(a,b):(b,a)∈R}显然，若RA×B，则R-1B×A。关系合成：设Q和R是两个二元关系，他们的合成Q。R(简记QR)为:QR={(a,b):对于某个c，(a,c)∈Q且(c,b)∈R}注意：两个函数f:A|—B和g:B|—C的合成是一个函数h:A|—C，使得对每一个a∈A，h(a)=g(f(a))1.3、特殊类型的二元关系1、A×A的二元关系设A是一个集合，RA×A是A上的一个二元关系，可以用一个有向图表示关系R。A的每一个元素用一个小圆圈表示(叫做有向图的顶点)，从a到b画一个箭头当且仅当(a,b)∈R，这些箭头是该有向图的边。例如：用图1-1中图表示关系R={(a,b),(b,a),(a,d),(d,c),(c,c),(c,a)}adcb图1-1二元关系的有向图表示自反关系：如果对于每一个a∈A，(a,a)∈R，则称关系RA×A是自反的对称关系：如果只要(a,b)∈R就有(b,a)∈R，则称关系RA×A是对称的没有(a,a)形式的有序对的对称关系可以表示成无向图或称图。反对称关系：如果当(a,b)∈R且a≠b时，(b,a)R，则称关系R是反对称的传递关系：如果只要(a,b)∈R且(b,c)∈R就有(a,c)∈R，则称关系R是传递的等价关系：把自反、对称、传递的关系叫做等价关系。如书上图1-6。等价类：表示等价关系的无向图由若干个集团组成，把等价关系的这种集团叫做等价类。定理1.3.1设R是非空集合A上的等价关系，则R的等价类构成A的一个划分。（证明：利用等价关系性质采用反证法，略）另外，由于二元关系R可以表示成图，所以也有类似于图的通路、长度、圈。1.4、有穷集合与无穷集合等势：如果存在双射函数f:A|—B，则称集合A与B等势。有穷集合：一般的，如果对某个自然数n，一个集合与{1,2,…,n}等势，则称这个集合是有穷的。无穷集合：如果一个集合不是有穷的，则称它是无穷的。例如：自然数集合N是无穷的；整数集合、实数集合都是无穷的。可数无穷的：称与N等势的集合是可数无穷的。可数的：称有穷集合或可数无穷集合是可数的。（可枚举的）相反，不是可数的集合称为不可数的。另外，要证明集合A是可数无穷的，必须给出A与N之间的一个双射函数f。见书1.5、三个基本的证明技术1、数学归纳法的原理如果A是一个自然数的集合使得：（1）0∈A；（2）对于每一个自然数n，{0,1,…,n}A蕴函n+1∈A;则A=N非形式地说(数学归纳法的原理)：任何一个包含0的自然数集合，如果它具有下述性质：它只要包含所有小于等于n的自然数就包含n+1，则它实际上就是全体自然数的集合。一般的，用归纳法证明下述断言：“对于所有的自然数n，性质P成立。”用下述方式把数学归纳法原理应用于集合A={n:对于n，P为真}：（1）基础步骤：证明0∈A，即对于0，P成立。（2）归纳假设：假设对任意固定的n≥0，P对于0,1,…,n成立。（3）归纳步骤：利用归纳假设证明P对于n+1成立，于是根据归纳原理，A等于N，即P对于每一个自然数成立。2、鸽巢原理鸽巢原理：设A和B是两个有穷集合，且|A|＞|B|，则不存在从A到B的一对一的函数。换句话说，如果企图把A的元素(“鸽子”)与B的元素(“鸽巢”)配对，迟早不得不把一只以上的鸽子放入一个巢里。鸽巢原理可以用第一个基本原理---数学归纳法证明。(见书上)定理1.5.1设R是有穷集合A上的二元关系，a,b∈A。如果在R中有一条从a到b的通路，则有一条长度不超过|A|的通路。证明：假设(a1,a2,…,an)是从a1=a到an=b的最短通路，即长度最小的通路，又假设n＞|A|。由鸽巢原理，A有一个元素重复出现在这条通路上，比如说ai=aj，1≤i＜j≤n。于是，(a1,a2,…,ai,aj+1,…,an)是另一条更短的从a到b的通路，这与假设(a1,a2,…,an)是从a到b的最短通路相矛盾。(完毕)3、对角化原理对角化原理：设R是集合A上的二元关系，D={a:a∈A且(a,a)R}称为R的对角线集合。对于每一个a∈A，令Ra={b:b∈A且(a,b)∈R}，则D与每一个Ra都不相同。即，把R看成一个正方阵列，对角线的补与每一行都不同。（见书上例1.5.3）理由：关于a是否是元素的问题，对角线集合D与Ra集合总是不同的。若a∈D，则必然(a,a)R；若a∈Ra，则必然(a,a)∈R;矛盾！即对角线上无关系的元素所在行自然不相等；对角线上有关系的元素又多余该对角线上元素。定理1.5.2集合2N是不可数的。（自然数的幂集）证明：(大概思路)利用反证法假设它是可数无穷的，再利用对角线原理证明假设不成立。略，见书。1.6、闭包与算法定义1.6.1设RA2是集合A上的有向图。R的自反传递闭包是关系R*={(a,b):a,b∈A且在R中存在从a到b的通路}例子见书图1-9，构造算法见P17下定义1.6.1函数的增长率：算法随问题规模变化的增长规律。(1)所有次数相同的多项式具有相同的增长率。(2)nd≤2n≤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元关系，其中n≥0。又设B是D的子集。如果只要b1,…,bn∈B且(b1,…,bn,bn+1)∈R，就有bn+1∈B，则称B在R下是封闭的。任何“集合B在关系R1,R2,…,Rm下是封闭的”形式的性质称为B的封闭性。定理1.6.1设P是由集合D上的关系定义的封闭性，A是D的子集，则有唯一的包含A具有性质P的极小集合B。（证明：略）闭包：定理1.6.1中的B是A在关系R1,…,Rm下的闭包。关于形式语言及表示我们前面已经讨论过。下面我们简单地讨论一下语言的有穷表示-----正则表达式与正则语言1.7语言的有穷表示-----正则表达式与正则语言计算理论中一个核心问题：用有穷的规定说明表示无穷语言。例1.8.1令L={w∈{0,1}*：在w中1出现两次或三次，并且第一次和第二次不相邻}这个语言可以只用单元集和语言运算符号∪、。、*描述如下：{0}*。{1}。{0}*。{0}。{1}。{0}*(({1}。{0}*)∪⊙*)进一步简单地写成：L=0*10*010*(10*∪⊙)---------正则表达式正则表达式定义：字母表上的正则表达式是字母表∪{(,),⊙,∪,*}上可以如下获得的所有字符串：(1)、⊙和的每一个成员是正则表达式。(2)、如果α和β是正则表达式，则(αβ)也是正则表达式。(3)、如果α和β是正则表达式，则(α∪β)也是正则表达式。(4)、如果α是正则表达式，则α*也是正则表达式。(5)、除上述(1)-(4)得到之外，没有任何别的正则表达式。如果α是任意一个正则表达式，则L(α)是α表示的语言。即L是从字符串到语言的函数。函数L的定义：(1)、L(⊙)=空集；对于每一个a∈，L(a)={a}(2)、如果α和β是正则表达式，则L((αβ))=L(α)L(β)(3)、如果α和β是正则表达式，则L((α∪β))=L(α)∪L(β)(4)、如果α是正则表达式，则L(α*)=L(α)*例1.8.2L(((a∪b)*a)是什么？计算如下：L(((a∪b)*a)=L((a∪b)*)L(a)----由(2)得到=L((a∪b)*){a}----由(1)得到=L((a∪b))*{a}----由(4)得到=(L(a)∪L(b))*{a}----由(3)得到=({a}∪{b})*{a}----由(1)两次得到={a,b}*{a}={w∈{a,b}*：w以a结束}。例1.8.3(c*(a∪(bc*))*)表示的语言是什么？----该正则表达式表示{a,b,c}上不含子串ac的所有字符串的集合。正则语言：定义字母表∑上的正则语言类由所有可写成L=L(α)的语言L组成，其中α是∑上的任一正则表达式。即，正则语言是所有能够用正则表达式描述的语言。也就是，∑上的正则语言类恰好是语言集合{{a}：a∈∑}∪{⊙}关于并、连接和Kleene星号函数的闭包。语言识别装置：专门为某个语言L设计的、用来回答“字符串w是L的成员吗？”这样的问题的算法。例如，识别语言L={w∈{0,1}*：w不含子串111}的装置运算如下：从左到右读字符串，每次读一个。有一个计数器，开始时为0，每当在输入串中遇到0时将它置回到0，每当遇到1时加1。如果计数器已经达到3，则停止计算并且回答“No”；如果读完整个字符串且计数器没有达到3，则停止计算并且回答“Yes”。语言识别装置和语言生成器是语言有穷说明的两种类型。本课程后续将研究两者之间的关系。（完）第二章有穷自动机2.1确定型有穷自动机2.2非确定型有穷自动机2.3有穷自动机与正则表达式2.4正则语言与非正则语言2.5状态最小化2.6关于有穷自动机的算法一、有穷自动机概念一个受到严格限制的实际计算机模型，有一个固定的、能力有限的“中心处理装置”。它接收输入，输入是一个字符串并且被传送到输入带上。没有输出，只给出是否接受这个输入的信号。换句话说，它是一种语言识别装置。有穷自动机（FA）是具有离散输入输出系统的数学模型。这种系统内部状态数目是有限的。系统的状态概括了对过去输入处理状况的信息。系统只需要根据当前所处的状态和面临的输入就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生变化。使有穷自动机成为这种受限制的模型的关键是：除固定的中心处理器之外它完全没有存储能力。2.1确定型有穷自动机q0有穷控制器q5q1.q4q2q3abababab输入带读头相关概念：输入带读头有限控制器状态初始状态终结状态----------------接受语言与自动机二.有穷自动机的非形式描述如果它从初始状态开始，最后结束在一个终结状态，则认为输入串被接受。机器接受的语言是它接受的所有字符串的集合。图2-1有穷自动机二.确定型有穷自动机定义2.1.1(形式定义)一个确定型有穷自动机是一个五元组M=(K,,,s,F).K是有穷状态集是字母表s∈K是初始状态FK是终结状态集合是从K×到K的函数，叫做转移函数。有穷自动机M选取下一个状态的规则被编码成转移函数。于是，如果M处于状态q∈K且从输入带读到的字符是a∈，则(q,a)∈K是M要转移到的唯一确定的状态。确定型有穷自动机(K,,,s,F)的格局是K×*的任一元素。例如：上图2－1表示的格局为（q2,ababab）二元关系├M在M的两个格局之间成立当且仅当M能够一步从一个格局变成另一个格局。于是，如果(q,ω)和(q’,ω’)是M的两个格局，则(q,ω)├M(q’,ω’)当且仅当对于某个符号a∈Σ,ω=aω’且δ(q,a)=q’.这时我们称(q,ω)一步产生(q’,ω’)。用├*M表示├M的自反传递闭包。(q,ω)├*M(q’,ω’)读作(q,ω)产生(q’,ω’)即在0步或若干步之后。称字符串ω∈Σ*被M接受当且仅当存在q∈F使(s,ω)├*M(q,e)。M接受的语言是M接受的所有字符串的集合，记作L(M)。例2.1.1设M是确定型有穷自动机(K,,,s,F)，其中K={q0，q1}，={a，b}，s=q0，F={q0}，是由右表给出的函数可以看出L(M)是有偶数个b的{a,b}*串。如果给Ｍ输入aabba，则它的初始格局为(q0，aabba)。于是(q0，aabba)├M(q0，abba)　　├M(q0，bba)　　├M(q1，ba)　├M(q0，a)　　├M(q0，e)因此(q0，aabba)├*M(q0，e),从而aabba被Ｍ接受。一般的，转移函数可以表示成状态图形式，右上表对应的状态图如右下。对应语言：(a*Uba*b)*qσ(σ)q0aq0q0bq1q1aq1q1bq0aabbq0q1状态图例2.1.2设计一台接受语言L(M)＝{ω∈{a,b}*:ω不含有3个连续的b}的确定型有穷自动机。令M=(K,,,s,F),其中K={q0,q1,q2,q3},={a,b},s=q0,F={q0,q1,q2},由右表给出对应的状态图如下：qσ(q,σ)q0aq0q0bq1q1aq0q1bq2q2aq0q2bq3q3aq3q3bq3q0q1q2q3aaaabbbb讨论：习题2.1.2对应语言：(a*∪(ba)*∪(bba)*)*(e∪b∪bb)2.2非确定型有穷自动机考虑语言L＝(ab∪aba)*,下图给出的确定型有穷自动机接受这个语言。abbq0q1aaaabbbq3q2q4下图的非确定型有穷自动机也接受语言L＝(ab∪aba)*aabbq0q1q3aaebq0q1q3特点：1)非确定性指对于同一个输入符号，允许几个可能的“下一个状态”2)如左下图，当输入为b时从q0出发不能进入任何状态。这是另一个特点。3)在非确定型有穷自动机状态图中允许标记空串e的箭头。如右图也接受语言L。定义2.2.1（形式定义）一个非确定型有穷自动机是一个五元组M=(K,,Δ,s,F)，其中K是有穷状态集合是字母表s∈K是初始状态FK是终结状态集合ΔK×(∪{e})×K是转移关系。每一个三元组(q,u,p)∈Δ叫做M的一个转移，它在形式定义中相当于M的状态图中从q到p标记u的箭头。若M处于状态q且下一个输入符号为a，则M下次可以按照任意一个(q,a,p)或(q,e,p)形式的转移进行。若按(q,e,p)进行，则不读入任何符号。非确定有穷自动机计算的形式定义与确定性自动机很类似，包括：格局(K×*的元素)、一步产生(├M)及其若干步产生(├*M)接受ω：字符串ω∈Σ*被M接受当且仅当存在状态q∈F使得(s,ω)├*M(q,e)定义语言：M接受的语言L(M)是所有M接受的字符串的集合。例2.2.1下图描述一台非确定型有穷自动机，接受含有模式bb或者bab出现的所有字符串的集合。形式地，这台机器是(K,,Δ,s,F)其中:K={q0,q1,q2,q3,q4}={a,b}s=q0F={q4}以及Δ={(q0,a,q0),(q0,b,q0),(q0,b,q1),(q1,b,q2),(q1,a,q3),(q2,e,q4),(q3,b,q4),(q4,a,q4),(q4,b,q4)}当给M输入字符串bababab时，可能产生几个不同的动作序列。例如，只使用(q0,a,q0)和(q0,b,q0)，M结束在非终结状态q0。见P41中但使用规则3、5、7、8、9，多种使M结束在终结状态q4。见P41下注意：一个字符串被非确定型有穷自动机接受当且仅当至少有一个引导到终结状态的计算序列，所以bababab∈L(M)。a,baebq0a,bbbq2q1q3q4定理2.2.1对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机。(注：构造性证明)关键思想：认为非确定有穷自动机在任一时刻不是处于一个状态，而是处于一个状态集合，即从初始状态出发通过消耗相同的输入能够到达的所有状态。e动作集：对任一状态q∈K，令E(q)等于M从状态q开始、不读任何输入能够到达的所有状态的集合。E（q）={p∈K:(q,e)├*M（p，e）}形式化定义：设有一台非确定性有穷自动机M=(K,,Δ,s,F)，与之等价的确定性有穷自动机M’=(K’,,’,s’,F’)，其中：K’=2ks’=E(s)F’={Q:QK∧Q∩F≠⊙}’(Q,a)=∪{E(p):p∈K且对某个q∈Q,(q,a,p)∈△}即取’(Q,a)为M从Q中的状态出发通过读输入符号a可以到达的所有状态的∪{E(p)集合。断言：对于任一字符串ω∈Σ*和任意状态p,q∈K，(q,ω)├*M(p,e)当且仅当对于某个包含p的集合P,(E(q),ω)├*M’(P,e)定理证明：证明M’是确定性的和等价于M。1）证明M’是确定性的，只要注意到’是单值函数，并且对所有的Q∈K’和a∈Σ都有定义。2）证明M与M’等价，考虑任一字符串ω∈Σ*。于是，ω∈L(M)当且仅当对于某个f∈F，(s,ω)├*M(f,e)---跟据L(M)定义当且仅当对于某个包含f的Q，(E(s),ω)├*M’(Q,e)---跟据断言当且仅当对于某个Q∈F’,(s’,ω)├*M’(Q,e)---跟据L(M’)定义当且仅当ω∈L(M’)3)断言证明，对|ω|做归纳，证明上述断言。（见书，略）aaeq0q1aeebebq3q2q4例2.2.3右图是一台非确定性有穷自动机。e动作集如下：E(q0)={q0,q1,q2,q3}E(q1)={q1,q2,q3}E(q2)={q2}E(q3)={q3}E(q4)={q3,q4}构造相应的确定性有穷自动机如下：s’=E(q0)={q0,q1,q2,q3}由于s’中状态存在(q1,a,q0)、(q1,a,q4)、(q3,a,q4)故：’(s’,a)=E(q0)∪E(q4)={q0,q1,q2,q3,q4}同理，’(s’,b)=E(q2)∪E(q4)={q2,q3,q4}’({q0,q1,q2,q3,q4},a)=E(q0)∪E(q4)={q0,q1,q2,q3,q4}’({q0,q1,q2,q3,q4},b)=E(q2)∪E(q4)={q2,q3,q4}’({q2,q3,q4},a)=E(q4)={q3,q4}’({q2,q3,q4},b)=E(q4)={q3,q4}’({q3,q4},a)=E(q4)={q3,q4}’({q3,q4},b)=⊙另外，’(⊙,a)=’(⊙,b)=⊙故构造出的确定性有穷自动机如右下图所示。（讨论习题2.2.1）abbaaaabb{q0,q1,q2,q3,q4}{q0,q1,q2,q3}{q2,q3,q4}{q3,q4}⊙b2.3有穷自动机与正则表达式本节内容：证明有穷自动机（确定的和非确定的）接收的语言类与正则表达式描述的语言类（正则语言类）相同。正则语言类：某些有穷的语言在并、连接及星号运算下的闭包。定理2.3.1有穷自动机接受的语言类在下述运算下是封闭的：a.并b.连c.Kleene星号d.补e.交[证明]（注：采用构造性证明）a.并，设两台非确定性自动机M1、M2，构造一台M使得L(M)=L(M1)∪L(M)图示P47b.连接，设两台非确定性自动机M1、M2，构造一台M使得L(M)=L(M1)○L(M)图示P48c.星号，设一台非确定性自动机M1，构造一台M使得L(M)=L(M1)*图示见P48d.补，设一台确定性自动机M=(K,,,s,F)，补语言L’=*-L(M)被确定自动机M’=(K,,,s,K-F)接受。也就是M和M’完全一样，只交换终结状态与非终结状态。e.交，因为，L1∩L2=*-((*-L1)∪(*-L2))，故由并和补下封闭性，得交下封闭。定理2.3.2一个语言是正则的当且仅当它被有穷自动机接受。（注：仅当---利用定理2.3.1证明；当---利用归纳证明）例2.3.1考虑正则语言(ab∪aab)*。用定理2.3.1各部分证明中的方法构造一台非确定型有穷自动机接受这个正则表达式所表示的语言。解：按一下几步构造之。阶段1aba;bb阶段2aebaeaeab;aab阶段3aebbaeaeeeab∪aab阶段4：(ab∪aab)*aebaeaebeeeee例2.3.2构造图中确定型有穷自动机接受的语言的正则表达式。这台自动机接受语言为：babbaa假定:NFA具有如下性质：(1)它有唯一的终结状态，F={f}(2)没有进入初始状态的转移和离开终结状态的转移。解：按以下步骤可以得到相应的正则表达式。babbaee步骤1：改造之符合性质abaae步骤2：消除状态q1e步骤3：消除状态q2步骤4：消除状态q3讨论：习题2.3.72.4正则语言与非正则语言前面已经证实，正则语言在各种运算下封闭，可以用正则表达式及确定型或非确定型有穷自动机说明，这些事实给我们提供了证明语言是正则的各种技术。例2.4.1设∑＝{0,1…,9}，L∑*是可以被2或3整除的非负整数的十进制表示的集合（前面无多余的0）。例如，0，3，6，244∈L，而1，03，00L。L是正则的。[证明]我们通过这个例子来说明通过正则语言的封闭性证明一个语言是正则的方法。L=L2∪L3其中：L2为可以被2整除的非负整数的十进制表示的集合L3为可以被3整除的非负整数的十进制表示的集合第一步证明非负整数的十进制表示是正则的：设L1是非负整数的十进制表示，则：L1＝0U{1,2,…,9}∑*由于L1是用正则表达式表示的，故L1是一个正则语言。第二步再证明L2（被2整除的非负整数十进制数集合）是正则的。L2是以0，2，4，6，8结尾的L1的成员组成的集合，即，L2＝L1∩∑*{0,2,4,6,8}根据定理2.3.1(e)（有穷自动机接受的语言在交运算下是封闭的），可知L2是正则的。第三步证明L3（被3整除的非负整数十进制数集合）是正则的。可以被3整除的非负整数需要满足的条件是它的数字之和可以被3整除。我们可以构造一台有穷自动机，用它的有穷控制器保存每个输入数字的模3之和。（定理2.3.2）如下页图所示。L3是这台有穷自动机接受的语言与L1的交，则L3也是正则的。最后，L＝L2UL3，则L也是正则的。L是一个正则语言。<证明完毕>1，4，72，5，81，4，71，4，72，5，82，5，80，3，6，90，3，6，90，3，6，9(余1)(余2)(余0)图被3整除的非负整数集合L3说明：虽然有各种强力技术证明语言是正则的，但还没有办法证明语言不是正则的。非正则语言是存在的——因为正则表达式(和有穷自动机)的数目是可数的语言的数目是不可数的定理2.4.1设L是一个正则语言，则存在正整数n≥1使得任一字符串ω∈L只要|ω|≥n就可以写成ω＝xyz，其中y≠e，|xy|≤n且对每一个i≥0，xyiz∈L。[证明]（注：引用p14页鸽巢原理证明）因为L是正则语言，故L可被一台确定性有穷自动机M接受。设M有n个状态，考虑M对|ω|≥n的前n步计算：(q0,w1w2…wn)├M(q1,w2w3…wn)├M…├M(qn,e)其中q0是初始状态这里有n+1个格局，M有n状态，据鸽巢原理q0q1…qn中必然有状态重复出现，qi=qji<j，对应字符串wi+1…wj=y,x=w1..wi,z=wj+1…n，显然成立。证明完毕。理解：这是泵定理之一，断言在某些字符串中存在某些点，可以在这些地方重复插入一个子串而不影响字符串的接受性。根据这个定理我们可以确定一个语言是非正则语言。例2.4.4有时候也用封闭性证明一个语言不是正则的。例如：L={ω∈{a,b}*:ω中a和b的个数相同}不是正则的。因为如果L是正则的，则根据在交运算下的封闭性，L∩a*b*也是封闭的。而后者正好是{anbn:n≥0}，刚刚证明不是正则的。所以与假设冲突，L不是正则的。讨论：习题2.4.8例2.4.2语言L＝{anbn:i≥0}不是正则的。假定L是正则的，则存在满足定理2.4.1要求的整数n。考虑字符串ω＝anbn∈L。根据定理，可以把它重写诚ω＝xyz使得|xy|≤n且y≠e，即y＝ai，其中i>0。但是，xz＝an-ibnL，与定理矛盾。2.5状态最小化最简单的优化：给定一台确定型有穷自动机，删去所有不可达的状态及所有进入或离开它们的转移。删去不可达的状态的方法是从初始状态开始求出可达状态的集合。下面给出求可达状态的集合的算法：R:={s};While存在状态p∈R和a∈∑使δ(p,a)Rdo把δ(p,a)加入R。例如书上p58图2-19中q7q8是明显不可达的，消除后剩下的自动机如图2-20。如下左边图----〉右边图babbaa,baabbq3q6ababbaa,baabbq3q6bbaaq8q7a定义2.5.1设L是一个语言，x,y.如果对所有的z，xzL当且仅当yzL,则称x和y是相对于L等价的。记作xLy。注意L是一个等价关系即，如果x与y都属于L或者都不属于L，并且把任一字符串附加在它们的后面所得到的两个字符串也同时属于L或者同时不属于L，则xLy。设x是一个字符串，用[x]表示x所在的相对于L的等价类。例2.5.1对于图2-20中的自动机所接受的语言L=(abUba)*，容易发现L有四个等价类：1)[e]=L注：xL，含x=e，使xzL，则zL2)[a]=La(即L。a)xLa，要使xzL，则z必须是bL3)[b]=LbxLb，要使xzL，则z必须是aL4)[aa]=L(aaUbb)没有z能把具有xL(aaUbb)修补满足xzL定义2.5.2设M=(K,,,s,F)是一台确定型有穷自动机。如果字符串x,y把M从s带到同一个状态，则称x与y是相对M等价的，记作xMy。形式地，xMy当且仅当存在状态q，使得(s,x)├M*(q,e)和(s,y)├M*(q,e)。例2.5.1(续)见书p60---其中M共有6个等价类，结束于该状态的字符串。定理2.5.1对于任意的确定型有穷自动机M=(K,,,s,F)和任意的字符串x,y,如果xMy,则xL(M)y。[证明]对于任意字符串x，令q(x)K是使(s,x)├M*(q(x),e)的唯一状态。注意:对于任意字符串x,z,xzL(M)当且仅当对于某个fF,(q(x),z)├M*(f,e)。现在，如果xMy,则根据M的定义，q(x)=q(y)。于是，xMy蕴涵对于所有的z,xzL(M)当且仅当yzL(M)即xL(M)y《完毕》上述定理可以表述：M是L(M)的细化例2.5.1续(p60),M等价类细化L(M)的等价类。如Eq5与[aa]重合，[e]等于Eq1与Eq3的并。定理2.5.2设L是一个正则语言，则有一台接受L的确定型有穷自动机，它的状态恰好与L的等价类一样多。[证明]利用前面的定理，构造性证明。（略）（Myhill-Nerode定理）推论：语言L是正则的当且仅当L有有穷个等价类。例2.5.2证明L＝{anbn：n≥0}不是正则的【证明】如果i≠j，由于把bi附加在ai后面得到L中的一个字符串，而把bi附加在aj后面得到的字符串不在L中，故(根据定义2.5.1)在L下ai与aj不等价。因此，L有无穷多个等价类[e],[a],[aa],…。根据推论，L不是正则的。有穷自动机到最小自动机构造算法：定义AM:AMKx,(q,w)AM当且仅当对于某个fF，(q,w)|--*M(f,e)。即w把M从q带到一个终结状态。等价：如果对于所有的z,(q,z)AM当且仅当(p,z)AM,则称q与p等价，记作qp，的等价类恰好是为了获得L(M)的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 自动机应该合并在一块的状态的集合。n定义：对于两个状态p、q,如果对于所有的长度不超过n的z,(q,z)AM当且仅当(p,z)AM，记作pnq,n的极限是引理2.5.1对于任意的两个状态p,qK和任意一个整数n≥1,qnp当且仅当(1)qn-1p且(2)对所有的a，(q,a)n-1(p,a)算法实现（计算，进而给出L的标准自动机）Initially0的等价类是F与K-FRepeatforn:=1,2….由n-1的等价类计算n的等价类(使用引理2.5.1来实现)Untiln-1与n相同由于等价类的数目不可能比M的状态还多，故算法迭代|K|-1次后终止当算法终止时，比如说在第n次迭代时终止，计算出n-1=n,则由引理有n=n+1=n+2=n+3=…..。因而计算出的关系正是，从而得到标准自动机。例2.5.3利用上述算法计算图2-20中的确定型自动机。消除不可达状态后的自动机babbaa,baabbq3q6a初试化：0的等价类是{q1,q3}和{q2,q4,q5,q6}。第一次跌代(1)：由于(q2,b)≠0(q4,b)与(q5,b),(q2,a)≠0(q6,a),故{q2}分裂出来；由于(q5,a)≠0(q4,a)与(q6,a)，故{q5}分裂分裂出来；剩下(q4,a)0(q6,a)，(q4,b)0(q6,b)，故{q4,q6}属于一个等价类；经过跌代分裂后，1的等价类为{q1,q3}，{q2}，{q4,q6}和{q5}第二次迭代后，没有进一步的等价类分裂。于是，算法终止，最后状态自动机如下右图所示。babbaa,baabbq3q6ababbaa,ba{q1,q3}{q4,q6}{q5}{q2}化简前的确定性自动机最小化后的确定型自动机2.6关于有穷自动机的算法定理2.6.1（类型构造和等价判断的复杂度分析）(1)有一个指数算法,给定一台非确定型有穷自动机,构造一台等价的确定型有穷自动机。(2)有一个多项式算法,给定一个正则语言,构造一台等价的非确定型有穷自动机。(3)有一个指数算法,给定一台非确定型有穷自动机,构造一个等价的正则表达式。(4)有一个多项式算法,给定一台确定型有穷自动机,构造一台等价的状态最少的确定型有穷自动机(5)有一个多项式算法,给定两台确定型有穷自动机,判断它们是否等价(6)有一个指数算法,给定两台非确定型有穷自动机,判断它们是否等价有穷自动机作为算法：确定型有穷自动机M是判断一个给定的字符串是否在L(M)中的有效算法。例2.6.1图中的确定型有穷自动机可以重新表述成下述的算法：q1:Letσ:=下一个符号;ifσ=文件结束then拒绝;elseifσ=athengotoq1;elseifσ=bthengotoq2;q2:Letσ:=下一个符号;ifσ=文件结束then拒绝;elseifσ=athengotoq2;elseifσ=bthengotoq3; q3:Letσ:=下一个符号;ifσ=文件结束then接受;elseifσ=athengotoq3;elseifσ=bthengotoq1;可以看出每个状态有||+2条指令，但判断w是否在L应该O(|w|)q2baq3q1aabb定理2.6.2如果L是一个正则语言,则有一个算法,任给w∈,它在O(|w|)时间内检查w是否在L中。关于非确定型有穷自动机计算问题：正则语言——非确定型有穷自动机确定型有穷自动机（指数时间）用运行确定型有穷自动机方式直接地”运行”非确定型有穷自动机（如下）具体说，设M=(K,∑,,s,F)是一台非确定型有穷自动机，考虑下述算法：S0:=E(s),n:=0;repeatletn:=n+1,σ:=第n个输入符号；ifσ≠文件结束thenSn:=∪{E(q):对某个p∈Sn-1,(p,σ,q)∈△}Untilσ=文件结束；IfSn-1∩F≠Φthen接受else拒绝备注：E(q)表示{p:(q,e)├*M(p,e)}Sn就是字符串在第n个时可以到达的状态集合。例2.6.2让我们用这个算法对输入串aaaba运行右图中的非确定型有穷自动机。解：利用算法得到Sn的值如下所示：S0={q0,q1}S1={q0,q1,q2}S2={q0,q1,q2}S3={q0,q1,q2}S4={q1,q2,q3,q4}S5={q2,q3,q4}因为S5包含终结状态，所以机器停机时接受输入aaaba。q2b,eaaea,bq1q3q0q4baa,bb定理2.6.3如果M=(K,∑,△,s,F)是一台非确定型有穷自动机，则有一个算法,任给w∈,它在O(|w||K|2)时间内检查w是否在L(M)中。（讨论：2.6.1(b);2.6.2(a)）第3章上下文无关语言3.1上下文无关文法3.2语法分析树3.3下推自动机3.4下推自动机和上下文无关文法3.5上下文无关语言与非上下文无关语言3.6关于上下文无关文法的算法3.7确定性与语法分析3.1上下文无关文法定义3.1.1上下文无关文法G是一个四元组(V,∑,R,S),其中V是一个字母表；（注：含终结符和非终结符）∑是终结符集合，其中，∑V；R是规则集合，它是(V-∑)×V*的