形式语言课件完整版本.ppt

2020 3 28 1 第7章下推自动机 PDA描述CFL 所以它应该与CFG等价 PDA应该包含FA的各个元素 或者包含那些可以取代FA的各个元素的功能的元素 PDA按照最左派生的派生顺序 处理处于当前句型最左边的变量 因此 需要采用栈作为其存储机构 按照FA的 习惯 PDA用终态接受语言 模拟GNF的派生PDA用空栈接受语言 2020 3 28 2 第7章下推自动机 主要内容PDA的基本概念 PDA的构造举例 用终态接受语言和用空栈接受语言的等价性 PDA是CFL的接受器 重点PDA的基本定义及其构造 PDA是CFL的等价描述 难点根据PDA构造CFG 2020 3 28 3 7 1基本定义 PDA的物理模型 2020 3 28 4 7 1基本定义 PDA应该含有三个基本结构存放输入符号串的输入带 存放文法符号的栈 有穷状态控制器 PDA的动作在有穷状态控制器的控制下根据它的当前状态 栈顶符号 以及输入符号作出相应的动作 在有的时候 不需要考虑输入符号 2020 3 28 5 7 1基本定义 下推自动机 PDA M Q q0 Z0 F Q 状态的非空有穷集合 q Q q称为M的一个状态 输入字母表 要求M的输入字符串都是 上的字符串 栈符号表 A 叫做一个栈符号 2020 3 28 6 7 1基本定义 Z0 Z0 叫做开始符号 是M启动时候栈内惟一的一个符号 所以 习惯地称其为栈底符号 q0 q0 Q 是M的开始状态 也可叫做初始状态或者启动状态 F F Q 是M的终止状态集合 简称为终态集 q F q称为M的终止状态 也可称为接受状态 简称为终态 2020 3 28 7 7 1基本定义 状态转移函数 有时候又叫做状态转换函数或者移动函数 Q 2020 3 28 8 7 1基本定义 q a Z p1 1 p2 2 pm m 表示M在状态q 栈顶符号为Z时 读入字符a 对于i 1 2 m 可以选择地将状态变成pi 并将栈顶符号Z弹出 将 i中的符号从右到左依次压入栈 然后将读头向右移动一个带方格而指向输入字符串的下一个字符 2020 3 28 9 7 1基本定义 q Z p1 1 p2 2 pm m 表示M进行一次 移动 空移动 即M在状态q 栈顶符号为Z时 无论输入符号是什么 对于i 1 2 m 可以选择地将状态变成pi 并将栈顶符号Z弹出 将 i中的符号从右到左依次压入栈 读头不移动 2020 3 28 10 7 1基本定义 符号使用约定英文字母表较为前面的小写字母 如a b c 表示输入符号 英文字母表较为后面的小写字母 如x y z 表示由输入字符串 英文字母表的大写字母 表示栈符号 希腊字母 表示栈符号串 2020 3 28 11 7 1基本定义 即时描述 ID q w Q 称为M的一个即时描述 它表示M处于状态q w是当前还未处理的输入字符串 而且M正注视着w的首字符 栈中的符号串为 的最左符号为栈顶符号 最右符号为栈底的符号 较左的符号在栈的较上面 较右的符号在栈的较下面 2020 3 28 12 7 1基本定义 如果 p q a Z a 则 q aw Z M p w 表示M做一次非空移动 从ID q aw Z 变成ID p w 如果 p q Z 则 q w Z M p w 表示M做一次空移动 从ID q aw Z 变成ID p w 2020 3 28 13 7 1基本定义 Mn是 M的n次幂 q1 w1 1 Mn qn wn n M 是 M的克林闭包 q w M p x M 是 M的正闭包 q w M p x 2020 3 28 14 7 1基本定义 M接受的语言M用终态接受的语言L M w q0 w Z0 p 且p F M用空栈接受的语言N M w q0 w Z0 p 2020 3 28 15 7 1基本定义 例7 1考虑接受语言L w2wT w 0 1 的PDA的设计 解法1 先设计产生L的CFGG1 G1 S 2 0S0 1S1再将此文法转化成GNF G2 S 2 0SA 1SBA 0B 1 2020 3 28 16 7 1基本定义 句子0102010的最左派生和我们希望相应的PDAM的动作 2020 3 28 17 7 1基本定义 句子0102010的最左派生和我们希望相应的PDAM的动作 2020 3 28 18 7 1基本定义 M1 q0 0 1 2 S A B 1 q0 S 其中 1 q0 0 S q0 SA 1 q0 1 S q0 SB 1 q0 2 S q0 1 q0 0 A q0 1 q0 1 B q0 此时有 N M1 L 2020 3 28 19 7 1基本定义 M2 q0 q1 0 1 2 S A B Z0 2 q0 Z0 q1 2 q0 0 Z0 q0 SAZ0 2 q0 1 Z0 q0 SBZ0 2 q0 2 Z0 q1 2 q0 0 S q0 SA 2 q0 1 S q0 SB 2 q0 2 S q0 2 q0 0 A q0 2 q0 1 B q0 2 q0 Z0 q1 此时有 N M2 L M2 L 2020 3 28 20 7 1基本定义 解法2 注意到L w2wT w 0 1 所以PDAM3的工作可以分成两大阶段 在读到字符2之前 为 记载 阶段 每读到一个符号就在栈中做一次相应的记载在读到2以后 再读到字符时 就应该进入 匹配 阶段 由于栈的 先进后出 特性正好与wT相对应 所以 用栈顶符号逐一地与输入字符匹配 2020 3 28 21 7 1基本定义 M3 q0 q1 q2 qf qt 0 1 2 A B Z0 3 q0 Z0 qf q0为开始状态q1为记录状态q2为匹配状态qf为终止状态qt陷阱状态 2020 3 28 22 7 1基本定义 3 q0 0 Z0 q1 AZ0 3 q0 1 Z0 q1 BZ0 3 q0 2 Z0 qf 3 q1 0 A q1 AA 3 q1 1 A q1 BA 3 q1 0 B q1 AB 3 q1 1 B q1 BB 2020 3 28 23 7 1基本定义 3 q1 2 A q2 A 3 q1 2 B q2 B 3 q2 0 A q2 3 q2 0 B qt 3 q2 1 B q2 3 q2 1 A qt 3 q2 Z0 qf 此时有 N M3 L M3 L 2020 3 28 24 7 1基本定义 不追求让PDA同时用终止状态和空栈接受同样的语言 还可以删除状态qf 这样我们可以得到PDAM4 M4 q0 q1 q2 0 1 2 A B Z0 4 q0 Z0 4 q0 0 Z0 q1 AZ0 4 q0 1 Z0 q1 BZ0 4 q0 2 Z0 q2 2020 3 28 25 7 1基本定义 4 q1 0 A q1 AA 4 q1 1 A q1 BA 4 q1 0 B q1 AB 4 q1 1 B q1 BB 4 q1 2 A q2 A 4 q1 2 B q2 B 4 q2 0 A q2 4 q2 1 B q2 构造接受L wwT w 0 1 的PDA构造接受L 1n0m n m 1 的PDA构造接受L 1n0n1m0m n m 1 的PDA构造PDAM接受L M 1n0n n 1 1n02n n 1 构造PDAM接受N M 1n0n n 1 1n02n n 1 2020 3 28 27 7 1基本定义 确定的PDA q a Z Q q a Z q Z 1PDA在每一个状态q和一个栈顶符号下的动作都是惟一的 关键对于 q Z Q M此时如果有非空移动 就不能有空移动 每一种情况下的移动都是惟一的 2020 3 28 28 7 2PDA与CFG等价 对于任意PDAM1 存在PDAM2 使得L M2 N M1 对于任意PDAM1 存在PDAM2 使得N M2 L M1 CFL可以用空栈接受语言的PDA接受 PDA接受语言可以用CFG描述 2020 3 28 29 7 2 1PDA用空栈接受和用终止状态接受等价 定理7 1对于任意PDAM1 存在PDAM2 使得N M2 L M1 证明要点 1 构造 设PDAM1 Q 1 q01 Z01 F 取PDAM2 Q q02 qe Z02 q02 Z02 F 其中Q q02 qe Z02 2020 3 28 30 7 2 1PDA用空栈接受和用终止状态接受等价 2 q02 Z02 q01 Z01Z02 q a Z Q 2 q a Z 1 q a Z q Z Q F 2 q Z 1 q Z q Z F 2 q Z 1 q Z qe q F 2 q Z02 qe Z Z02 2 qe Z qe 2020 3 28 31 7 2 1PDA用空栈接受和用终止状态接受等价 2 证明N M2 L M1 x L M1 q01 x Z01 M1 q 且q F q01 x Z01Z02 M1 q Z02 且q F q01 x Z01Z02 M2 q Z02 且q F 2020 3 28 32 7 2 1PDA用空栈接受和用终止状态接受等价 q01 x Z01Z02 M2 q Z02 M2 qe 且q F q01 x Z01Z02 M2 qe q02 x Z02 M2 q01 x Z01Z02 M2 qe q02 x Z02 M2 qe x N M2 2020 3 28 33 7 2 1PDA用空栈接受和用终止状态接受等价 定理7 2对于任意PDAM1 存在PDAM2 使得L M2 N M1 证明要点 1 构造 设PDAM1 Q 1 q01 Z01 2020 3 28 34 7 2 1PDA用空栈接受和用终止状态接受等价 取PDAM2 Q q02 qf Z02 q02 Z02 qf 其中Q q02 qf Z02 2的定义如下 2 q02 Z02 q01 Z01Z02 对于 q a Z Q 2 q a Z 1 q a Z 2 q Z02 qf 2020 3 28 35 7 2 1PDA用空栈接受和用终止状态接受等价 2 证明L M2 N M1 x L M2 q02 x Z02 M2 qf q02 x Z02 M2 q01 x Z01Z02 q02 x Z02 M2 q01 x Z01Z02 M2 qf q01 x Z01Z02 M2 q Z02 且 q Z02 M2 qf q01 x Z01Z02 M1 q Z02 q01 x Z01 M1 q x N M1 2020 3 28 36 7 2 2PDA与CFG等价 定理7 3对于任意CFLL 存在PDAM 使得N M L 证明要点 先考虑识别L 的PDA 然后再考虑对 的处理问题 2020 3 28 37 7 2 2PDA与CFG等价 1 构造PDA 设GNFG V T P S 使得L G L 取PDAM q T V q S 对于任意的A V a T q a A q A a P 也就是说 q q a A 的充分必要条件是A a P 2020 3 28 38 7 2 2PDA与CFG等价 2 证明构造的正确性 N M L 施归纳于w的长度n 证明 q w S Mn q 的充分必要条件为S nw 并且在假设结论对n k成立 而证明结论对n k 1成立时 取w xa x k a T 在证明必要性时有如下过程 充分性的证明过程是倒退回来 2020 3 28 39 7 2 2PDA与CFG等价 q w S q xa S Mk q a M q 此时必定存在A V A 1 q 2 q a A q a q a A 1 M q 2 1 q 由 q 2 q a A 就可以得到A a 2 P 再由归纳假设 得到S kxA 1 合起来就有S kxA 1 xa 2 1 2020 3 28 40 7 2 2PDA与CFG等价 3 考虑 L的情况 先按照 1 的构造方法构造出PDAM q T V q S 使得N M L 然后取M1 q q0 T V Z 1 q0 Z 其中 q0 q Z V 令 1 q0 Z q0 q Z0 对于 a A T V 1 q a A q a A 2020 3 28 41 7 2 2PDA与CFG等价 定理7 4对于任意的PDAM 存在CFGG使得L G N M 证明要点 1 构造对应 q1 A1A2 An q a A 难以用产生式 q A a q1 A1A2 An 模拟 同样也难以用 q A a q1 A1 q2 A2 qn An 模拟 2020 3 28 42 7 2 2PDA与CFG等价 PDA的移动 q1 A1A2 An q a A 需要用如下形式的产生式模拟 q A qn 1 a q1 A1 q2 q2 A2 q3 qn An qn 1 q2 qn是分别对应PDA恰 处理完 A1进而处理A2 恰 处理完 An 1进而处理An的状态 当然就有了恰 处理完 An而进入的状态qn 1 这个状态就是 处理完 A后其次栈顶变为栈顶的状态 2020 3 28 43 7 2 2PDA与CFG等价 取CFGG V P S 其中 V S Q QP S q0 Z0 q q Q q A qn 1 a q1 A1 q2 q2 A2 q3 qn An qn 1 q1