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

有限自动机理论06016004 陈文宇电子科技大学计算机科学与工程学院 联系方式 cwy楼B1 509 课程情况 学时 40 前10周 学分 考试 闭卷 笔试大概10周考试考查 作业 3 4次 不参加考试 教材 有限自动机理论陈文宇电子科技大学出版社2007 3 参考书 形式语言与自动机理论 第2版 蒋宗礼姜守旭清华大学出版社2007形式语言与自动机陈有祺机械工业出版社2008 参考书 IntroductiontoAutomataTheory Languages andComputation SecondEdition 自动机理论 语言和计算导论 JohnE Hopcroft机械工业出版社 理论来源 形式语言和自动机的理论来源于 1 Chomsky对自然语言的研究 2 ALGOL60语言的语法描述方式 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 nmod2 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 AA B是两个集合 如果A B 且 x B 但x A 则称A是B的真子集A B 两个集合相等 当且仅当A B且B A注意 不是A B且B A 定义1 2集合的运算 集合A与集合B的并 记为A B集合A的所有元素和集合B的所有元素合并在一起组成的集合 A B x x A或x B 思考 什么情况下 A B A 集合A与集合B的交 记为A B是由集合A和集合B的所有公共元素组成的集合 A B x x A且x B 思考 什么情况下 A B A 集合A与集合B的差 记为A B属于集合A但不属于集合B的所有元素组成的集合 A B x x A且x B 思考 什么情况下 A B A 如果B A 将A B称为集合B 关于集合A 的补 集合A称为集合B的全集 或论域 定义1 3幂集 设A为一个集合 那么A的幂集为A的所有子集组成的集合记为2A2A 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 练习 1 10之间的和为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 且amod3 bmod3 是一个等价关系 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的 二元 关系R1 R2 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 则R1 R2 1 4 2 1 2 4 3 1 3 3 R2 R1 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 6Fibonacci数 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 3deg 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 2ideg 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 用 代表两个字符串 与 的连接 并置 若 a1a2a3 an b1b2b3 bm 则 a1a2a3 anb1b2b3 bm 特别 用代表 n的n次连接 0 n n 1 n 0 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 A3 A和B中有一个为 则A A 6 An代表集合A的n次连接 幂 A的n次幂定义为 1 A0 2 An An 1An 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 A A2 A3 An 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 若 a1a2a3 an 其中 ai n 0 11 前缀和后缀 x y z 且x yzy是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 反之亦然 除了 以外 对于任何字符串xx是自身的前缀 但不是真前缀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 0 0 1 1 0 1 111 0 1 语言的n次幂 设 是一个字母表 L L的n次幂是一个语言 1 当n 0时 Ln 2 当n 1时 Ln Ln 1L 语言的例子 令 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 克林 在1951 1956年间 从识别语言的角度来研究语言 给出了语言的另一种描述方式 Kleene在研究神经细胞时建立了自动机模型 Kleene使用该模型来识别 接收 一个语言 按照某种识别规则构造自动机 该自动机就定义了一个语言 该语言由自动机能够识别的所有字符串构成 语言的两种不同的定义方式进一步引起了人们的研究兴趣 一个语言 可以采取不同的描述方式 文法产生语言和自动机识别语言 由于是同一个语言 两种方式应该是等价的 也就存在两种方式之间的等价的相互转换方法 Chomsky于1959年 将他本人的形式语言的研究成果和Kleene的自动机的研究成果结合起来 不仅确定了文法和自动机分别从产生和识别角度定义语言 而且证明了文法与自动机的等价性 此时 形式语言与自动机理论才真正诞生 并被置于数学的光芒之下 形式语言与自动机理论出现后 迅速在计算机科学技术领域得到了应用 使用巴科斯 诺尔范式 BNF Backus NaurForm 成功地对高级程序设计语言ALGOL 60的词法和语法规则进行了形式化的描述 实际上 巴科斯 诺尔范式就是上下文无关文法的产生式另一种表示方式 这一成功 使得形式语言与自动机理论得到了进一步的发展 尤其是上下文无关文法 被作为计算机程序设计语言语法的最佳近似描述得到了较为深入的研究 后来 人们又将上下文无关文法应用到了模式匹配和模型化处理等方面 而这些内容都是算法描述和分析 计算复杂性理论和可计算性理论的研究基础 形式语言理论的研究对象与以前的所有语言研究不同 不止自然语言 而是人类一切语言 既有自然语言 也有人工语言 包括计算机编程的高级语言 乔姆斯基的形式语言理论得到了多重验证 于是才为语言学界和计算机科学界所折服 引发了语言学中伽利略式的科学革命的开端 乔姆斯基的形式语言理论得到过计算机科学的三种验证 验证一 乔氏4型文法与4种语言自动机一一对应 验证二 计算机所使用的各种高级语言 如ALGOL FORTRAN PASCAL C LISP等 都遵循一种程序语言文法描述的范式 即巴科斯 诺尔范式 计算机科学家发现 巴科斯 诺尔范式等价于乔姆斯基的2型文法 即与上下文无关文法 而乔姆斯基的3型文法 正则文法 在研究文字的计算机模式识别时 也被有效应用 于是 乔氏的4种类型文法被计算机科学界称作乔姆斯基分类 验证三 乔姆斯基用形式语言理论的思想证明了计算机科学的一个重大理论问题 计算机程序语言是否有歧义性是不可判定的 20世纪中期 程序语言ALGOL60问世不久 人们发现它有歧义性 当计算机科学家绞尽脑汁寻找办法来判断一种程序语言是否有歧义性时 乔姆斯基用形式语言理论的思想证明 一个任意的上下文无关文法是否有歧义性是不可判定的 因此 属于上下文无关文法的程序语言是否有歧义性也是不可判定的 乔姆斯基的论证令计算机科学界折服 实际上 形式语言与自动机理论除了在计算机科学与技术领域的直接应用外 更在计算机计算机科学与技术领域的人才的计算