参考博客 :
上下文无关文法 CFG 转为下推自动机 PDA 流程 :
① 开始状态 : 开始状态
, 跳转到
状态的指令
, 使用
替换栈内空字符
, 即将
放入栈中 ;
② 循环状态 :
状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;
基本指令
生成为
和
两条指令 , 前面都是读取空字符作为栈读取的信息 ;
终端字符指令 , 如果存在终端字符
和
, 那么生成
和
两条指令 , 含义是读取栈顶
字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;
③ 接受状态 :
状态跳转到
指令是
, 栈顶读取到
字符删除 ;
④ 拆分指令 : 在循环状态
中的基本指令中存在多字符指令 , 如
,
读取到空字符
, 使用
字符替换栈顶的
字符 , 这是
个字符 , 肯定不行 , 需要逐个放进去 , 先放
, 再放
, 最后放
;
最终分解为
读取空字符放入
到栈顶 ,
读取空字符放入
到栈顶 ,
读取空字符放入
到栈顶 ;
将上下文无关语法 ( CFG ) 转为下推自动机 ( PDA ) :
上下文无关文法 CFG 转为下推自动机 PDA 流程 :
① 开始状态 : 开始状态
, 跳转到
状态的指令
, 使用
替换栈内空字符
, 即将
放入栈中 ;
② 循环状态 :
状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;
基本指令
生成为
和
两条指令 , 前面都是读取空字符作为栈读取的信息 ;
基本指令
生成为
和
两条指令 , 前面都是读取空字符作为栈读取的信息 ;
终端字符指令 , 如果存在终端字符
和
, 那么生成
和
两条指令 , 含义是读取栈顶
字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;
③ 接受状态 :
状态跳转到
指令是
, 栈顶读取到
字符删除 ;
④ 拆分指令 : 在循环状态
中的基本指令中存在多字符指令 , 如
,
读取到空字符
, 使用
字符替换栈顶的
字符 , 这是
个字符 , 肯定不行 , 需要逐个放进去 , 先放
, 再放
, 最后放
;
最终分解为 :
读取
字符放入
到栈顶替换
字符 ,
读取空字符放入
到栈顶 ,
读取空字符放入
到栈顶 ;
最终分解为 :
, 读取
字符放入
到栈顶替换
字符 ,
, 读取空字符放入
到栈顶 ;
最终的下推自动机样式
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有