参考博客 :

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

一、下推自动机计算过程

1 . 下推自动机 ( PDA ) 提升了自动机计算能力 : 在上述自动机的基础上 , 提升该自动机的计算能力 , 引入一个新的栈结构 ;

栈特点 : ① 后进先出 , ② 存储能力无限 ;

2 . 下推自动机计算有两个部分 , 一个是字符的读取 , 一个是栈内字符的存取 , 栈内只有最上面的字符会被替换 ;

3 . 下推自动机 ( PDA ) 的指令格式 : 该指令包含了 上述讲的两个操作 ;

$$1,0\to \epsilon$$

① 自动机字符读取 : 左侧的 $1$ 是从带子上读取的字符 ;

② 栈内字符存取操作 : $0\to \epsilon$ 是需要在栈上进行的操作 , 将栈顶的 $0$ 取出 , 然后将 $\epsilon$ 放入到栈中 , 相当于在栈中 , 使用 $\epsilon$ 将栈顶的 $0$ 替换掉 ;

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

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

① 开始状态 : 开始状态 ${\mathrm{q}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}$ , 跳转到 ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 状态的指令 $\epsilon ,\epsilon \to \mathrm{K}$ , 使用 $\mathrm{K}$ 替换栈内空字符 $\epsilon$ , 即将 $\mathrm{K}$ 放入栈中 ;

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

基本指令 $\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}|\mathrm{b}$ ,
生成为 " $\epsilon ,\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}$ " 和 " $\epsilon ,\mathrm{S}\to \mathrm{b}$ " 两条指令 , 前面都是读取空字符作为栈读取的信息 ;

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

③ 接受状态 : ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 状态跳转到 ${\mathrm{q}}_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}}$ 指令是 $\epsilon ,\mathrm{K}\to \epsilon$ , 栈顶读取到 $\mathrm{K}$ 字符删除 ;

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

最终分解为
$\epsilon ,\mathrm{S}\to \mathrm{b}$ 读取空字符放入 $\mathrm{b}$ 到栈顶 ,
$\epsilon ,\epsilon \to \mathrm{T}$ 读取空字符放入 $\mathrm{T}$ 到栈顶 ,
$\epsilon ,\epsilon \to \mathrm{a}$ 读取空字符放入 $\mathrm{a}$ 到栈顶 ;

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

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