欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

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

发布时间：2025/6/17 编程问答 54 豆豆
生活随笔 收集整理的这篇文章主要介绍了 【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★ 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

文章目录

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



参考博客 :

  • 【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )
  • 【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )
  • 【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法 转为 Chomsky 范式 )
  • 【计算理论】下推自动机 PDA 及 计算示例
  • 【计算理论】下推自动机 PDA ( 设计下推自动机 | 上下文无关语法 CFG 等价于 下推自动机 PDA )
  • 【计算理论】上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA )
  • 【计算理论】下推自动机 PDA ( 上下文无关语言 CFL 的 泵引理 | 泵引理反证示例 | 自动机扩展 )




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


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

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

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

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

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


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

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

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





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


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

S→aTb∣b\rm S \to aTb | bS→aTb∣b
T→Ta∣ε\rm T \to Ta|\varepsilonT→Ta∣ε


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

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

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

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

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

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


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

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

ε,S→aTb\rm \varepsilon , S \to aTbε,S→aTb 最终分解为 :
ε,S→b\rm \varepsilon , S \to bε,S→b 读取 S\rm SS 字符放入 b\rm bb 到栈顶替换 S\rm SS 字符 ,
ε,ε→T\rm \varepsilon , \varepsilon \to Tε,ε→T 读取空字符放入 T\rm TT 到栈顶 ,
ε,ε→a\rm \varepsilon , \varepsilon \to aε,ε→a 读取空字符放入 a\rm aa 到栈顶 ;

ε,T→Ta\rm \varepsilon , T \to Taε,T→Ta 最终分解为 :
ε,T→a\rm \varepsilon , T \to aε,T→a , 读取 T\rm TT 字符放入 a\rm aa 到栈顶替换 T\rm TT 字符 ,
ε,ε→T\rm \varepsilon , \varepsilon \to Tε,ε→T , 读取空字符放入 T\rm TT 到栈顶 ;



最终的下推自动机样式

总结

以上是生活随笔为你收集整理的【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。