有限自动机理论01章基础知识.ppt

有限自动机理论06016004,陈文宇 电子科技大学计算机科学与工程学院,联系方式,主楼B1-509 /teacher/teacher.aspx?id=48,课程情况,学时：40（前10周） 学分： 考试：闭卷、笔试 大概10周考试 考查：作业(3-4次)，不参加考试,教材：,有限自动机理论 陈文宇 电子科技大学出版社 2007.3,参考书,形式语言与自动机理论(第2版) 蒋宗礼 姜守旭 清华大学出版社2007 形式语言与自动机 陈有祺 机械工业出版社2008,参考书,Introduction to Automata Theory, Languages, and Computation (Second Edition) 自动机理论、语言和计算导论 （John E. Hopcroft 机械工业出版社）,理论来源,形式语言和自动机的理论来源于 (1) Chomsky对自然语言的研究； (2) ALGOL 60语言的语法描述方式； (3)Turing、Kleene、Neumann、Huffman等 对自动机的研究。,形式语言与自动机的作用,形式语言和自动机的理论已经成为计算机科学的理论基础。 应用范围已被扩展到生物工程、自动控制系统、图像处理与模式识别等许多领域。,计算机学科的专业能力,计算思维能力 算法设计与分析能力 程序设计与实现能力 计算机系统的认知、分析、 设计和运用能力,计算思维能力,形式化描述能力 抽象思维能力 逻辑思维方法,计算机学科的专业能力,相关理论是计算机学科基础。 理论方面的知识是计算机科学的真正灵魂。 这也是计算机科学与其他学科的重要区别。,有限自动机理论在科学领域中得到直接应用 对于计算机学科人才的计算思维能力的培养，也具有重要作用。,研究生阶段,需要进一步进行抽象思维、逻辑思维、创造思维能力的培养。 需要更宽厚、坚实的理论基础。,第1章 基础知识,本章将对有限自动机理论中所需的数学基础知识作扼要的介绍。 包括集合及其运算、关系、证明的方法、图与树的概念；常用术语和形式语言与自动机的发展 。,内容：,1.1 集合及其运算 1.2 关系 1.3 证明和证明的方法 1.4 图与树 1.5 语言 1.6 常用术语 1.7 形式语言与自动机的发展,1.1 集合及其运算,一些没有重复的对象的全体称为集合，而这些被包含的对象称为该集合的元素。 集合中元素可以按任意的顺序进行排列。 使用大写英文字母表示一个集合。,如何删除指定位置的元素？,有穷集合和无穷集合,如果一个集合包含的元素个数是有限的，称该集合为有穷集合。 如果一个集合包含的元素是无限的，称该集合为无穷集合。 无穷集合又分为可数集(也称为可列集，如正奇数集)和不可数集(如实数集)。,集合的定义方法：,列举法 命题法,列举法(穷举法),对于有穷的，且元素个数较少的集合，可以采用列举法，即将集合的所有元素全部列出，并放在一对花括号中。 例如 集合A =1，2，3，4，5,对于某些无穷集合，也可以使用类似列举的方法进行描述 如自然数集合： 0，1，2，3，,命题法,对于集合元素较多的有穷集合或者是无穷集合，可使用集合元素的形成模式 x | P(x) 进行描述。 其中：x表示集合中的任一元素, P(x)是一个谓词，对x进行限定。,用来描述或判定客体性质、 特征的词项。,x | P(x) 表示 由满足P(x)的一切x构成的集合。 可以使用自然语言，或者数学表示法来描述（表达）谓词P(x),例如：,n | n是偶数 或 n | n mod 2 = 0 描述了由所有偶数组成的集合。,集合的基数,若集合A包含元素x，记为x A 反之， x A 对于有穷集合A，使用|A|表示该集合包含的元素的个数，也称基数或势 |A| = 0 A = ,定义1-1 子集,设A, B是两个集合，如果集合A中的每个元素都是集合B的元素，则称集合A是集合B的子集(集合B是集合A的包集) A B 或 B A A, B是两个集合，如果A B，且x B，但x A，则称A是B的真子集 A B,两个集合相等，当且仅当 A B且B A 注意： 不是 A B且B A,定义1-2 集合的运算,集合A与集合B的并，记为AB 集合A的所有元素和集合B的所有元素合并在一起组成的集合。 AB=x | xA 或 xB ,思考：,什么情况下： AB=A ？,集合A与集合B的交，记为AB 是由集合A和集合B的所有公共元素组成的集合。 AB= x | xA 且 xB ,思考：,什么情况下： A B=A ？,集合A与集合B的差，记为AB 属于集合A但不属于集合B的所有元素组成的集合。 AB= x |xA 且 x B ,思考:,什么情况下： A - B=A ？,如果B A，将AB称为集合B（关于集合A）的补。 集合A称为集合B的全集（或论域）,定义1-3 幂集,设A为一个集合，那么A的幂集为A的所有子集组成的集合 记为2A 2A=B | B A,例1-1,集合A=1，2，3，则A的幂集为: 2A= ， 1，2，3， 1，2，1，3，2，3， 1，2，3 ,任取其中2个元素构成的集合,幂集2A的元素个数,当集合A为有穷集时，如果|A|=n，那么A的幂集2A的元素个数(集合A的所有子集的个数)为2n。 （集合A的幂集表示为2A的原因） 无论集合A是有穷集合，还是无穷集合，都使用2A表示集合A的幂集。,定义1-4 笛卡儿积,集合A和B的笛卡儿乘积 A B（也简记为AB） A B = (a, b) |a A且b B 当集合A、B为有穷集时 |A B|= |A| *| B|,例1-2,设A = a, b, c, B = 0, 1, 则A B =(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1) B A=(0, a), (0, b), (0, c), (1, a), (1, b), (1, c) 也可根据约定记为： A B=a0, a1, b0, b1, c0, c1,思考,什么情况下： A B = B A ?,练习,110之间的和为10的整数集合的集合, 1, 9, 2, 8, 3, 7, 4, 6, 1, 2, 7, 1, 3, 6, 1, 4, 5, 2, 3, 5, 1, 2, 3, 4 注意：没有5，5,1.2 关系,1.2.1 二元关系 1.2.2 等价关系与等价类 1.2.3 关系的合成,1.2.1 二元关系,设A和B为两个集合，则A B的任何一个子集称为A到B的一个二元关系。 若R为A到B的关系，当 (a, b) R时，可记为aRb 若A = B ，则称R为A上的关系,思考：,如果集合A和B都是有穷集合，则 A到B的二元关系有多少个？ A到B的一个二元关系 最多可以有多少个元素？ 最少可以有多少个元素,例1-3,设A为正整数集合，则A上的关系“”是集合 (a, b) | a, b A,且a b = (1, 2), (1, 3), (1, 4), . (2, 3), (2, 4), (2, 5), . . ,1.2.2 等价关系,设R是A上的二元关系 (1) 如果对于a A，都有 (a, a) R 则称R是自反的。,(2) 如果对于a, b A (a, b) R (b, a) R 则称R是对称的。,(3)若对a, b, c A (a, b) R且(b, c) R(a, c) R 则称R为传递的。,定义1-6,如果集合A上的二元关系R是自反的、对称的和传递的 则称R为等价关系。,等价关系的性质,等价关系的一个重要性质为： 集合A上的一个等价关系R 可以将集合A划分为若干个互不相交的子集-等价类,对A中的每个元素a，使用a表示a的等价类，即a=b | aRb。 等价关系R将集合A划分成的等价类的数目-等价关系的指数。,例1-3,自然数集合N上的模3同余关系 R=(a, b)| a, b N, 且 a mod 3 = b mod 3 是一个等价关系。,0,3,6,3n, 第1个等价类； 1,4,7,3n+1, 第2个等价类； 2,5,8,3n+2, 第3个等价类； 分别记为0，1和2。,N = 0 1 2 等价关系的指数为3,思考,自然数集合N上的相等关系,1.2.3 关系的合成,关系可以进行合成。,定义1-7,设R1 A B是A到B的(二元)关系 R2 B C是B到C 的(二元)关系 R1与R2的合成是A到C的(二元)关系 R1R2 = (a, c)| (a, b) R1且(b, c) R2 ,例1-5,R1和R2的是集合1,2,3,4上的关系 R1 =(1, 1), (1, 2), (2, 3), (3, 4) R2 =(2, 4), (4, 1), (4, 3), (3, 1), (3, 4) 则R1R2 =(1, 4), (2, 1), (2, 4), (3, 1), (3, 3) R2R1 =(4, 1), (4, 2), (4, 4), (3, 1), (3, 2),有？个关系,定义1-8 关系的n次幂,设R是S上的二元关系，则Rn递归定义为： (1) R0 = (a, a) | a S (2) Ri = Ri-1 R (i = 1, 2, 3, ),定义1-9 关系的闭包,设R是S上的二元关系， R的正闭包R+为 (1) R R+ ； (2) 若(a, b), (b, c) R+, 则 (a, c) R+ ； (3) 除(1)，(2)外， R+不再含有其他任何元素。,普通定义:R+,R+ = R R2 R3 ,且当S为有穷集时，有 R+ = R R2 R3 R|s|,关系的克林闭包,R* = R0 R+,例1-6,设R1= (a, b), (c, d), (b, d), (b, b), (d, e) R2= (a, a), (b, c), (d, c), (e, d), (c, a) 则R1 R2 = (a, c), (c, c), (b, c), (d, d),R1+ = (a, b), (c, d), (b, d), (b, b), (d, e), (a, d), (a, e), (c, e), (b, e) R1* = (a, a), (b, b), (c, c), (d, d), (e, e) R1+,1.3 证明和证明的方法,形式语言和有限自动机有很强的理论性，许多的论断以定理的形式进行描述，而定理的正确性是需要进行证明的。 形式语言和有限自动机理论中定理的证明普遍使用反证法和归纳法,1.3.1 反证法 1.3.2 归纳法 1.3.3 递归定义与归纳证明,1.3.1反证法(归谬法),利用反证法证明一个命题时，一般的步骤为： (1) 假设该命题不成立； (2) 进行一系列的推理； (3) 在推理的过程中如果出现了下列情况之一：,与已知条件矛盾； 与公理矛盾； 与已证过的定理矛盾； 与临时的假定矛盾； 自相矛盾；,反证法(续),由于上述矛盾的出现，可以断言“假设该命题不成立”的假设不正确； 从而肯定原命题正确。,反证法(续),反证法例子,是无理数。,演绎与归纳,演绎是从普遍性的理论知识出发，去认识个别的、特殊的现象的一种逻辑推理方法。 演绎的基本形式是三段论。 归纳是根据个别的、特殊的现象，得到普遍性知识的逻辑推理方法。,1.3.2 归纳法,归纳法是从特殊到一般的逻辑推理方法。 分为完全归纳法和不完全归纳法两种形式。,完全归纳法是根据一切情况的分析而作出的推理。 由于必须考虑所有的情况，得出的结论是完全可靠的。,归纳法（续）,不完全归纳法是根据一部分情况作出的推理。 不能作为严格的证明方法。,在自动机理论中，普遍使用数学归纳法证明某个命题。,数学归纳法可以使用 “有限步骤” 解决“无限”问题。,数学归纳法,对于一切非负整数n的 命题M(n) (1) M(0)为真； (2) 假设对于任意的k 0，M(k)为真，能够证明M(k + 1)为真 (3)则对一切n 0，M(n)为真。,第(1)步称为归纳基础 第(2) 步称为归纳步骤 第(2)步中“设对于任意的k 0，M(k)为真”，称为归纳假设,数学归纳法的简化,对于0，证明结论成立； 假设结论对于n成立，证明结论对于n成立。,1.3.3 集合递归定义与归纳证明,递归定义 (1) 基础 (2) 归纳 (3) 极小性限定(有限性),递归定义集合步骤,(1)基础： 首先定义该集合中最基本的元素 x1, x2, x3, xm,(2)归纳： 对于该集合中的元素 x1, x2, x3, xn 使用某种组合方法对这些元素进行处理后所得的新元素在该集合中,(3)有限性： 只有满足(1)和(2)的元素才在集合中,递归定义集合的优点,除集合的基本元素(直接定义)外 集合中的元素的产生遵从相同的规律。,例1-6 Fibonacci数,Fibonacci数组成的集合为： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ,(1)基础： 0和1是最基本的两个元素； (2)归纳： 若m是第i个元素,n是第i+1个元素 则第i + 2个元素为n + m; (3)只有满足(1)和(2)的数，才是集合的元素,例,括号匹配的串构成的集合的定义 ( ),( )( ),( ( ) ), （1）基础： ( )是最基本的串,（2）归纳： 若S是括号匹配的串,则(S)是括号匹配的串 若S是括号匹配的串,则SS是括号匹配的串,练习,给出下列计算的递归定义 字符串的倒序,1.4 图与树,1.3.1 无向图 1.3.2 有向图 1.3.3 树,图,现实世界中，许多问题可以抽象成图来表示。 直观地，图是由一些点和连接两点的边组成的。,定义1-10无向图,设V是一个非空的有穷集合 E V V 称G = (V, E)为一个无向图。 其中，V称为顶点集 E称为无向边集,无向图中的边都没有方向 (vi, vj)和(vj, vi)表示的是同一条边,无向图顶点的度: 该顶点相关联的边的条数 记为 deg(v)，其中： v V,练习,设G = (V，E)为一个无向图，则,数学归纳法,证明： (1)基础。 当图|E|=0时，图中各结点的度均为0，因此,(2)归纳。 假设|E|=n时结论成立 |E|=n+1时，图添加一条边 令为(vi,vj)。,则 deg(vi)， deg(vj) 都增加1 而其它结点的度保持不变 因此在新图中仍有,(3)由归纳法原理 结论对任意无向图成立。,例,V = v1, v2, v3, v4, v5 E = (v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v5), (v3, v4), (v3, v5), (v4, v5) deg(v1) = deg(v2) =deg(v4) = deg(v5) = 3 deg(v3) = 4,有向图,(vi, vj)表示的是从前导vi出发，到达后继vj的一条边。 (vi, vj)和(vj, vi)表示的是不同边 有向图顶点的度： 入度与出度,例 G2,V = v1, v2, v3, v4, v5 E = (v1, v2), (v1, v3), (v2, v3), (v3, v4), (v3, v5), (v4, v1),(v4, v5), (v5, v2),(v5, v4) ideg(v1)= 1,odeg (v1)= 2 ideg(v2) =2, odeg(v2) =1,定义1-12 有向路,设G = (V，E)为一个有向图 如果对于0 i k 1，均有 (vi, vi+1) E 称v0，v1，vk是一条(有向)路,有向回路,当v0 = vk时 称为一条(有向)回路。,思考,从v1到v4有多少条路？,定义1-13 树,设G = (V, E)为一个有向图。 当G满足如下条件时，称G为一棵(有向)树：,1) v V，v没有前导，且v到树中的其他顶点都有一条有向路，该顶点称为树G的根； 2)每个非根顶点有且仅有一个前导； 3) 每个顶点的后继按其拓扑关系从左到右排序。,1.5 语言,任意字符的集合是一个字母表。 如 26个英文字母表；10个阿拉伯数字字母表；24个希腊字母表；二进制字母表,字母表有非空性、有穷性、单一性 一般使用表示字母表。,字符串,字母表中的字母按照某种顺序排列成的字符的序列,语言,字符串的集合,语言研究的三个方面,1）如何给出一个语言的表示。 对于有穷语言，使用列举法； 对于无穷语言，需要考虑语言的有穷描述。,语言研究的三个方面（续）,2）对于一个给定的无穷语言是否存在有穷描述（有穷表示）。 注意：并不是所有的无穷语言都存在有穷表示。,语言研究的三个方面（续）,3）具有有穷表示的语言的结构以及结构的描述问题。,1.6 常用术语,(1) 用代表空串，代表仅含有空串的集合。 (2) 用代表空集，表示一个元素都不包含的集合。 (3) 用代表字母表。,常用术语（续）,(4) 用代表两个字符串与的连接（并置） 若 = a1a2a3an, = b1b2b3bm; 则= a1a2a3anb1b2b3bm。 特别： = =,用代表n的n次连接 0 = n = n-1 ，n0,(5) 用AB代表集合A与B的连接 A=a1,a2,a3,an B=b1,b2,b3,bm,AB= a1b1，a1b2，a1b3，a1bm， a2b1，a2b2，a2b3，a2bm， a3b1，a3b2，a3b3，a3bm， anb1，anb2，anb3，anbm ,注意：,A=A=,一般，AB与BA是不相等的。,思考:,AB与BA在什么情况下相等? 1)当 A=B； 2)A或B中有一个为,则 A=A=A 3)A和B中有一个为，则 A=A=,6)An代表集合A的n次连接(幂) A的n次幂定义为： (1) A0 = (2) An = An-1A n 1,7) A*代表A上所有字符串的集合 即表示集合A中的所有字符串进行任意次 连接而形成的串的集合,A*称为集合A的闭包(克林闭包) A* = A0 A1 A2 An,例 A=0，1,A0= 即长度为0的0和1组成的串的集合 A1=A=0,1 即长度为1的0和1组成的串的集合,A2=AA=00,01,10,11 即长度为2的0和1组成的串集合 A3=A2A =000,001,010,011,100,101,110,111 即长度为3的0和1组成的串的集合, A* = A0 A1 A2 An =0和1 组成的所有的串 =w|w是0和1 组成的串,如果串是集合A的闭包中的串，也称是集合A上的串。 对于任何集合A 有(A*)*= A*,8) A+称为A的正闭包 A+=AA2A3An,A * 与 A+,A * = A+ A0 即 A * = A+ ,注意：,A0= *= += *= +=,思考,是否对于任意的集合A，都有 A+= A*-,辨析与思考与,|=1 |=0 A=A A= ,9）给定字母表，则*的任意子集L称为字母表上的一个语言。 本质上，语言L是字母表上的字符串形成的集合。,10)给定字母表， L是字母表上的一个语言，是L的一个字符串 称为L的一个句子。,串的长度,|=0； |= n；若=a1a2a3an； 其中：ai，n0；,11)前缀和后缀： x,y,z*，且x=yz y是x的前缀； 如果z ，则称y是x的真前缀； z是x的后缀； 如果y，则称z是x的真后缀；,例1-13,串abcde： 前缀：，a，ab，abc，abcd，abcde 真前缀：，a，ab，abc，abcd 后缀：，e，de，cde，bcde，abcde 真后缀：，e，de，cde，bcde,对于任意字符串x，x的前缀有 |x|+1 个 真前缀有 | x | 个,对于任何字符串x，x的任意前缀y有惟一的一个后缀z与之对应，使得x=yz，反之亦然； 对于任何字符串x，x的任意真前缀y有惟一的一个真后缀z与之对应，使得x=yz，反之亦然（除了以外）；,对于任何字符串x x是自身的前缀，但不是真前缀 x是自身的后缀，但不是真后缀,对于任何字符串x ， 是x的前缀，且是真前缀； 是x的后缀，且是真后缀；,思考：,对于， 前缀是？真前缀？ 后缀是？真后缀？,12)语言的前缀性质 设L是某个字母表上的语言 如果L中的任何句子都是另一个句子的真前缀，则称语言L具有前缀性质。,例1-14,字母表0，1上的语言 L1=0n|n=0 具有前缀性质； 语言L2=0n1|n=0 不具有前缀性质。,语言与句子,设是一个字母表，L *, L称为字母表上的一个语言 x L, x称为L的一个句子。 语言的可分为有穷语言与无穷语言,语言的乘积,设1, 2是两个字母表 L1 1*, L2 2*, 语言L1与L2的乘积是一个语言： L1L2=xy | x L1, y L2 该语言是字母表1 2 上的语言,语言的例子,字母表 0, 1上的一些语言： 00, 11 0, 1, 00, 11 00, 1*1 0, 1*1110, 1*,语言的n次幂,设是一个字母表，L *, L的n次幂是一个语言 (1) 当n = 0时， Ln = (2) 当n 1时， Ln = Ln-1 L,语言的例子,令 = 0, 1， L = 0, 1 L = 0, 1, 00, 01, 10, 11, = + L = , 0, 1, 00, 01, 10, 11, = *,L = 0n1n | n 1 L = 0n1m0k | n, m, k 1 L = 0n1m0k | n, m, k ,语言的闭包,L的正闭包L+是一个语言： L+ = L L2 L3 L的克林闭包L*是一个语言： L* = L0 L+,1.7形式语言与自动机的发展,语言学家Chomsky(乔姆斯基)最早从产生语言的角度研究语言。1956年，通过抽象，Chomsky将语言形式地定义为由一个字母表的字母组成的一些串的集合：对于任意语言L，有一个字母表，使得LC*。可以在字母表上按照一定的形成规则定义一个文法，该文法产生的所有的句子组成的集合就是该文法产生的语言。,1959年，Chomsky根据产生语言的文法的产生式的不同特点，将文法和对应产生的语言分为三大类。,数学家Kleene（克林）在19511956年间，从识别语言的角度来研究语言，给出了语言的另一种描述方式。Kleene在研究神经细胞时建立了自动机模型，Kleene使用该模型来识别（接收）一个语言：按照某种识别规则构造自动机，该自动机就定义了一个语言，该语言由自动机能够识别的所有字符串构成。,语言的两种不同的定义方式进一步引起了人们的研究兴趣。一个语言，可以采取不同的描述方式：文法产生语言和自动机识别语言。由于是同一个语言，两种方式应该是等价的，也就存在两种方式之间的等价的相互转换方法。,Chomsky于1959年，将他本人的形式语言的研究成果和Kleene的自动机的研究成果结合起来，不仅确定了文法和自动机分别从产生和识别角度定义语言，而且证明了文法与自动机的等价性。此时，形式语言与自动机理论才真正诞生。并被置于数学的光芒之下。,形式语言与自动机理论出现后，迅速在计算机科学技术领域得到了应用。使用巴科斯-诺尔范式（BNF-Backus-Naur Form）成功地对高级程序设计语言ALGOL-60的词法和语法规则进行了形式化的描述（实际上，巴科斯-诺尔范式就是上下文无关文法的产生式另一种表示方式）。这一成功，使得形式语言与自动机理论得到了进一步的发展。,尤其是上下文无关文法，被作为计算机程序设计语言语法的最佳近似描述得到了较为深入的研究。后来，人们又将上下文无关文法应用到了模式匹配和模型化处理等方面，而这些内容都是算法描述和分析、计算复杂性理论和可计算性理论的研究基础。,形式语言理论的研究对象与以前的所有语言研究不同，不止自然语言，而是人类一切语言：既有自然语言，也有人工语言，包括计算机编程的高级语言。乔姆斯基的形式语言理论得到了多重验证，于是才为语言学界和计算机科学界所折服，“引发了语言学中伽利略式的科学革命的开端。”,乔姆斯基的形式语言理论得到过计算机科学的三种验证。,验证一：乔氏4型文法与4种语言自动机一一对应。,验证二：计算机所使用的各种高级语言，如ALGOL、FORTRAN、PASCAL、C、LISP等，都遵循一种程序语言文法描述的范式，即巴科斯诺尔范式。计算机科学家发现，巴科斯诺尔范式等价于乔姆斯基的2型文法，即与上下文无关文法。而乔姆斯基的3型文法正则文法，在研究文字的计算机模式识别时，也被有效应用。于是，乔氏的4种类型文法被计算机科学界称作乔姆斯基分类。,验证三：乔姆斯基用形式语言理论的思想证明了计算机科学的一个重大理论问题：计算机程序语言是否有歧义性是不可判定的。 20世纪中期，程序语言ALGOL60问世不久，人们发现它有歧义性。当计算机科学家绞尽脑汁寻找办法来判断一种程序语言是否有歧义性时，乔姆斯基用形式语言理论的思想证明，一个任意的上下文无关文法是否有歧义性是不可判定的，因此，属于上下文无关文法的程序语言是否有歧义性也是不可判定的。乔姆斯基的论证令