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

举报
韩曙亮 发表于 2022/01/10 23:43:36 2022/01/10
【摘要】 文章目录 一、上下文无关文法 CFG 转为下推自动机 PDA 流程二、上下文无关文法 CFG 转为下推自动机 PDA 示例 2 参考博客 : 【计算理论】上下文无关语法 ( 语法组...

文章目录



参考博客 :





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


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

① 开始状态 : 开始状态 q s t a r t \rm q_{start} qstart​ , 跳转到 q l o o p \rm q_{loop} qloop​ 状态的指令 ε , ε → K \rm \varepsilon , \varepsilon \to K ε,ε→K , 使用 K \rm K K 替换栈内空字符 ε \varepsilon ε , 即将 K \rm K K 放入栈中 ;

② 循环状态 : q l o o p \rm q_{loop} qloop​ 状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;

基本指令 S → a T b ∣ b \rm S \to aTb|b S→aTb∣b 生成为 ε , S → a T b \rm \varepsilon , S \to aTb ε,S→aTb 和 ε , S → b \rm \varepsilon , S \to b ε,S→b 两条指令 , 前面都是读取空字符作为栈读取的信息 ;

终端字符指令 , 如果存在终端字符 a \rm a a 和 b \rm b b , 那么生成 a , a → ε \rm a, a \to \varepsilon a,a→ε 和 b , b → ε \rm b, b \to \varepsilon b,b→ε 两条指令 , 含义是读取栈顶 a \rm a a 字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;


③ 接受状态 : q l o o p \rm q_{loop} qloop​ 状态跳转到 q a c c e p t \rm q_{accept} qaccept​ 指令是 ε , K → ε \rm \varepsilon , K \to \varepsilon ε,K→ε , 栈顶读取到 K \rm K K 字符删除 ;

④ 拆分指令 : 在循环状态 q l o o p \rm q_{loop} qloop​ 中的基本指令中存在多字符指令 , 如 ε , S → a T b \rm \varepsilon , S \to aTb ε,S→aTb , 读取到空字符 ε \varepsilon ε , 使用 a T b \rm aTb aTb 字符替换栈顶的 S \rm S S 字符 , 这是 3 3 3 个字符 , 肯定不行 , 需要逐个放进去 , 先放 b \rm b b , 再放 T \rm T T , 最后放 a \rm a a ;

最终分解为
ε , S → b \rm \varepsilon , S \to b ε,S→b 读取空字符放入 b \rm b b 到栈顶 ,
ε , ε → T \rm \varepsilon , \varepsilon \to T ε,ε→T 读取空字符放入 T \rm T T 到栈顶 ,
ε , ε → a \rm \varepsilon , \varepsilon \to a ε,ε→a 读取空字符放入 a \rm a a 到栈顶 ;





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


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

R → X R X ∣ S \rm R \to XRX | S R→XRX∣S
S → a T b ∣ b T a \rm S \to aTb | bTa S→aTb∣bTa
T → X T X ∣ X ∣ ε \rm T \to XTX | X |\varepsilon T→XTX∣X∣ε
X → a ∣ b \rm X \to a | b X→a∣b


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

① 开始状态 : 开始状态 q s t a r t \rm q_{start} qstart​ , 跳转到 q l o o p \rm q_{loop} qloop​ 状态的指令 ε , ε → K \rm \varepsilon , \varepsilon \to K ε,ε→K , 使用 K \rm K K 替换栈内空字符 ε \varepsilon ε , 即将 K \rm K K 放入栈中 ;

在这里插入图片描述

② 循环状态 : q l o o p \rm q_{loop} qloop​ 状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;

基本指令 R → X R X ∣ S \rm R \to XRX | S R→XRX∣S 生成为 : ε , R → X R X \rm \varepsilon , R \to XRX ε,R→XRX 和 ε , R → S \rm \varepsilon , R \to S ε,R→S 两条指令 , 前面都是读取空字符作为栈读取的信息 ;

基本指令 S → a T b ∣ b T a \rm S \to aTb | bTa S→aTb∣bTa 生成为 : ε , S → a T b \rm \varepsilon , S \to aTb ε,S→aTb 和 ε , S → b T a \rm \varepsilon , S \to bTa ε,S→bTa 两条指令 , 前面都是读取空字符作为栈读取的信息 ;

基本指令 T → X T X ∣ X ∣ ε \rm T \to XTX | X |\varepsilon T→XTX∣X∣ε 生成为 : ε , T → X T X \rm \varepsilon , T \to XTX ε,T→XTX , ε , T → X \rm \varepsilon , T \to X ε,T→X , ε , T → ε \rm \varepsilon , T \to \varepsilon ε,T→ε 三条指令 , 前面都是读取空字符作为栈读取的信息 ;

基本指令 X → a ∣ b \rm X \to a | b X→a∣b 生成为 : ε , X → a \rm \varepsilon , X \to a ε,X→a 和 ε , X → b \rm \varepsilon , X \to b ε,X→b 两条指令 , 前面都是读取空字符作为栈读取的信息 ;

终端字符指令 : 如果存在终端字符 a \rm a a 和 b \rm b b , 那么生成 a , a → ε \rm a, a \to \varepsilon a,a→ε 和 b , b → ε \rm b, b \to \varepsilon b,b→ε 两条指令 , 含义是读取栈顶 a \rm a a 字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;

在这里插入图片描述


③ 接受状态 : q l o o p \rm q_{loop} qloop​ 状态跳转到 q a c c e p t \rm q_{accept} qaccept​ 指令是 ε , K → ε \rm \varepsilon , K \to \varepsilon ε,K→ε , 栈顶读取到 K \rm K K 字符删除 ;

在这里插入图片描述

④ 拆分指令 : 在循环状态 q l o o p \rm q_{loop} qloop​ 中的基本指令中存在多字符指令 , 如 ε , R → X R X \rm \varepsilon , R \to XRX ε,R→XRX , 读取到空字符 ε \varepsilon ε , 使用 X R X \rm XRX XRX 字符替换栈顶的 R \rm R R 字符 , 这是 3 3 3 个字符 , 肯定不行 , 需要逐个放进去 , 先放 X \rm X X ( 第三个 ) , 再放 R \rm R R , 最后放 X \rm X X ( 第一个 ) ;

ε , R → X R X \rm \varepsilon , R \to XRX ε,R→XRX 最终分解为 :
ε , R → X \rm \varepsilon , R \to X ε,R→X 读取空字符后 , 使用 X \rm X X 字符替换栈顶 R \rm R R 字符 ,
ε , ε → R \rm \varepsilon , \varepsilon \to R ε,ε→R 读取空字符后 , 将 R \rm R R 字符放到到栈顶 ,
ε , ε → X \rm \varepsilon , \varepsilon \to X ε,ε→X 读取空字符后 , 将 X \rm X X 字符放到到栈顶 ;

ε , S → a T b \rm \varepsilon , S \to aTb ε,S→aTb 最终分解为 :
ε , S → b \rm \varepsilon , S \to b ε,S→b 读取空字符后 , 使用 b \rm b b 字符替换栈顶 S \rm S S 字符 ,
ε , ε → T \rm \varepsilon , \varepsilon \to T ε,ε→T 读取空字符后 , 将 T \rm T T 字符放到到栈顶 ,
ε , ε → a \rm \varepsilon , \varepsilon \to a ε,ε→a 读取空字符后 , 将 a \rm a a 字符放到到栈顶 ;

ε , S → b T a \rm \varepsilon , S \to bTa ε,S→bTa 最终分解为 :
ε , S → a \rm \varepsilon , S \to a ε,S→a 读取空字符后 , 使用 a \rm a a 字符替换栈顶 S \rm S S 字符 ,
ε , ε → T \rm \varepsilon , \varepsilon \to T ε,ε→T 读取空字符后 , 将 T \rm T T 字符放到到栈顶 ,
ε , ε → b \rm \varepsilon , \varepsilon \to b ε,ε→b 读取空字符后 , 将 b \rm b b 字符放到到栈顶 ;

ε , T → X T X \rm \varepsilon , T \to XTX ε,T→XTX
ε , T → X \rm \varepsilon , T \to X ε,T→X 读取空字符后 , 使用 X \rm X X 字符替换栈顶 T \rm T T 字符 ,
ε , ε → T \rm \varepsilon , \varepsilon \to T ε,ε→T 读取空字符后 , 将 T \rm T T 字符放到到栈顶 ,
ε , ε → X \rm \varepsilon , \varepsilon \to X ε,ε→X 读取空字符后 , 将 X \rm X X 字符放到到栈顶 ;



最终的下推自动机样式 :

在这里插入图片描述

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111469572

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入