形式语言自动机——上下文无关文法与下推自动机(三).ppt_第1页
形式语言自动机——上下文无关文法与下推自动机(三).ppt_第2页
形式语言自动机——上下文无关文法与下推自动机(三).ppt_第3页
形式语言自动机——上下文无关文法与下推自动机(三).ppt_第4页
形式语言自动机——上下文无关文法与下推自动机(三).ppt_第5页
已阅读5页,还剩21页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1 CollegeofComputerScience Technology BUPT 4 3Chomsky范式和Greibach范式 Chomsky范式定义 2型文法G N T P S 若生成式形式都是A BC和A a A B C N a T 则G是Chomsky范式 若 L G 则S 是P的一个生成式 但S不能在任何其它生成式的右边 每个上下文无关文法都具有等效的CNF 定理4 3 1 2 CollegeofComputerScience Technology BUPT CNF的构成步骤 1 用算法1 2 3 4消除 生成式 无用符号 单生成式2 对生成式A D1D2 Dnn 2若Di T 则引入新生成式Bi Di Bi是新非终结符若Di N 则令Bi Di 从而将原生成式变化为A B1B2 Bnn 2当n 2时 再将其变为A B1C1 C1 B2C2 C2 B3C3 Cn 1 Bn 1BnCi是新引入的非终结符 定理证明 自学 3 CollegeofComputerScience Technology BUPT CNF的构成例 例 书P148例1 设G A B S a b P S 是无 无循环 无无用符号 无单生成式的文法 P S aAB BAA BBB aB AS b求等效的CNFG1解 S BA A a B AS B b已是CNF 加入到P1中对S aAB 将其变换为S CaC1 Ca a C1 AB将A BBB变换为A BC2 C2 BB 4 CollegeofComputerScience Technology BUPT CNF的构成例 例 2型文法G A B S a b P S P S bA aBA bAA aS aB aBB bS b求等效的CNF解 S CbA CaB 增加Cb b C2 aA CbD CaS a 增加D AAB CaE CbS b 增加E BB 5 CollegeofComputerScience Technology BUPT Greibach范式 Greibach范式 GNF 定义 2型文法G N T P S 若生成式的形式都是A a A N a T N 且G不含 生成式 则称G为Greibach范式 记为GNF 任何2型文法都具有等效的GNF 定理4 3 2 6 CollegeofComputerScience Technology BUPT GNF的构成步骤 1 将2型文法变换为CNF A a A BC形式 2 将非终结符排序 再进行代换 对形如Ai Aj ji 3 消左递归 对最高的An An 进行变换 使An生成式变为终结符开头 4 回代 将An生成式回代入An 1生成式 使其右部首符为终结符 将An 1生成式回代入An 2生成式 使其右部首符为终结符 5 最后将消直接左递归时引入的A1 A2 An 生成式右部进行代换 使其首符变为终结符 7 CollegeofComputerScience Technology BUPT GNF的构成例 例 书P149例2 设已有CNF A BC B CA b C AB a 将其变换为GNF 解 按其非终结符排列为A B C A是低位 C是高位 中 右部首符序号高于左部的非终结符 无需变换 对 需要变换 将 代入 得C BCB a 仍需变换 将 代入 得C CACB bCB a 8 CollegeofComputerScience Technology BUPT GNF的构成例 对上述变换后所得结果消直接左递归对C CACB bCB a变换为 1 1 2C 1 2 1C 2C C 1 1C 即C bCB a bCBC aC C ACB ACBC 9 CollegeofComputerScience Technology BUPT GNF的构成例 回代将C的生成式 回代入B的生成式 B CA b被变换为B bCBA aA bCBC A aC A b 将新的B生成式 回代入A的生成式 A BC被变换为A bCBAC aAC bCBC AC aC AC bC 再将新的A生成式 代入新引入的C 生成式 C ACB ACBC 被变换为 略 注意 新引入的Ai 相当于排在最低位 10 CollegeofComputerScience Technology BUPT 4 4下推自动机 PDA 主要内容PDA的基本概念 PDA的构造举例 用终态接受语言和用空栈接受语言的等价性 PDA是上下文无关语言的接收器 重点PDA的基本定义及其构造PDA与上下文无关语言等价难点根据PDA构造上下文无关文法 11 CollegeofComputerScience Technology BUPT 问题的引出 类似于anbn的语言无法由一般的有限自动机识别 有限状态识别器中必须有无限个状态 不允许 需要扩充机器的能力 识别anbn的无限状态自动机 12 CollegeofComputerScience Technology BUPT 下推自动机的结构 扩充办法 引入一个下推栈 足够简单 可解决许多有意义的问题 如识别有效的程序下推自动机PDA PushDownAutomaton 由一条输入带 一个有限状态控制器和一个下推栈组成PDA的动作在有限状态控制器的控制下根据它的当前状态 栈顶符号 以及输入符号作出相应的动作 有时 不需要考虑输入符号 空转移 栈 后进先出表对栈的操作 压入 弹出 均在栈顶进行 13 CollegeofComputerScience Technology BUPT 下推自动机的定义 NPDA的形式定义 七元组M Q T q0 z0 F 其中 Q 有限控制器的状态集合T 有限输入字母表 有限下推栈字母表 Q T Q 当前状态当前输入当前栈顶符号有限子集q0 初始状态 q0 Qz0 下推栈的起始符号 z0 F 终态集合 F Q 14 CollegeofComputerScience Technology BUPT 下推自动机的转换函数 转换函数 q a Z p q p Q a T Z 表示在状态q 输入字符a 且栈顶符Z时 转入状态p 栈顶符Z由 代替 同时读头右移一格 约定 的最左符号放在栈顶 表示下推栈的顶符被弹出如 q a Z p q Z p 称为 转换 即不考虑当前输入字符 读头不移动 但控制器状态可以改变且栈顶符可以调整 15 CollegeofComputerScience Technology BUPT 下推自动机的格局 格局 用于描述PDA的瞬时工作状况PDA格局 q 其中 q 当前状态 待输入串 时 表示输入字符已读完 下推栈中的内容 时表示栈已弹空 q a Z p r 用格局可表示为 q a Z p r 对PDA而言 初始格局为 q0 z0 终止格局为 q q F 16 CollegeofComputerScience Technology BUPT 下推自动机接受的语言 两种接受方式终态接受 L M q0 z0 q q F 空栈接受 L M q0 z0 q q Q 当空栈接受时 终止状态可为Q中任意状态 换言之 终止状态集是与状态无关的 此时 取F 17 CollegeofComputerScience Technology BUPT 下推自动机例 例 构造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 18 CollegeofComputerScience Technology BUPT 下推自动机的图形表示 上例的图形表示 表示 p q a Z 注 栈空就不能再移动了 用格局表示aabb的识别过程 q0 aabb z0 q1 abb az0 q1 bb aaz0 q2 b az0 q2 z0 q0 终态接受 19 CollegeofComputerScience Technology BUPT 若对于每个输入字符 其后续状态都是确定的 就是DPDA 如前例 DPDA必须满足下述二个条件之一 对 q Q z a T有 q a z 最多含一个后续选择且 q Z 或者 q a z 且 q z 最多含一个元素 这两个限制防止了在 动作和包含一个输入符号的动作之间做选择的可能性 即在同样状态 同样栈顶符号下最多只能有一个选择 确定的下推自动机 DPDA 20 CollegeofComputerScience Technology BUPT 例 构造PDAM 接受语言L M c T a b 解题思路 从状态q0接受句子 将输入存到栈中 状态不变 直到看到中心标记c 当达到c时 将状态变为q1 栈不变 将输入与下推栈匹配 状态不变 退栈 直至栈空 确定的下推自动机 DPDA 该自动机的形式定义 见书P157 21 CollegeofComputerScience Technology BUPT 例 构造PDAM 接受语言L M T a b 与前面的例子类似 区别在于中间没有标志 c 解 非确定的下推自动机 NPDA 把 c z z 改为 z z 就引进了非确定性 因为机器可在任何时刻进行这种 转换 22 CollegeofComputerScience Technology BUPT 例 构造PDAM 接受语言L M aibjck i j或i k 解题思路 与前例类似 利用不确定性 PDA可以猜想a应与b匹配还是与c匹配 所构造的NPDAM利用两个不确定的分支实现不同的猜想 解 非确定的下推自动机 NPDA 23 CollegeofComputerScience Technology BUPT 定理4 4 1如果Lf是PDAMf以终态接受的语言 必存在一个PDAM 以空栈接受语言L 使L Lf证明 设Mf Q T q0 z0 F 构造PDAMf Q qe q1 T z1 1 q1 z1 用M 模拟Mf 空栈接受与终态接受的等价 对所有qf F和z z1 1 qf z qe 当Mf进入终态时 用 转换进入qe状态 弹出栈顶 在qe状态下 若栈不为 则不断弹出栈顶符 直至栈空 1定义 1 q1 z1 q0 z0z1 将z1作为栈底符 进入Mf的起始状态 对所有q Q a T z 令 1 q a z q a z 即M 模拟Mf的动作 24 CollegeofComputerScience Technology BUPT 定理4 4 2如果L 是PDAM 以空栈接受的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论