下推自动机

前言

在证明一个语言是上下文无关的时候，有两种选择：可以给出生成它的上下文无关文法，或者给出识别它的 下推自动机(PDA)。本篇所介绍的称为 下推自动机 的计算模型，很像非确定型有穷自动机，但是它有一个称为 栈 的额外设备。栈在控制器的有限存储量之外提供了附加的存储，使得下推自动机能够识别某些非正则语言。

对比示意图

对比示意图

栈的作用体现在它能保存无限的信息量。有穷自动机(DFA) 不能用它的有限存储保存大数据量的字符串，所以它不能识别语言 {}，而 PDA可以用栈保存它所看见的的个数，从而能识别这个语言。因此，栈的无界性使得PDA能够保存大小没有限制的数，下面的非形式化的描述关于语言 {} 的PDA如何工作：

读取输入串的符号，每读一个，把它推入栈，一旦看见之后，每读一个，就把一个 弹出栈，当栈中的被清空时恰好读完输入串，则接受这个输入。如果在还有没有读的时候栈已经被清空，或者在栈中还有的时候已经读完了；或者出现在的后面，则拒绝这个输入。

PDA的形式化定义

，其中

1. ：有穷状态集
2. ：输入字母表，{}
3. ：栈字母表，{}
4. 转移函数
5. ：初始状态
6. ：接受状态(终结状态)集

PDA计算的形式定义

1. ；输入
2. 计算：状态--栈符号串序列
   ，
   其中 ，满足
   • 
   • ；其中
   • ；(或者同时要求 )
   • 接受：对输入存在接受计算
   • (识别，接受)的语言: {接受}

举例说明

假设 {} ，{},{},{},{}，则可得如下转移函数表：

转移函数表

对上表略作说明：当处于状态时，可以读入空串，也不消耗栈底元素，可将 “$”压入栈底进入状态，之后读到压栈，读到将弹出栈，直到读到栈底元素"$"之后结束判断是否在接受状态；

注意：

1. NUL表示不允许该状态出现
2. 这四种状态分别是：没有01；0比1多；0比1少；0的个数与1相同