有限自动机理论05章下推自动机.ppt

第五章下推自动机PDA FA识别正则语言 右线性语言 PDA识别上下文无关语言 FA只能处理正则语言正则文法生成无穷语言是由于A wA不需要记录w的个数 无关文法生成无穷语言A A 需要记录 和 之间的对应关系无法用FA的有穷个状态来表示 为FA扩充一个无限容量的栈用栈的内容和FA的状态结合起来就可以表示无限存储 这种模型就是下推自动机PDA PDA作为形式系统最早于1961年出现在Oettinger的论文中 与上下文无关文法的等价性由Chomsky于1962年发现 与FA比较 PDA具有一个栈存储器有两个操作 入栈 将内容压入栈中出栈 将栈顶元素移出 下推自动机物理模型 a1 a2 a3 aj an an 1 FSC 存储带 栈存储器 栈存储器 存放不同于字母的符号只能对栈顶元素进行操作 下推自动机动作根据 FSC当前的状态输入带上的当前字符栈顶符号进行状态改变和入栈或出栈操作将读头向右移动一个单元 5 1 1确定的下推自动机 例5 1语言L w w a b 且a b个数相等 暂时不考虑状态 或PDA仅有一个状态 初始 栈为空从左到右逐个扫描串w a b 入栈 若栈为空 当前符号是a 则A入栈若栈为空 当前符号是b 则B入栈若栈顶为A 当前符号是a 则A入栈若栈顶为B 当前符号是b 则B入栈 出栈 若栈顶为A 当前符号是b 则A出栈若栈顶为B 当前符号是a 则B出栈 若串w有相同个数的a和b当且仅当w扫描结束后 栈为空 注意 PDA在两种情况下停机 串扫描结束没有对应的规则 串扫描结束 栈如果为空就接收扫描过的串 对于非正式的算法 用形式化的方式进行描述 特殊的符号Z0表示栈底初始化时先压入栈 规则 指令 若x是w的当前符号D是栈顶符号则用符号串V代替D即将D弹出栈 而将串V压入栈 具体 若x是w的当前符号 栈顶符号为D将D弹出栈将A压入栈 成为新的栈顶 一般地 若x是w的当前符号 栈顶符号为D表示 将D弹出栈将串A1A2 Ak压入栈 A1为新栈顶 例5 1算法的形式化描述 规则表示将w扫描结束后 将栈置成空也表示该PDA可以接收空串 思考 如何接收语言L w w a b 且a和b个数相等 例 语言L anbn n 0 定义 则还可以接收语言 ab n n 0 或 ambm ab n m 0 n 0 等语言 思考 如何接收语言 L anbn n 0 L anbn n 0 L ab n n 0 L ab n n 0 例5 2 L wcwT w a b 识别语言 思想 将w的各个字符压入栈后栈中的内容从栈顶到栈底的顺序刚好是wT的顺序 为了区别压栈和出栈动作增加两个状态 read和matchPDA处于read状态时 处理整个串的前半部分 将对应的符号压入栈 扫描到字母c时PDA的状态转为match开始处理整个串的后半部分 将栈中的内容出栈 规则 若PDA处于状态qw的当前字母是x当前栈顶符号为D则自动机的状态改变为q 并用符号串V代替D 在本例中 用Z代表任意的栈顶符号规则 read a Z read AZ 可以表示以下3条规则 read a Z0 read AZ0 read a A read AA read a B read AB 用下列的规则来描述PDA read a Z read AZ read b Z read BZ read c Z match Z match a A match match b B match match Z0 match 若串w是该语言的合法的串当且仅当w扫描结束后 栈为空 Z0 符号栈 串abbcbba的处理过程 A B read match B 扫描到字母c 栈内的内容 从栈顶到栈底 是扫描过的串的逆与未扫描过的串的顺序相同此时 不作出栈和入栈操作 仅仅把PDA的状态从read改变到match 接收语言L anbn n 0 q0 a Z0 q0 AZ0 q0 a A q0 AA q0 b A q1 q1 b A q1 q1 Z0 q1 5 1 2不确定的下推自动机 例5 3语言L wwT w a b 没有中心点字符在扫描过程中 就没有确定的位置进行状态的变换具有不确定性 使用规则 read Z match Z 来代替 read c Z match Z 即在read状态时 可随时改变为match状态 栈的内容和扫描符号不变 read a Z read AZ read b Z read BZ read Z match Z match a A match match b B match match Z0 match 该PDA是不确定的处于状态read状态时随时都可以进行选择 继续扫描 或状态变换为match 一个串w能够由PDA所识别 仅当串是wwT的形式且PDA状态在中心点进行了变换 对于不确定的PDA和串w若存在至少一个可能的扫描过程使得当串w扫描结束时 栈为空则称串w能够被PDA所识别 接收语言L ab n n 0 q1 a Z0 q2 AZ0 q2 b A q1 q1 Z0 q1 接收语言L ab n n 0 q0 a Z0 q0 AZ0 q0 b A q1 q1 a Z0 q2 AZ0 q2 b A q1 q1 Z0 q1 定义5 1 下推自动机PDA是一个七元式 M Q q0 Z0 F Q是一个有限状态的集合 是输入串的字母集合 是栈内符号集合 q0 Q是开始状态Z0 是栈底符号F Q是接收状态集合 Q Q 对于确定的PDA 有 q x D q V 对于不确定的PDA 有 q V q x D 一般 使用表示 函数 定义5 2PDA格局 或瞬间描述ID 格局代表某个时刻PDA的情况PDA的格局是一个三元式 q w 其中 q为状态 w x1x2 xn还没有被扫描到的串 将扫描x1 Z1Z2 Zm栈的内容 Z1在栈顶 Zm在栈底 PDA 初始格局为 q0 w Z0 接收格局为 q 其中 q Q 与接收状态无关 格局的转换是由于状态转换函数的作用引起的 确定的PDA 引起的格局转换为 q xw A q1 w A1A2 Ak 不确定的PDA 情况1 则 q xw A q1 w A1A2 Ak 则 q xw A q2 xw B1B2 Bj 不确定的PDA 情况2 则 q xw A q1 w A1A2 Ak 则 q xw A q2 w B1B2 Bj 用 代表格局的任意次变换 不确定PDA对于某一格局可能会有不同的下一格局 5 1 3PDA接收语言的两种方式 定义5 3PAD以空栈方式接收的语言为L M 且L M w q0 w Z0 q q Q 接收格局与接收状态无关只要当串w扫描结束 而栈为空则串w被PDA以空栈方式所接收 定义5 4 PAD以终态方式接收的语言为F M 且F M w q0 w Z0 q q F 接收格局与栈是否为空无关只要当串w扫描结束 而PDA处于某个接收状态则串w被PDA以终态方式所接收 定理5 1 语言L被PDA以终态方式所接收当且仅当它被PDA以空栈方式所接收 即终态接收与空栈接收方式等价 证明 略 5 1 4广义PDA和单态PDA 定义5 5广义的PDA是七元式PDA Q q0 Z0 F 除了 外 其余同一般的PDA 其中 Q是一个有限状态的集合 是输入串的字母集合 是栈内符号集合q0 Q是开始状态Z0 是初始的栈底符号F Q是接收状态 终止状态 集合 Q Q q x B1B2 Bk q C1C2 Cn 一般形式为 一般的PDA 栈顶只是一个符号广义PDA的栈顶可以为多个符号 定理5 4 若语言L能由广义PDA所接收则L能够由一般的PDA所接收 证明思路 广义的PDA的一条规则一般PDA的多条规则的组合 就是 证明 对于广义的PDA的任意一条规则增加状态r1 r2 rk 1 改造为 得到一般的PDA 且L L PDA 定义5 6单态PDA 仅有一个状态的PDA规则简化为 等价性 问题 一个NFA是否可以转换为一个单态PDA 思路 NFA Q q0 F 将NFA的状态当作PDA的栈内符号构造单态的PDA Q q0 NFA q x q1 q2 qn 单态的PDA NFA 若q q0 w 单态的PDA 有 w q0 q NFA 若 q x F 单态的PDA 因此 NFA q0 w F 单态的PDA w q0 即L NFA L PDA 右线性文法 G V S P 也可以对应一个单态的PDA 产生式A bBA b PDA的规则 将文法的开始符号S当作是单态PDA的栈底符号 则 对于文法GS w1A w1bB w1bw2 w对于单态PDA w1bw2 S bw2 A w2 B 例5 4语言L anbn n 1 文法S aSBS aBB b 单态PDA 对于串anbn 单态的PDA可能会有以下的格局转换 anbn S n an jbn SBj anbn S n an kbn Bk anbn S n bn Bn 其中 是导出 和 的中间过程 会导致停机 因为没有合适的规则 可以完成最后的转换 bn Bn 使用n 1次规则1次规则n次规则 5 1 5下推自动机的存储技术 参考Turing的存储技术 略 5 1 6PDA扫描多个符号 参考Turing的扫描多个符号技术 略 5 2上下文无关文法和范式 范式是指标准的形式在代数中 2 4 3 6 的范式是1 2 本节讨论在上下文无关文法的几个重要的范式 定理5 5 G是一个上下文无关文法 则存在一个上下文无关文法G 使得 L G L G 若 L G 则G 没有空串产生式 若 L G 则G 有S 且S 不出现在G 的任何产生式的右边 G 中没有A B形式的产生式 证明 前3点是空串定理的内容 见2 6 第4点证明参见参考文献1 5 2 1Chomsky范式 CNF 定义5 7上下文无关文法G V S P 若G的每个产生式是下列形式之一 A BCA B C VA aA V a S 且S不出现在产生式的右边则G是Chomsky范式 CNF 定理5 6 G是一个上下文无关文法 则存在一个等价的上下文无关文法G 使得L G L G 且G 是CNF 证明 对于任意的上下文无关文法G首先使它满足定理5 5的要求对于文法中的任意的产生式A B1B2 Bm 假设每个Bi都是非终结符 若不是 则使用非终结符Bi 来代替Bi 并增加产生式Bi Bi A B1B2 Bm 若m 2 满足了CNF要求 m 3 将它改造为m 1个产生式 A B1B2 Bm A B1C1C1 B2C2 Cm 3 Bm 2Cm 2Cm 2 Bm 1Bm 其中C1 C2 Cm 2是新加的非终结符得到的文法G 是CNF且L G L G 证毕 5 2 2Greibach范式 GNF 定义5 8上下文无关文法G V S P 是GNF 若G的每个产生式形式为A bWb W V 定理5 7 G是一个上下文无关文法 则存在一个等价的上下文无关文法G 使得L G L G 且G 中没有直接左递归的产生式 即不存在A Av形式的产生式其中 A V v UV 没有直接左递归的文法也称为无直接左递归范式 NLR 证明 见2 7 某些文法可能没有直接左递归 但可能会有间接左递归 定理5 8 G是一个上下文无关文法 则存在一个等价的上下文无关文法G 使得L G L G 且G 中没有间接左递归的产生式 没有间接左递归的文法也称为无间接左递归范式 证明 见2 7 定理5 9 G是任意一个上下文无关文法 则存在一个等价的上下文无关文法G 使得L G L G 且G 是Greibach范式 GNF 对于任意的上下文无关文法G 产生式形式为Ai AjwAi aw 或 假设w包含的字符全为非终结符对于Ai aw 本身就是GNF的形式 对于Ai Ajw 利用消除左递归的算法 在消除左递归的以后 从An 1开始 将An代入到An 1 将An 1代入到An 2 直至A1 再将增加的非终结符的产生式的开头符号代替掉 得到GNF 5 3PDA与上下文无关语言 PDA识别的语言是上下文无关语言 定理5 10 对于上下文无关语言L和文法G若L L G 则语言L能被 广义 不确定的PDA所接收 证明 假设文法是GNF范式构造一个单态的PDA来接收语言L 文法G中有3种形式的产生式 它们分别对应PDA的规则 S A bA bW其中 A V W V 需要证明 语言L L PDA 为证明之 先证明 w1w2 S w2 iffS w1 即扫描串后w1 M栈内符号串为 若上述成立 假设w2 则 w1 S iffS w1 现在用归纳法证明 对串w1的长度进行归纳 w1w2 S w2 iffS w1 证明 基础 当w1 有两种情况 a w2 S w2 S iffS S是成立的 b 若S 在G中 则有 w2 S w2 iffS 是成立的 假设 当w1 时 长度为n时 w1w2 S w2 iffS w1 令 A w2 aw3 将w1a当作新的w1 长度为n 1 则 w1aw3 S aw3 A iffS w1A 而 aw3 A w3 iffA a 因此 w1aw3 S w3 iffS w1a 所以 假设成立 证毕 例5 10 文法G为S L L LL 对于串 构造的单态的PDA 栈底为S 为 S LS L LLL 对于单态的PDA可以构造对应的上下文无关文法G使得L M L G 例5 11有单态的PDA 构造上下文无关文法G 用Z代替Z0作为开始符号 为 Z aAZ bBZ A aAA bB bBB a 例5 12构造PDA 接收语言L w2wT w 0 1 解法1 read match 解法2 GNF PDA 产生L的上下文无关文法 S 2 0S0 1S1 将文法转化成GNF S 2 0SA 1SBA 0B 1 构造单态PDA S 0SA S 1SB S 2 A 0 B 1 定理5 11 对于单态的PDA存在一个上下文无关文法G使得L G L PDA 且G为GNF范式形式 证明 PDA文法B a B a 根据单态的PDA可以得到对应的GNF 而多态的PDA 不可以直接得到GNF 问题 多态PDA如何得到对应的上下文无关文法 定理5 12 对于多态PDA 存在上下文无关文法G