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