四种自动机与对应文法 有限自动机 下推自动机 图灵机 线性有界自动机.ppt

形式语言与自动机 1 参考文献 2 参考文献 3 参考文献 4 背景 5 图灵机1936年首先由图灵 A M Turing 提出 他设计的自动机称为图灵机 背景 6 有限状态机又被称为有穷状态自动机 有限自动机1951年到1956年 克林 Kleene 在研究神经细胞中 建立了识别语言的系统 有限状态机 背景 7 丘奇 Church 提出了一个假设 图灵机的计算能力代表着可实现的计算装置的基本范围 任何能在电子计算机上实现的计算都能用图灵机进行描述 背景 8 形式语言1956年 N 乔姆斯基 NoamChomsky 给出一种文法的数学模型 语言L定义为一个字母表 中的字母组成的一些串的集合 L 字母表上按照一定的规则定义一个文发 grammar 该文法所产生的所有句子组成的集合就是该文法产生的语言 背景 9 20世纪50年代 巴科斯范式 BackusNourForm或BackusNormalForm BNF 实现了对高级语言ALGOL 60的成功描述 这一成功 使得形式语言在20世纪60年代得到了大力的发展 并使形式语言与编译原理紧密联系在一起 上述理论在编译原理 人工智能 可计算性和时序逻辑电路设计等领域有着广泛的应用 语言理论 10 自然语言 人与人之间交流的基本手段 如 汉语 英语 俄语 法语 等人工语言 主要用于人与计算机之间的交流 如 程序设计语言 语言理论 11 形式语言 研究自然语言和人工语言都必须遵循的一般规律研究字符串集合及其性质的学科Chomsky文法体系 4种类型的文法及其产生的语言正规文法RG 正规语言RL 上下文无关文法CFG 上下文无关语言CFL 上下文有关文法CSG 上下文有关语言CSL 无限制文法URG 递归可枚举语言r e 自动机理论 12 语言 形式语言 识别器4种类型自动机与4类文法相对应有限自动机FA RL RG下推自动机PDA CFL CFG线性界限自动机LBA CSL CSG图灵机TM r e URG 形式语言 FormalLanguage 13 语言及其表示 14 语言 某个字母表上满足某些特定条件的字符串的集合 1 1字母表 串和语言字母表 Alphabet 由字符组成的非空有限集 通常用 表示 sigma西格马 空集不能作为字母表无限集也不能作为字母表 例如 a b c d 0 1 语言及其表示 15 语言及其表示 16 语言及其表示 17 语言及其表示 18 串 String 由某字符表上的字符组成的有限序列 例如 0100101是字母表 0 1 上的一个串 串的长度 一个串中字符的个数 设x为字母表 上的一个串 x的长度记为 x 例如 0100101 7空串 不含任何字符的串 即长度为零的串 记为 语言及其表示 19 前缀 后缀 子串 语言及其表示 20 语言及其表示 21 串的逆 把一个串中的字符逆向顺序重新排列得到的另一个串设x为一个串 x的逆记为xR例 若x 0100101则xR 1010010易知1 xR x 2 空串的逆仍是空串 R 语言及其表示 22 串的连接 concatenation 运算 语言及其表示 23 串的幂运算串的连接运算又称为串的乘法运算 类似于从数的乘法运算推广到数的幂运算那样 也可以从串的乘法推广到串的幂运算 设x为一个串 则定义 语言及其表示 24 语言及其表示 25 语言及其表示 26 语言 Language 语言及其表示 27 语言几种基本运算 语言的乘积 product 语言及其表示 28 语言及其表示 29 语言及其表示 30 句型 推导与句子 语言及其表示 31 文法所产生的语言 语言及其表示 32 举例 语言及其表示 33 语言及其表示 34 语言及其表示 35 语言识别器 语言识别器同文法一样 都是对 可能为无限集的 语言提供有限表示的一种方式 语言识别器也称为自动机 如果说文法是从产生语言的角度来表示语言 那么自动机是从识别语言的角度来表示语言 自动机的结构可以大致表示成下图的形式 图自动机的大致结构 语言及其表示 36 即自动机由 部分组成 有限状态器 输入带和辅助存储器 有的自动机可以没有辅助存储器 输入带可以有限长或无限长 有限状态控制器对输入带可以只允许读 不允许写 也可以读和写 根据不同的规定 自动机可以分为几种类型 正规文法与有限自动机 37 正规语言是Chomsky文法体系中最简单的一类语言 产生这种语言的文法是正规文法 识别这类语言的是有限自动机 此外 这类语言也可以用正规表达式表示 因此 正规语言也叫正规集 正规表达式与正规集 38 正规表达式与正规集 39 正规表达式的性质 40 正规文法和正规语言 41 正规文法是Chomsky文法体系中最简单的一种文法 说它简单 是指它的产生式的形式简单 因为产生式集是一个文法的核心 定义和例子 正规文法和正规语言 42 有限自动机 finiteautomaton FA 43 有限自动机 finiteautomaton FA 44 45 确定的有限自动机 46 确定的有限自动机 47 确定的有限自动机 48 确定的有限自动机 49 确定的有限自动机 50 确定的有限自动机 51 确定的有限自动机 52 不确定的有限自动机 53 不确定的有限自动机 54 不确定的有限自动机 55 不确定的有限自动机 56 不确定的有限自动机 57 不确定的有限自动机 58 带输出的有限自动机 59 Moore机 60 Moore机 61 Moore机 62 Moore机 63 Moore机 64 Mealy机 65 Mealy机 66 Mealy机 67 Mealy机 68 Moore机和Mealy机的等价性 69 上下文无关文法与下推自动机 70 上下文无关文法 context freegrammer 71 上下文无关文法 context freegrammer 72 上下文无关文法 context freegrammer 73 上下文无关文法 context freegrammer 74 上下文无关文法 context freegrammer 75 推导树 derivationtree 76 推导树 derivationtree 77 推导树 derivationtree 78 推导树与推导的关系 79 最左推导与最右推导 80 上下文无关文法的歧义性 81 上下文无关文法的歧义性 82 上下文无关文法的应用 83 上下文无关文法的应用 84 下推自动机 PushdownAutomaton 85 下推自动机 PushdownAutomaton 86 下推自动机 PushdownAutomaton 87 下推自动机 PushdownAutomaton 88 下推自动机 PushdownAutomaton 89 下推自动机 PushdownAutomaton 90 下推自动机 PushdownAutomaton 91 下推自动机 PushdownAutomaton 92 例 构造PDAM 接受语言L M anbn n 1 思路 把输入的字符a入栈 当开始输入b时 从栈中弹出a 若a b个数相同 则到达终态 且栈中空 解 设PDAM Q T q0 z0 F Q q0 q1 q2 q0 初态 接受a q1状态 接受b q2状态 输入 回到q0T a b z0 a F q0 定义为 q0 a z0 q1 az0 q1 a a q1 aa q1 b a q2 q2 z0 q0 q2 b a q2 下推自动机 PushdownAutomaton 93 表示 p q a Z 上例的图形表示 用格局表示aabb的识别过程 q0 aabb z0 q1 abb az0 q1 bb aaz0 q2 b az0 q2 z0 q0 终态接受 确定的下推自动机 94 无限制文法 95 无限制文法 96 图灵机 97 图灵机 98 图灵机 99 图灵机 100 图灵机 101 图灵机 102 图灵机 103 图灵机 104