文章目录
- 一、上下文无关文法 CFG 转为下推自动机 PDA 流程
- 二、上下文无关文法 CFG 转为下推自动机 PDA 示例 2
参考博客 :
- 【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )
- 【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )
- 【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法 转为 Chomsky 范式 )
- 【计算理论】下推自动机 PDA 及 计算示例
- 【计算理论】下推自动机 PDA ( 设计下推自动机 | 上下文无关语法 CFG 等价于 下推自动机 PDA )
- 【计算理论】上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA )
- 【计算理论】下推自动机 PDA ( 上下文无关语言 CFL 的 泵引理 | 泵引理反证示例 | 自动机扩展 )
一、上下文无关文法 CFG 转为下推自动机 PDA 流程
上下文无关文法 CFG 转为下推自动机 PDA 流程 :
① 开始状态 : 开始状态
, 跳转到
状态的指令
, 使用
替换栈内空字符
, 即将
放入栈中 ;
② 循环状态 :
状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;
基本指令
生成为
和
两条指令 , 前面都是读取空字符作为栈读取的信息 ;
终端字符指令 , 如果存在终端字符
和
, 那么生成
和
两条指令 , 含义是读取栈顶
字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;
③ 接受状态 :
状态跳转到
指令是
, 栈顶读取到
字符删除 ;
④ 拆分指令 : 在循环状态
中的基本指令中存在多字符指令 , 如
, 读取到空字符
, 使用
字符替换栈顶的
字符 , 这是
个字符 , 肯定不行 , 需要逐个放进去 , 先放
, 再放
, 最后放
;
最终分解为
读取空字符放入
到栈顶 ,
读取空字符放入
到栈顶 ,
读取空字符放入
到栈顶 ;
二、上下文无关文法 CFG 转为下推自动机 PDA 示例 2
将上下文无关语法 ( CFG ) 转为下推自动机 ( PDA ) :
上下文无关文法 CFG 转为下推自动机 PDA 流程 :
① 开始状态 : 开始状态
, 跳转到
状态的指令
, 使用
替换栈内空字符
, 即将
放入栈中 ;
② 循环状态 :
状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;
基本指令
生成为 :
和
两条指令 , 前面都是读取空字符作为栈读取的信息 ;
基本指令
生成为 :
和
两条指令 , 前面都是读取空字符作为栈读取的信息 ;
基本指令
生成为 :
,
,
三条指令 , 前面都是读取空字符作为栈读取的信息 ;
基本指令
生成为 :
和
两条指令 , 前面都是读取空字符作为栈读取的信息 ;
终端字符指令 : 如果存在终端字符
和
, 那么生成
和
两条指令 , 含义是读取栈顶
字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;
③ 接受状态 :
状态跳转到
指令是
, 栈顶读取到
字符删除 ;
④ 拆分指令 : 在循环状态
中的基本指令中存在多字符指令 , 如
, 读取到空字符
, 使用
字符替换栈顶的
字符 , 这是
个字符 , 肯定不行 , 需要逐个放进去 , 先放
( 第三个 ) , 再放
, 最后放
( 第一个 ) ;
最终分解为 :
读取空字符后 , 使用
字符替换栈顶
字符 ,
读取空字符后 , 将
字符放到到栈顶 ,
读取空字符后 , 将
字符放到到栈顶 ;
最终分解为 :
读取空字符后 , 使用
字符替换栈顶
字符 ,
读取空字符后 , 将
字符放到到栈顶 ,
读取空字符后 , 将
字符放到到栈顶 ;
最终分解为 :
读取空字符后 , 使用
字符替换栈顶
字符 ,
读取空字符后 , 将
字符放到到栈顶 ,
读取空字符后 , 将
字符放到到栈顶 ;
读取空字符后 , 使用
字符替换栈顶
字符 ,
读取空字符后 , 将
字符放到到栈顶 ,
读取空字符后 , 将
字符放到到栈顶 ;
最终的下推自动机样式 :