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

韩曙亮

发布于 2023-03-28 12:19:28

9000

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

参考博客 :

一、下推自动机计算过程

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

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

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

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

1, 0 \to ε

$1 , 0 \to \varepsilon$

① 自动机字符读取 : 左侧的

1

$1$

是从带子上读取的字符 ;

② 栈内字符存取操作 :

0 \to ε

$0 \to \varepsilon$

是需要在栈上进行的操作 , 将栈顶的

0

$0$

取出 , 然后将

ε

$\varepsilon$

放入到栈中 , 相当于在栈中 , 使用

ε

$\varepsilon$

将栈顶的

0

$0$

替换掉 ;

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

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

① 开始状态 : 开始状态

q_{s t a r t}

$\rm q_{start}$

, 跳转到

q_{l o o p}

$\rm q_{loop}$

状态的指令

ε, ε \to K

$\rm \varepsilon , \varepsilon \to K$

, 使用

K

$\rm K$

替换栈内空字符

ε

$\varepsilon$

, 即将

K

$\rm K$

放入栈中 ;

② 循环状态 :

q_{l o o p}

$\rm q_{loop}$

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

基本指令

S \to a T b | b

$\rm S \to aTb|b$

生成为 "

ε, S \to a T b

$\rm \varepsilon , S \to aTb$

" 和 "

ε, S \to b

$\rm \varepsilon , S \to b$

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

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

a

$\rm a$

和

b

$\rm b$

, 那么生成

a, a \to ε

$\rm a, a \to \varepsilon$

和

b, b \to ε

$\rm b, b \to \varepsilon$

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

a

$\rm a$

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

③ 接受状态 :

q_{l o o p}

$\rm q_{loop}$

状态跳转到

q_{a c c e p t}

$\rm q_{accept}$

指令是

ε, K \to ε

$\rm \varepsilon , K \to \varepsilon$

, 栈顶读取到

K

$\rm K$

字符删除 ;

④ 拆分指令 : 在循环状态

q_{l o o p}

$\rm q_{loop}$

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

ε, S \to a T b

$\rm \varepsilon , S \to aTb$

S

$\rm S$

读取到空字符

ε

$\varepsilon$

, 使用

a T b

$\rm aTb$

字符替换栈顶的

S

$\rm S$

字符 , 这是

3

$3$

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

b

$\rm b$

, 再放

T

$\rm T$

, 最后放

a

$\rm a$

;

最终分解为

ε, S \to b

$\rm \varepsilon , S \to b$

读取空字符放入

b

$\rm b$

到栈顶 ,

ε, ε \to T

$\rm \varepsilon , \varepsilon \to T$

读取空字符放入

T

$\rm T$

到栈顶 ,

ε, ε \to a

$\rm \varepsilon , \varepsilon \to a$

读取空字符放入

a

$\rm a$

到栈顶 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-12-21，如有侵权请联系 cloudcommunity@tencent.com 删除

存储

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

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

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

登录后参与评论

暂无评论