【计算理论】下推自动机 PDA ( 设计下推自动机 | 上下文无关语法 CFG 等价于 下推自动机 PDA )
文章目录
I . 下推自动机 设计
设计下推自动机 , 可以识别
语言 ;
表示镜面反射 , 如果
是由
组成的字符串
, 那么
就是其镜面反射
字符串 , 然后将
和
串联在一起 ,
;
1 . 首先生成开始状态 ;
开始状态是接受状态 , 因为如果字符串是空字符串 , 空字符串的镜面反射还是空字符串 , 因此读取空字符串后的状态 , 是接受状态 , 开始状态其本身就是接受状态 ;
2 . 向栈底放入 字符
, 用于作为栈底的标识 , 生成
指令 ;
指令包含
部分 : 读取字符 , 和 栈内操作 ;
- 读取字符 : 指的是读取的带子上的字符串 ,
中前面的
指的是从带子上读取
;
- 栈内操作 : 使用某个字符 替换 栈顶字符 ;
中后面的
指的是使用
字符替换栈顶的空字符
;
3 . 镜面反射的前半个镜面 :
入栈 : 每读取一个
, 就将
放入栈中 , 生成指令
;
入栈 : 每读取一个
, 就将
放入栈中 , 生成指令
;
4 . 跳转到新的状态 , 在新的状态执行 后半个镜面的操作 :
无条件跳转就是读取
, 并且栈中元素保持不变 , 即使用
替换栈顶的
;
生成的指令为
当前的下推自动机 :
5 . 镜面反射的后半个镜面 :
出栈 : 每读取一个
, 从栈里拿走一个
, 生成指令
;
出栈 : 每读取一个
, 从栈里拿走一个
, 生成指令
;
6 . 栈清空 , 跳转到最后的 接受状态 : 上述出栈操作执行若干次后, 总能将栈内的字符取出完毕 , 只剩下一个
字符 , 该字符是栈底的标识 ; 此时将
字符从栈内取出即可 ;
生成如下指令 :
指令含义是 读取
字符 , 使用
字符替换栈中的
字符 ;
最后跳转到的状态是接受状态 ;
当前下推自动机为 :
II . 上下文无关语法 ( CFG ) 等价于 下推自动机 ( PDA )
假设某语言由 上下文无关语法 ( CFG ) 生成 , 找到一个 下推自动机 ( PDA ) 识别该语言 ;
构造下推自动机流程 ( PDA ) :
构造下推自动机 , 包含
个状态 , 开始状态
, Loop 循环状态
, 可接受状态
;
1 .
开始状态 :
读取
字符 , 使用
替换栈顶的
, 对应的指令为
其中的
是栈顶的标识 ,
是栈内的实际字符 ;
2 .
循环阶段 , 根据 上下文无关语法 ( CFG ) 做替换 ;
① 当栈顶是变元时 , 作变换 , 读取
, 即什么都不读取 , 将栈顶的变元 替换成
, 生成的 下推自动机 指令为 "
" , 对应着的上下文无关语法规则为
;
② 当栈顶是终端字符 ( 常元 ) , 让带子上的 读头 读取一个终端字符 , 对应的栈中 , 将栈顶的终端字符删除 , 相当于使用
替换终端字符 , 生成指令 "
" ;
一直读取 终端字符 , 并将栈顶的终端字符删除 , 一直循环该操作 , 直到 栈顶是一个变元 未为止 ;
3 . 跳转到
状态 : 当栈内的字符都出栈后 , 只剩下一个
字符作为栈底标识 , 此时
出栈 , 生成对应的 下推自动机指令 "
" , 即使用空字符
替换栈内的
字符 ;
之后跳转到最后一个状态 ,
可接受状态 ;
相关文章
- 深度揭秘华为边缘计算系统设计的六大核心原则
- 虚拟化与云计算硬核技术内幕 (6) —— 妇女能顶半边天
- 数据采集-存储-计算-图表绘制-电脑展示-手机展示,一条龙最小闭环2021.7.21
- 集中趋势中均值、中位数、众数以及偏态分布、偏度和峰度计算相关
- simon二阶段设计样本量计算
- Schrödinger计算设计的药物SGR-1505 IND获FDA批准
- 对标CASP,工业界和学术界发起CACHE挑战,弥合分子发现和计算设计之间的差距
- C语言中数组长度的计算详解
- PHP 通过经纬度计算距离
- R语言计算IV值
- 【计算理论】图灵机 ( 接受状态作用 | 格局 | 图灵机语言 | 图灵机设计复杂性 )
- 【计算理论】计算理论总结 ( 图灵机设计示例 ) ★★
- 开课了!AI助力能源材料计算模拟设计,这个系列讲座不可错过
- Hadoop综合练习第四节–MapReduce计算气象温度等例子详解大数据
- 专访清微智能尹首一:理想的计算应该是架构随着软件变
- 如何使用 Oracle 进行时间差计算?(oracle时间差计算)
- 解锁Linux系统中的计算工具:BC(linuxbc)
- SQL Server中平方根的计算之路(sqlserver平方根)
- 利用Oracle精确测算年龄(oracle准确计算年龄)
- Redis实现高性能计算的利器(什么情况适合用redis)
- Oracle中计算查询中位数的方法(oracle中查中位数)
- Oracle中计算平均数的方法(oracle中取平均数)
- Oracle SUM条件计算细节之分析(oracle sum条件)