1. 下推自动机¶
1.1. PDA：下推自动机¶
DFA 和 NFA 的一个显著特征是没有内存（memory）。 因此，除了它们当前所处的状态（state）之外，没有任何历史记录或其他方式可以存储信息。 这限制了它们能够识别的语言（language）范围。
考虑仅仅赋予机器使用一个计数器（counter）变量的能力能带来什么。 例如，用一个计数器很容易识别平衡括号的语言。 看到左括号时就将计数器加一，看到右括号时就将计数器减一。 如果计数器变为负数，则拒绝（reject）。 如果处理完串（string）后计数器为零，则接受，否则拒绝。 同样，计数器也能识别由 \(a^nb^n\) 形式的串构成的语言。
不过，除了计数器之外，另一种存储方案是使用栈（stack）。 可以通过把左括号压入（push）栈、遇到右括号时弹出（pop）栈顶，来识别平衡括号。 \(a^nb^n\) 形式的串同样可以先把开头的 a 压入栈，然后在处理 b 时把它们从栈中弹出。 使用栈具备计数器的全部能力，并且具有更大的灵活性。
在接下来的几章中，我们将研究两类带内存的机器。 下推自动机（PDA）用栈作为内存， 我们将看到这使它能够识别比 DFA 或 NFA 范围更广的语言。 图灵机（Turing machine）的内存形式比 PDA 更灵活， 这将使它能够识别范围更广的语言。
1.2. PDA 的转移类型¶
1.3. PDA 接受模型——最终状态接受¶
1.4. PDA 接受模型——空栈接受¶
1.5. 接受定义的等价性¶
1.6. 思考题¶
带有栈的 PDA 很容易识别由 \(a^nb^n\) 形式的串构成的语言。 它也能识别由 \(a^nb^nc^n\) 形式的串构成的语言吗？
PDA 能识别语言 $wcw^R$ 吗？ 即由串 $w$ 后跟符号 $c$ 再后跟 $w$ 的反转所构成的语言。 它当然可以，但它能否确定性地做到这一点呢？
PDA 能识别语言 $ww^R$ 吗？ 可以，但它能否确定性地做到这一点呢？
