【计算理论】下推自动机 PDA ( 设计下推自动机 | 上下文无关语法 CFG 等价于 下推自动机 PDA )

文章目录

• I . 下推自动机 设计
  • II . 上下文无关语法 ( CFG ) 等价于 下推自动机 ( PDA )

I . 下推自动机 设计

设计下推自动机 , 可以识别

语言 ;

表示镜面反射 , 如果

是由

组成的字符串

, 那么

就是其镜面反射

字符串 , 然后将

和

串联在一起 ,

;

1 . 首先生成开始状态 ;

开始状态是接受状态 , 因为如果字符串是空字符串 , 空字符串的镜面反射还是空字符串 , 因此读取空字符串后的状态 , 是接受状态 , 开始状态其本身就是接受状态 ;

2 . 向栈底放入 字符

, 用于作为栈底的标识 , 生成

指令 ;

指令包含

部分 : 读取字符 , 和 栈内操作 ;

• 读取字符 : 指的是读取的带子上的字符串 ,

中前面的

指的是从带子上读取

;

• 栈内操作 : 使用某个字符 替换 栈顶字符 ;

中后面的

指的是使用

字符替换栈顶的空字符

;

3 . 镜面反射的前半个镜面 :

入栈 : 每读取一个

, 就将

放入栈中 , 生成指令

;

入栈 : 每读取一个

, 就将

放入栈中 , 生成指令

;

4 . 跳转到新的状态 , 在新的状态执行 后半个镜面的操作 :

无条件跳转就是读取

, 并且栈中元素保持不变 , 即使用

替换栈顶的

;

生成的指令为

当前的下推自动机 :

5 . 镜面反射的后半个镜面 :

出栈 : 每读取一个

, 从栈里拿走一个

, 生成指令

;

出栈 : 每读取一个

, 从栈里拿走一个

, 生成指令

;

6 . 栈清空 , 跳转到最后的 接受状态 : 上述出栈操作执行若干次后, 总能将栈内的字符取出完毕 , 只剩下一个

字符 , 该字符是栈底的标识 ; 此时将

字符从栈内取出即可 ;

生成如下指令 :

指令含义是 读取

字符 , 使用

字符替换栈中的

字符 ;

最后跳转到的状态是接受状态 ;

当前下推自动机为 :

II . 上下文无关语法 ( CFG ) 等价于 下推自动机 ( PDA )

假设某语言由 上下文无关语法 ( CFG ) 生成 , 找到一个 下推自动机 ( PDA ) 识别该语言 ;

构造下推自动机流程 ( PDA ) :

构造下推自动机 , 包含

个状态 , 开始状态

, Loop 循环状态

, 可接受状态

;

1 .

开始状态 :

读取

字符 , 使用

替换栈顶的

, 对应的指令为

其中的

是栈顶的标识 ,

是栈内的实际字符 ;

2 .

循环阶段 , 根据 上下文无关语法 ( CFG ) 做替换 ;

① 当栈顶是变元时 , 作变换 , 读取

, 即什么都不读取 , 将栈顶的变元 替换成

, 生成的 下推自动机 指令为 "

" , 对应着的上下文无关语法规则为

;

② 当栈顶是终端字符 ( 常元 ) , 让带子上的 读头 读取一个终端字符 , 对应的栈中 , 将栈顶的终端字符删除 , 相当于使用

替换终端字符 , 生成指令 "

" ;

一直读取 终端字符 , 并将栈顶的终端字符删除 , 一直循环该操作 , 直到 栈顶是一个变元 未为止 ;

3 . 跳转到

状态 : 当栈内的字符都出栈后 , 只剩下一个

字符作为栈底标识 , 此时

出栈 , 生成对应的 下推自动机指令 "

" , 即使用空字符

替换栈内的

字符 ;

之后跳转到最后一个状态 ,

可接受状态 ;