1、形式语言形式语言-研究字符串集合及其性质的学科计算机处理的主要对象语言自然语言(字符串)人工语言（符号串）自然语言自然语言：人与人之间交流的基本手段。 如：汉语、英语、俄语、法语、等人工语言人工语言：主要用于人与计算机之间的交流。 如：程序设计语言 （也有例外，如世界语）形式语言形式语言：研究自然语言和人工语言都必须遵循的一般规律自动机：自动机：语言（形式语言）识别器可见，本课程是计算机科学的基本理论1、编译理论的发展过程： 汇编=编译或解释 =CC Compiler(YACC) 上述过程中无不运用某些形式语言的理论结果。2、形式语言的研究价值。 （1）程序语言的设计 （2）Compiler技
2、术方法改进 （3）计算复杂性：算法与自动机 （4）NP问题（多项式时间复杂度问题）（4）人工智能技术发展： 专家系统中知识表示（规则表示）及推理（规则推导） 程序正确性证明，前置条件=结果分析 软件自动生成，如CC Compiler、应用软件自动构造技术等 自然语言理解，语言识别及分析技术3、形式语言与自动机关系 形式语言研究引入了自动机进行语言识别。 自动机就是一种自动识别句子的构造或程序。 形式语言中的文法与自动机之间存在不可分割的关系。 每一种文法（四种典型文法）=一种自动机4、本课程只介绍一般的形式语言基本概念和理论 “入门性”参考书1、计算理论基础计算理论基础（第二版），Harry
3、R. L., Christos H. P.，清华大学出版社，1999年9月2、 计算理论基础（第2版）中文翻译版，张立昂、刘田 译，清华大学出版社， 2000年7月3、 形式语言与自动机理论形式语言与自动机理论吴哲辉，吴振寰 编著，机械工业出版社，2007年4月4、形式语言与自动机理论教学参考书形式语言与自动机理论教学参考书，蒋宗礼 ，清华大学出版社，2007年7月5、形式语言及其与自动机的关系形式语言及其与自动机的关系，美 J.E. 霍普克罗夫特，J.D. 厄儿曼 著；莫绍揆、段祥、顾秀芳 译，科学出版社出版， 1979年6、形式语言及其句法分析形式语言及其句法分析， 美 A.V. 阿霍，
4、J.D. 厄儿曼 著， 石青云 译 科学出版社出版， 1987年7、无论其它有关形式语言与自动机理论的书。0.2、语言及其表示、语言及其表示 提要：本节将从一般的观点来讨论定义语言的两种主要方法：提要：本节将从一般的观点来讨论定义语言的两种主要方法：产生程序产生程序和和识别程序识别程序 。产生程序主要介绍。产生程序主要介绍Chomsky文法，而识别程序则介绍各种已文法，而识别程序则介绍各种已研究过的识别程序。研究过的识别程序。 1、过程和算法 在讨论有穷表示的概念以前，我们非形式地介绍一下过程和算法。 一个过程过程就是一个能被机械地执行的指令有穷系列。如一个计算机的程序。 总是要终止的过程叫做
5、总是要终止的过程叫做算法算法。2、语言的表示 语言定义：（非形式）一个语言L是在某个有限字母表上的有限长符号串的集合。 1）罗列法罗列法： 当L由有限符号串组成时，则一个显然的表示法是把L中所有的符号串罗列出来。 L为无穷集时，怎么表示？ 假定要求（规定）语言的表示是有限的。2）产生系统产生系统：也称为文法系统。 即可给予一种算法或过程，它依某种次序可系统地依次产生语言的句子。 优点：文法=句子结构 句法分析和翻译简单3）识别法识别法： 给出一个过程，当输入一个任意的符号串时，它能判定该符号串（或句子）是否在语言中。 实际上，我们必须要求该过程是一个算法算法。什么是语言理论？什么是语言理论？
6、语言理论就是对符号行的集合、它们的表示法、结构以及特性的研究。0.3、文法文法 1、启示启示 自然语言研究自然语言研究：文法的概念由语言学家在研究自然语言的过程中形式化了的。他们不但关心正确句子的识别，而且也关心提供句子的结构性描述。 目的目的：目标之一是发展一种能够描述自然语言(英语)的形式文法，从而解决自然语言的计算机化理解、翻译和解决文字问题。 但目前自然语言研究还不成熟，而计算机语言形式化已经成熟。 例1. 1 The little boy ran quickly。 The little boy ranQuickly.图1、句子分析图解句子分析分析上述句子的规则如下： The litt
7、le boy ran quickly 注意：注意： 目的目的：我们不但要能够检查句子的语法是否正确，而且还要能产生语法上正确的句子。 方法方法：从开始，利用规则到结束。这样可以导出无穷多个句子中任何一个句子。 一般形式一般形式： The, little + boy ran quickly 例如：little The The boy ran quickly. 这里，虽然大部分句子都没有意义，然而在广义上说还是语法上正确的句子。2、文法的形式概念、文法的形式概念 文法是语言的产生程序中最重要的一类，一个文法是定义语言的一个数学系统。 这里，我们先考察一类文法，也称为乔姆斯基文法 或 短语结构文法。
8、（0型文法）1）一个语言的文法文法需要用两个不想交的符号集： 终结符终结符 与 非终结符非终结符N2）文法的核心是产生式规则集产生式规则集P： （N）* N （N）* （N）*3）文法定义文法定义： 约定约定：如果(，)是一个产生式，则用缩写 来表示。定义定义：一个文法是一个四元组一个文法是一个四元组G=（N，P，S），），其中：其中：（1）N是非终结符的有限集（变量集是非终结符的有限集（变量集 或或 句法种类集）。句法种类集）。（2）是终结符的有限集，与是终结符的有限集，与N不相交。不相交。（3）P是（是（N）* N （N）* （N）* 的有限子集，的有限子集， （，）P，可以写成：，可以写
9、成：；称为一个产生式。；称为一个产生式。（4）S是是N的一个特定符号，称为句子符或起始符。的一个特定符号，称为句子符或起始符。例子例子1.2 G1 =（A, S，0, 1，P，S）是一个文法，）是一个文法， 其中：其中：P有下列产生式组成：有下列产生式组成： S 0A1 0A 00A1 A e 这里，非终结符是这里，非终结符是A和和S；终结符是；终结符是0和和1。 问题：问题：1、该语言是什么样？、该语言是什么样？2、如何修改更简单？、如何修改更简单？ 讨论讨论句子形式句子形式：一个文法按递归方式定义语言。递归地定义如下：一个文法按递归方式定义语言。递归地定义如下：（1）S是一个句子形式。是一
10、个句子形式。（2）如果）如果是一个句子形式，且是一个句子形式，且是是P中的产生式中的产生式 则则也是一个句子形式。也是一个句子形式。 或或 ，则，则叫作句型。其中叫作句型。其中（N）*句子句子：文法：文法G的不含非终结符的一个句子形式称由的不含非终结符的一个句子形式称由G生成的一个句子。生成的一个句子。语言语言：由文法：由文法G生成的语言记为生成的语言记为L(G)，它是由，它是由G生成的所有句子的生成的所有句子的 集集 合。合。 即：即： L(G) = w | w S=*S= w*G0.4、文法分类、文法分类 按文法的产生式形式产生式形式可以对文法进行分类。乔姆斯基（Chomsky）文法分为四
11、类：即 0型、1型、2型、3型 0型型 1型型 2型型 3型型 -依次条件强硬 0型文法 设G=（N,P,S）为一文法，若其产生式均为如下结构： 其中: （N）* ，且至少含有一个非终结符。 （N）* 则称此文法为0型文法。或称短语文法，或无(条件)限制文法。 如果对0型文法分别加上下列第i条限制，则就可得到相应的i型文法： 1、若P，则 ，仅Se例外（空句子）。 2、对于任何P，则=AN，（N）* 3、P中任何产生式均为AB，A；其中：* ，A,BN文法分类文法分类：0型文法型文法：若P，其中,（N）*， 称为无限制文法无限制文法，或称短语文法短语文法。1型文法型文法：若P，则 ， 称为上下
12、文敏感的上下文敏感的，或前后文有关文法前后文有关文法。2型文法型文法：若P，则=AN，（N）*， 称为上下文无关的上下文无关的，或前后文无关文法前后文无关文法。3型文法型文法：若P中产生式均为AB，A； 其中：* ，A,BN； 称为右线性的右线性的，或正规文法正规文法。例子1.2是一个上下文有关的文法，即1型文法。(可改造成3型)例子1.3 一个文法具有下列产生式规则： S 0S | 1S | e 此文法生成的语言是0，1*。该文法是一个右线性文法，即3型文法。约定约定： 如果语言L能由x型的文法生成，就称L是x型语言。 比如：L(3)就由3型文法生成的语言，也就是3型语言。语言集合之关系语言
13、集合之关系： L(3) L(2) L(1) L(0) 0.5、识别程序识别程序-自动机自动机 自动机与文法、语言的关系。 对语言提供有限规定的另一种常用方法另一种常用方法：对语言定义一个识别程序。对语言定义一个识别程序。 也就是定义一个集合的高度格式化过程。1、识别程序的组成、识别程序的组成 识别程序有三个部分三个部分： a）一个输入磁带（字母表的线性序列） b）一个有限状态控制 c）一个辅助存储（按某种结构组织的存储字母集合） a0 a1 a2 a3 an 有限状态控制辅助存储输入头输入磁带图示 一个识别程序其中：输入头输入头，一次可读一个字母（方格）识别程序的一次移动识别程序的一次移动：左
14、移一格、不动、右移一格辅助存储辅助存储：可由两个函数（即存函数和取函数）来刻画其性能。 例如：下推表。 取函数 f ： -为存储字母表 f（Z1Z2Zn）= Z1 - 唯一能取最上端符号 存函数：假定用一个有限长符号串代替下推表最上端的符号。 g ： * * g（Z1Z2Zn, Y1Yk）= Y1Yk Z2Zn 辅助存储的类型决定一个识别程序的名称。辅助存储的类型决定一个识别程序的名称。 如：以下推表为辅助存储的识别程序称为：下推识别程序（或叫下推自动机）。识别程序的识别程序的核心核心是一个一个有限状态控制有限状态控制。可表示为状态的一个有限集，连同一个描述状态如何随当前输入符号当前输入符号（
15、输入头处符号）和取自辅助存储的当前信息当前信息而改变的映射映射。同时，也决定输入输入头移动头移动及存储存储什么信息。识别程序的运算运算是作一系列移动移动。移动移动： 输入头向左移、向右移、保持不动。 将信息存入辅助存储。 改变控制的状态。组态组态：一个识别程序的行为可由其组态来描述。 组态描述组态描述： 有限控制的状态。 输入磁带的内容，以及输入头的位置。 辅助存储的内容。 确定性的确定性的：在每一组态中最多存在一个可能的移动。 有限控制有限控制： 非确定性的非确定性的：在每一组态，移动不只一种，而属于一个有限集。 有限控制处于特定的初始状态。初始组态初始组态： 输入头处在最左边的符号。 辅存
16、中有特定的初始内容。 有限控制处于特定的最终状态集中一个状态。最终组态最终组态： 输入头处在右边的结束标记。 辅助存储也满足一定的条件（最终）。接受符号串接受符号串w： 在输入串w的条件下，能够从初始组态开始作一系列移动，（确定性） 并结束于一个最终组态，则称该识别程序接受输入符号串w。接受符号串接受符号串w： 识别程序从初始组态开始，作许多不同的移动序列。只要其中（非确定性） 至少有一个序列结束于一个最终组态，则认为符号串w被接受。例1.4 设M是确定型有穷自动机(K, , , s , F )，没有存储能力。其中： K = q0，q1， = a，b， s = q0， F = q0， 是状态转
17、移由右表给出的函数。 可以看出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、
18、语言L是右线性的右线性的3型，当且仅当L由一个（单向确定性）有限自动机所定义。2、语言L是上下文无关的上下文无关的2型，当且仅当L由一个（单向非确定性）下推自动机所定义。3、语言L是上下文敏感的上下文敏感的1型，当且仅当L由一个（双向非确定性）线性有界自动机所定义。4、语言L是递归可数的递归可数的0型，当且仅当L由一个图灵机所定义。最后，关于识别程序的精确定义可在我们课程教材中详细讨论。1.1、集合、集合 集合集合：对象的汇集。 如：L=a,b,c,d 就是四个字母的汇集形成的集合。 元素或成员元素或成员：构成集合的所有对象。 如：b是集合L的一个元素，表示成：bL 另一方面z不是L的元素，记
19、作：z L 单元素集单元素集：集合中只有一个元素，即有一个元素构成的集合。 空集空集：集合中没有一个元素，用表示。 集合元素性质定义：设集合A已经定义，P是A的元素具有的性质，则可以定义一个新集合B如下： B=x:x A且x具有性质P 子集子集：如果集合A的每一个元素都是集合B的元素，则称A是B的子集，记作：A B 真子集真子集： 如果A B，但AB，则称A是B的真子集。集合的性质集合的性质：设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) (
20、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，其中表示中所有元素的汇集 则是A的一个划分。例如：(a,b),c,d是a,b,c,d的一个划分； 奇自然数集合和偶自然数集合构成自然数N的一个划分。1.2、关系与函数、关系与函数 ：由两个元素构成的对，前后有
21、别。 如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元关系就是A1。An一个子集。 即有序n元组的集合。 ：集合A到集合B的函数是A和B上的具有下述特殊性质的二元关系R: 对于每一个元素aA，在R中恰好存在一个有序对以a为第一分量， 第二分量bB。 一般的，设f: A1An
22、|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 =(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|
23、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中图表示关系R= (a,b),(b,a),(a,d),(d,c),(c,c),(c,a) adcb图1-1 二元关系的有向图表示自反关系自反关系：如果对于每一个aA，(a,a)R，则称关系R AA 是自反自反的对称关系对
24、称关系：如果只要(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-6。等价类等价类：表示等价关系的无向图由若干个集团组成，把等价关系的这种集团 叫做等价类等价类。定理1.3.1 设R是非空集合A上的等价关系，则R的等价类构成A的一个划分。 （证明：利用等价关系性质采用反证法，
25、略）另外，由于二元关系R可以表示成图，所以也有类似于图的、。1.4、有穷集合与无穷集合：如果存在双射函数f: A|B，则称集合A与B等势。：一般的，如果对某个自然数n，一个集合与1,2,n等势， 则称这个集合是有穷的有穷的。：如果一个集合不是有穷的，则称它是无穷的无穷的。 例如：自然数集合N是无穷的；整数集合、实数集合都是无穷的。：称与N等势的集合是可数无穷的可数无穷的。：称有穷集合或可数无穷集合是可数的可数的。（可枚举的） 相反，不是可数的集合称为。另外，要证明集合A是可数无穷的，必须给出A与N之间的一个双射函数f。见书1.5、三个基本的证明技术、三个基本的证明技术 1、的原理的原理 如果A
26、是一个自然数的集合使得： （1）0A； （2）对于每一个自然数n，0,1,n A蕴函n+1A; 则A=N 非形式地非形式地说(数学归纳法的原理)： 任何一个包含0的自然数集合，如果它具有下述性质：它只要包含所有小于等于n的自然数就包含n+1，则它实际上就是全体自然数的集合。 一般的一般的，用归纳法证明下述断言：“对于所有的自然数n，性质P成立。” 用下述方式把数学归纳法原理应用于集合A=n: 对于n，P为真： （1）基础步骤：证明0A，即对于0，P成立。 （2）归纳假设：假设对任意固定的n0，P对于0,1,n成立。 （3）归纳步骤：利用归纳假设证明P对于n+1成立，于是根据归纳原理，A等于N，
27、即P对于每一个自然数成立。换句话说，如果企图把换句话说，如果企图把A的元素的元素(“鸽子鸽子”)与与B的元素的元素(“鸽巢鸽巢”)配对，迟配对，迟早不得不把一只以上的鸽子放入一个巢里。早不得不把一只以上的鸽子放入一个巢里。 鸽巢原理可以用第一个基本原理鸽巢原理可以用第一个基本原理-数学归纳法证明。数学归纳法证明。(见书上见书上)设设R是有穷集合是有穷集合A上的二元关系，上的二元关系，a,bA。如果在R中有一条从a到b的通路，则有一条长度不超过|A|的通路。：假设(a1,a2,an)是从a1=a到an=b的最短通路，即长度最小的通路，又假设n|A|。由鸽巢原理，A有一个元素重复出现在这条通路上，
28、比如说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看成一个正方阵列，对角线的补与每一行都不同。 （见书上例1.5.3） 理由：关于a是否是元素的问题，对角线集合D与Ra集合总是不同的。 若aD，则必然(a,a)R；若aRa，则必然(a,a)R;矛盾！ 即对角线上无关系的元素所在行自然不相等
29、；对角线上有关系的元素又多余该对角线上元素。定理定理1.5.2 集合集合2N是不可数的。是不可数的。（自然数的幂集自然数的幂集）证明：(大概思路)利用反证法假设它是可数无穷的，再利用对角线原理证明假设不成立。略，见书。 1.6、闭包与算法、闭包与算法 设RA2是集合A上的有向图。R的是关系 R*= (a,b): a,bA且在R中存在从a到b的通路 例子见书图1-9，构造算法见P17下 定义1.6.1函数的增长率函数的增长率：算法随问题规模变化的增长规律。 (1) 所有次数相同的多项式具有相同的增长率。 (2) nd2n nn 例子：以R关系的自反传递闭包计算为例，说明函数增长率。 p17定义1
30、.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,R2,Rm下是封闭的”形式的性质称为B的封闭性。定理定理1.6.1 设P是由集合D上的关系定义的封闭性，A是D的子集，则有唯一的包含A具有性质P的极小集合B。 （证明：略）闭包闭包：定理1.6.1中的B是A在关
31、系R1,Rm下的闭包闭包。关于形式语言及表示我们前面已经讨论过。下面我们简单地讨论一下语言的有穷表示-正则表达式与正则语言 计算理论中一个核心问题：用有穷的规定有穷的规定说明表示无穷语言无穷语言。例1.8.1 令L=w0,1* ：在w中1出现两次或三次，并且第一次和第二次不相邻 这个语言可以只用单元集和语言运算符号、。、*描述如下： 0* 。1 。 0* 。 0 。 1 。 0* ( (1 。0* ) *) 进一步简单地写成： L=0*10*010*(10* ) - 正则表达式正则表达式正则表达式定义定义： 字母表上的正则表达式是字母表 (,), , , * 上可以如下获得的所有字符串： (1
32、)、 和的每一个成员是正则表达式。 (2)、如果和是正则表达式，则()也是正则表达式。 (3)、如果和是正则表达式，则()也是正则表达式。 (4)、如果是正则表达式，则*也是正则表达式。 (5)、除上述(1)-(4)得到之外，没有任何别的正则表达式。 如果如果是任意一个正则表达式，则是任意一个正则表达式，则L()是是表示的语言。即表示的语言。即L是从字是从字符串到语言的函数。符串到语言的函数。函数L的定义： (1)、L( )=空集；对于每一个a，L(a)=a (2)、如果和是正则表达式，则L( () ) = L()L() (3)、如果和是正则表达式，则L( () ) = L()L() (4)、
33、如果是正则表达式，则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的所有字符串的集合。正则语言正则语言： 定义字母表上
34、的正则语言正则语言类由所有可写成L=L()的语言L组成，其中是上的任一正则表达式。 即，正则语言是所有能够用正则表达式描述的语言。 也就是， 上的正则语言正则语言类恰好是语言集合 a：a 关于并、连接和Kleene星号函数的闭包。语言识别装置语言识别装置：专门为某个语言L设计的、用来回答“字符串w是L的成员吗？”这样的问题的算法。例如，识别语言L=w0,1*：w不含子串111 的装置运算如下： 从左到右读字符串，每次读一个。有一个计数器，开始时为0，每当在输入串中遇到0时将它置回到0，每当遇到1时加1。如果计数器已经达到3，则停止计算并且回答“No”；如果读完整个字符串且计数器没有达到3，则停
35、止计算并且回答“Yes”。 语言识别装置和语言生成器是语言有穷说明的两种类型。 本课程后续将研究两者之间的关系。 （完）一、有穷自动机概念一、有穷自动机概念一个受到严格限制的实际计算机模型，有一个固定的、能力有限的“中心处理装置”。它接收输入，输入是一个字符串并且被传送到输入带上。没有输出，只给出是否接受这个输入的信号。换句话说，它是一种语言识别装置。有穷自动机有穷自动机（FA）是具有离散输入输出系统的数学模型。这种系统内部状态数目是有限的状态数目是有限的。系统的状态概括了对过去输入处理状况的信息。系统只需要根据当前所处的状态和面临的输入就可以决定系统的后继行为。每当系统处理了当前的输入后，系
36、统的内部状态也将发生变化。使有穷自动机成为这种受限制的模型的关键关键是：除固定的中心处理器之外它完全没有存储能力。 q0有穷控制器有穷控制器 q5 q1 . q4 q2 q3abababab输入带输入带读头读头相关概念相关概念：输入带读头有限控制器状态初始状态终结状态-接受语言与自动机二. 有穷自动机的非形式描述 如果它从初始状态初始状态开始，最后结束在一个终结状态终结状态，则认为输入串被接受。 机器接受的语言机器接受的语言是它接受的所有字符串的集合。图2-1 有穷自动机二. 确定型有穷自动机定义定义 2.1.1 (形式定义形式定义)一个确定型有穷自动机是一个五元组一个确定型有穷自动机是一个五
37、元组M = (K, , , s , F ).K是是有穷状态有穷状态集集 是是字母表字母表s K是初始状态F K是终结状态集合 是从K 到K的函数，叫做转移函数。 有穷自动机M选取下一个状态的规则被编码成转移函数。于是，如果M处于状态qK且从输入带读到的字符是a ，则 (q,a)K是M要转移到的唯一确定的状态。 确定型有穷自动机(K, , , s , F )的格局是K *的任一元素。 例如：上图21表示的格局为（q2,ababab）二元关系M在M的两个格局之间成立当且仅当M能够一步从一个格局变成另一个格局。于是，如果(q,)和(q, )是M的两个格局，则(q,)M (q,)当且仅当对于某个符号a
38、,=a 且 (q ,a)= q.这时我们称(q, )一步产生一步产生 (q, )。用*M表示M的自反传递闭包。 (q,)*M (q,)读作(q,)产生(q,) 即在0步或若干步之后。称字符串*被M接受当且仅当存在qF使(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)
39、 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 ,)q0aq0
40、q0bq1q1aq0q1bq2q2aq0q2bq3q3aq3q3bq3q0q1q2q3aaaabbbb讨论讨论：习题2.1.2对应语言：(a*(ba)*(bba)*)*(ebbb) 考虑语言L(ababa)*,下图给出的确定型有穷自动机接受这个语言。 abbq0q1aaaabbbq3q2q4下图的非确定型有穷自动机也接受语言L(ababa)*aabbq0q1q3aaebq0q1q3特点：特点：1) 非确定性指对于同一个输入符号，允许几个可能的“下一个状态” 2)如左下图，当输入为b时从q0出发不能进入任何状态。这是另一个特点。 3)在非确定型有穷自动机状态图中允许标记空串e的箭头。如右图也接受
41、语言L。定义 2.2.1 （形式定义）一个一个非确定型有穷自动机非确定型有穷自动机是一个五元组是一个五元组 M = (K, , , s, F )， 其中 K是有穷状态集合 是字母表sK是初始状态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 )及其若干步
42、产生(*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=q0 F=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输入字符
43、串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 对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机。 ( 注：构造性证明) 关键思想：关键思想：认为非确定有穷自动机在任一时刻不是处于一个状态，而是处于一个状态集合，即从初始状态出发通过消耗相同的输入能够到达的
44、所有状态。 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 = 2k s = E(s) F = Q : Q K QF (Q,a) = E(p): pK 且对某个q Q, (q,a,p) 即取即取(Q,a) 为M从Q中的状态出发通过读输入符号a可以到达的所有状态的E(p)集合。定理证明：证明M是确定性的和等价于M。1）证明M是确定性的，只要注意到是
45、单值函数，并且对所有的QK和a都有定义。2）证明M与M等价，考虑任一字符串* 。于是，L(M) 当且仅当 对于某个fF，(s, )*M (f, e) -跟据L(M)定义 当且仅当 对于某个包含f的Q，(E(s), )*M(Q, e) -跟据断言 当且仅当 对于某个QF, (s, )*M(Q, e) -跟据L(M)定义 当且仅当 L(M) 3) 断言证明，对|做归纳，证明上述断言。（见书，略）aaeq0q1aeebebq3q2q4例2.2.3 右图是一台非确定性有穷自动机。e动作集如下：E(q0)=q0,q1,q2,q3E(q1) =q1,q2,q3E(q2) = q2 E(q3) = q3 E
46、(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,
47、q4,a) = E(q4) = q3,q4(q3,q4,b) = 另外，( ,a) = ( ,b) = 故构造出的确定性有穷自动机如右下图所示。 （讨论习题2.2.1）abbaaaabbq0,q1,q2,q3,q4q0,q1,q2,q3q2,q3,q4q3,q4b本节内容：本节内容： 证明有穷自动机（确定的和非确定的）接收的语言类与正则表达证明有穷自动机（确定的和非确定的）接收的语言类与正则表达式描述的语言类（正则语言类）相同。式描述的语言类（正则语言类）相同。 正则语言类正则语言类：某些有穷的语言在并、连接及星号运算下的闭包。：某些有穷的语言在并、连接及星号运算下的闭包。定理定理2.3.1
48、有穷自动机接受的语言类在下述运算下是封闭的：有穷自动机接受的语言类在下述运算下是封闭的： 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, ,
49、 s , K- F)接受。也就是M和M完全一样，只交换终结状态与非终结状态。e.交，因为，L1 L2= *- ( (*- L1) (*- L2) )，故由并和补下封闭性，得交下封闭。定理定理2.3.2 一个语言是正则的当且仅当它被有穷自动机接受。一个语言是正则的当且仅当它被有穷自动机接受。 （注：仅当（注：仅当-利用定理利用定理2.3.1证明；当证明；当-利用归纳证明）利用归纳证明）例2.3.1 考虑正则语言考虑正则语言 (abaab)* 。用定理。用定理2.3.1各部分证明中的方法构各部分证明中的方法构造一台非确定型有穷自动机接受这个正则表达式所表示的语言。造一台非确定型有穷自动机接受这个正
50、则表达式所表示的语言。解：按一下几步构造之。解：按一下几步构造之。阶段阶段1 aba ; b b阶段阶段2 aebaeaeab ; aab 阶段阶段3 aebbaeaeeeab aab 阶段阶段4：(abaab)*aebaeaebeeeee例例2.3.2 构造图中确定型有穷自动机接受的语言的正则表达式。 这台自动机接受语言为： babbaa1q2q3q* , :31,a bkb kN有个假定假定: NFA 具有如下性质： (1) 它有唯一的终结状态，F= f (2) 没有进入初始状态的转移和离开终结状态的转移。解解：按以下步骤可以得到相应的正则表达式。babba1q2q3qee4q5q步骤1：
