前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★

【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★

作者头像
韩曙亮
发布于 2023-03-28 12:19:44
发布于 2023-03-28 12:19:44
9620
举报

文章目录

参考博客 :

一、上下文无关文法 CFG 转为下推自动机 PDA 流程


上下文无关文法 CFG 转为下推自动机 PDA 流程 :

① 开始状态 : 开始状态

\rm q_{start}

, 跳转到

\rm q_{loop}

状态的指令

\rm \varepsilon , \varepsilon \to K

, 使用

\rm K

替换栈内空字符

\varepsilon

, 即将

\rm K

放入栈中 ;

② 循环状态 :

\rm q_{loop}

状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;

基本指令

\rm S \to aTb|b

生成为

\rm \varepsilon , S \to aTb

\rm \varepsilon , S \to b

两条指令 , 前面都是读取空字符作为栈读取的信息 ;

终端字符指令 , 如果存在终端字符

\rm a

\rm b

, 那么生成

\rm a, a \to \varepsilon

\rm b, b \to \varepsilon

两条指令 , 含义是读取栈顶

\rm a

字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;

③ 接受状态 :

\rm q_{loop}

状态跳转到

\rm q_{accept}

指令是

\rm \varepsilon , K \to \varepsilon

, 栈顶读取到

\rm K

字符删除 ;

④ 拆分指令 : 在循环状态

\rm q_{loop}

中的基本指令中存在多字符指令 , 如

\rm \varepsilon , S \to aTb

,

\rm S

读取到空字符

\varepsilon

, 使用

\rm aTb

字符替换栈顶的

\rm S

字符 , 这是

3

个字符 , 肯定不行 , 需要逐个放进去 , 先放

\rm b

, 再放

\rm T

, 最后放

\rm a

;

最终分解为

\rm \varepsilon , S \to b

读取空字符放入

\rm b

到栈顶 ,

\rm \varepsilon , \varepsilon \to T

读取空字符放入

\rm T

到栈顶 ,

\rm \varepsilon , \varepsilon \to a

读取空字符放入

\rm a

到栈顶 ;

二、上下文无关文法 CFG 转为下推自动机 PDA 示例 1


将上下文无关语法 ( CFG ) 转为下推自动机 ( PDA ) :

\rm S \to aTb | b
\rm T \to Ta|\varepsilon

上下文无关文法 CFG 转为下推自动机 PDA 流程 :

① 开始状态 : 开始状态

\rm q_{start}

, 跳转到

\rm q_{loop}

状态的指令

\rm \varepsilon , \varepsilon \to K

, 使用

\rm K

替换栈内空字符

\varepsilon

, 即将

\rm K

放入栈中 ;

② 循环状态 :

\rm q_{loop}

状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;

基本指令

\rm S \to aTb|b

生成为

\rm \varepsilon , S \to aTb

\rm \varepsilon , S \to b

两条指令 , 前面都是读取空字符作为栈读取的信息 ;

基本指令

\rm T \to Ta|\varepsilon

生成为

\rm \varepsilon , T \to Ta

\rm \varepsilon , T \to \varepsilon

两条指令 , 前面都是读取空字符作为栈读取的信息 ;

终端字符指令 , 如果存在终端字符

\rm a

\rm b

, 那么生成

\rm a, a \to \varepsilon

\rm b, b \to \varepsilon

两条指令 , 含义是读取栈顶

\rm a

字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;

③ 接受状态 :

\rm q_{loop}

状态跳转到

\rm q_{accept}

指令是

\rm \varepsilon , K \to \varepsilon

, 栈顶读取到

\rm K

字符删除 ;

④ 拆分指令 : 在循环状态

\rm q_{loop}

中的基本指令中存在多字符指令 , 如

\rm \varepsilon , S \to aTb

,

\rm S

读取到空字符

\varepsilon

, 使用

\rm aTb

字符替换栈顶的

\rm S

字符 , 这是

3

个字符 , 肯定不行 , 需要逐个放进去 , 先放

\rm b

, 再放

\rm T

, 最后放

\rm a

;

\rm \varepsilon , S \to aTb

最终分解为 :

\rm \varepsilon , S \to b

读取

\rm S

字符放入

\rm b

到栈顶替换

\rm S

字符 ,

\rm \varepsilon , \varepsilon \to T

读取空字符放入

\rm T

到栈顶 ,

\rm \varepsilon , \varepsilon \to a

读取空字符放入

\rm a

到栈顶 ;

\rm \varepsilon , T \to Ta

最终分解为 :

\rm \varepsilon , T \to a

, 读取

\rm T

字符放入

\rm a

到栈顶替换

\rm T

字符 ,

\rm \varepsilon , \varepsilon \to T

, 读取空字符放入

\rm T

到栈顶 ;

最终的下推自动机样式

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-12-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 一、上下文无关文法 CFG 转为下推自动机 PDA 流程
  • 二、上下文无关文法 CFG 转为下推自动机 PDA 示例 1
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档