下推自动机(push-down automata, PDA)
1. 定义
PDA 可以看成是一个带有附加的下推存储器的有限自动机，下推存储器是一个栈。如下图所示：
定义如下：
一个不确定的PDA可以表达成一个7元组：
-
是输入符号的有穷集合；
-
是状态的有限集合；
-
是初始状态；
-
为下推存储器符号的有穷集合；
-
为最初出现在下推存储器顶端的符号;
-
是终止状态集合,
-
是从
到
子集的映射。
2. 映射关系 的解释
3. 符号约定
4. 下推自动机接受的语言
下推自动机 所接受的语言定义为：
5. 举例
下推自动机接受语言
，其中，
,
定义如下:
那么：
另外两种自动机
1. 图灵机
- 图灵机与0型文法等价；
- 图灵机与有限自动机(FA)的区别：图灵机可以通过其读/写头改变输入带的字符。
2. 线性带限自动机
- 线性带限自动机与1型文法等价；
- 线性带限自动机是一个确定的单带图灵机，其读写头不能超越原输入带上字符串的初始和终止位置，即线性带限自动机的存储空间被输入符号串的长度所限制。
各类自动机的区别
各类自动机的主要区别是它们能够使用的信息存储空间的差异：有限状态自动机只能用状态来存储信息；下推自动机除了可以用状态以外，还可以用下推存储器(栈)；线性带限自动机可以利用状态和输入/输出带本身。因为输入/输出带没有“先进后出”的限制，因此，其功能大于栈；而图灵机的存储空间没有任何限制。
语言与识别器的对应关系
识别器是有穷地表示无穷语言的另一种方法。每一个语言的句子都能被一定的识别器所接受。
