文章目录

• 一、 下推自动机
• 二、下推自动机 计算过程
• 三、下推自动机 计算结果
• 四、下推自动机 计算示例

一、 下推自动机

1 . 下推自动机 由来 : 下推自动机 ( PDA ) 是在 确定性有限自动机 ( DFA ) 基础上 扩展而来的 ;

2 . 下面是 下推自动机 ( PDA ) 的示意图 :

① 输入字符串 : 将输入的字符写在右侧的带子上 ;

② 开始状态 : 读取指针 ( 读头 ) 开始指向最左端字符 , 此时处于开始状态 ;

③ 启动自动机 , 自动机根据读取的指令进行计算 ;

④ 读取指令 : 每读取一个字符 , 自动机跳转到一个新的状态 , 指针向后移动一个格子 ;

⑤ 自动机停止 : 当读取指针指向输入的最右端 , 此时自动机就停止了 , 此时查看当前状态 , 如果当前是接受状态 , 称自动机接受该字符串 ( 带子上写的字符组成的字符串 ) , 反之 , 自动机不接受该字符串 ;

二、下推自动机 计算过程

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

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

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

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

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

是从带子上读取的字符 ;

② 栈内字符存取操作 :

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

取出 , 然后将

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

将栈顶的

替换掉 ;

三、下推自动机 计算结果

1 . 下推自动机 ( PDA ) 是否接受字符串 : 将带子上的字符全部读取完毕后 , 此时的状态如果是 接受状态 , 那么带子上的字符组成的字符串就可以被 下推自动机接受 ;

2 . 计算能力 : 下推自动机 ( PDA ) 比 确定性有限自动机 ( DFA ) 多了栈上的操作 , 下推自动机 ( PDA ) 的计算能力比有限自动机 ( DFA ) 计算能力高 ;

3 . 语言识别能力 : 确定性有限自动机 ( DFA ) 是不能识别

语言的 , 但是 下推自动机 ( PDA ) 是可以认识该语言的 ;

四、下推自动机 计算示例

上图的下推自动机有

个状态

;

读取

字符串 , 并给出 下推自动机 计算过程 ;

指令含义 : 当读取

字符后 ,

指的是在栈上的操作 , 从栈内取出

字符 , 向栈内放入一个

字符 , 本质是在栈中使用

替换

字符 ;

1 . 开始状态 是

, 此时读头指向

位置 , 栈内是空的 ;

2 . 开始状态

: 读取

指令 , 读取

字符后 ,

指的是在栈上的操作 , 从栈内拿走

,

是空字符 , 相当于不用拿 , 并将

字符放入栈 , 相当于使用

替换 栈内 空字符

,

字符的作用 : 下推自动机是无法识别栈底的 ,

作用是辅助下推自动机识别栈底元素 , 当下推自动机读取到

时 , 就知道已经读取到栈底了 ;

开始状态 读取字符 操作

, 最终向栈中放入了字符

;

状态跳转 : 此时 自动机状态 跳转到了

状态 ;

3 .

状态 : 读取

指令 , 读取到一个

, 从栈内拿走

, 使用

替换

, 并将该替换后的

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

替换

; 之后依然保持

状态不变 ;

状态跳转 : 下推自动机状态 仍保持

状态 ;

4 .

状态 : 再次读取

指令 , 读取到一个

, 从栈内拿走

字符 , 使用

替换

, 并将该替换后的

放入栈中 ; 之后依然保持

状态不变 ;

状态跳转 : 下推自动机状态 仍保持

状态 ;

5 .

状态 , 读取

指令 , 读取到一个

, 从栈中拿走一个

, 并将

放入栈中 ,

是空字符串 , 从栈内拿取放入

栈不变 , 相当于将一个

从栈内拿出 ;

状态跳转 : 下推自动机状态 从

状态跳转到

状态 ;

6 .

状态 : 读取

指令 , 从栈中 , 拿走一个

, 将

放入栈内 , 相当于在栈内使用

空字符 替换

, 操作完成后 , 栈内少一个

;

状态跳转 : 下推自动机状态 仍保持

状态 ;

7 .

状态 , 读头读取到了最右端 , 所有字符都读取完毕 , 此时不需要读取任何字符 , 读取

指令 , 从栈内拿走

, 将

放入栈中 , 跳转到

状态 ;

此时 , 栈清空 , 下推自动机停止计算 ;

是个双圈 , 接受状态 , 说明该下推自动机接受该

字符串 ;