下推自动机
下推自动机（pushdown automata，简称掌上电脑）是一种有限自动机，它配有一个存储设备，具体来说就是一个堆栈，我们可以将符号推入其中。
下推自动机中的转换读取输入符号，就像有限自动机一样。此外，转换还可以包括从堆栈顶部弹出符号和/或将新符号压入堆栈的堆栈操作。
这是一个典型的掌上电脑转换。
转换有两个部分：从输入中读取的符号和堆栈操作。堆栈操作有两个部分：要从堆栈顶部移除的符号和要压入堆栈的符号。当且仅当所需的符号出现在输入上并且我们想要删除堆栈的符号位于堆栈的顶部时，掌上电脑可以进行转换。如果缺少这两个要求中的任何一个，机器就不能进行转换。
pda还具有忽略给定转换上的输入或堆栈的能力。例如，从输入中读取一个符号，同时忽略我们所做的堆栈
转换的堆栈部分的ε符号表示“什么都不做”。在本例中，我们尝试从堆栈中取出任何内容，也不向堆栈中推送任何内容。
将一个符号压入堆栈而不弹出任何操作
不用强迫我们做任何事就能弹出一个符号
在机器开始运行时，堆栈是空的。根据程序的要求，我们可以也可以不要求在输入结束时堆栈为空。
堆栈字母表
掌上电脑可以与堆栈一起使用的符号集称为堆栈字母表，Γ。通常，堆栈字母表由输入字母表Σ加上在机器中起特殊作用的额外标记符号组成。
一个常用的标记符号$用于标记堆栈的底部。在许多例子中，我们在运行的一开始就在堆栈上放了一个$。$作为一个特殊的标记，让我们知道堆栈是否即将清空。当$重新出现在堆栈顶部时，我们知道堆栈几乎是空的。
一个例子
下面的掌上电脑被设计为接受这种语言
L = {0n1n | n > 0}
pda本质上是不确定的
根据定义，pda是不确定的机器。许多重要的掌上电脑示例都必不可少地使用了不确定性。
这里有一个著名的例子。下面的掌上电脑接受这种语言
L = {wwR | w∈Σ*}
机器使用从状态2到状态3的转换来猜测何时到达输入的中间。状态2和状态3中的堆栈操作强制执行了一个约束，即字符串的倒序前半部分必须与字符串的后半部分匹配。
正式的定义
下推自动机是一个6元组（Q， Σ， Γ， δ, q0， F），其中Q， Σ， Γ和F都是有限集合，并且
- Q是状态的集合，
- Σ是输入字母，
- Γ是堆栈字母表，
- δ：问 × Σε × Γε → P（问 × Γε)为过渡函数，
- 问0 ∈ 问是启动状态，和
- F是可接受状态的集合。