Can you summarize the following document?
        
  下推自动机比有限状态自动机复杂:除了有限状态组成部分外,还包括一个长度不受限制的栈;下推自动机的状态迁移不但要参考有限状态部分,也要参照栈当前的状态;状态迁移不但包括有限状态的变迁,还包括一个栈的出栈或入栈过程。下推自动机可以形象的理解为,借由加上读取一个容量无限栈的能力,扩充一个能做formula_1-转移的非确定有限状态自动机。  下推自动机存在“确定”与“非确定”两种形式,两者并不等价。(对有限状态自动机两者是等价的)  每一个下推自动机都接受一个形式语言。被“非确定下推自动机”接受的语言是上下文无关语言。  如果我们把下推自动机扩展,允许一个有限状态自动机存取两个栈,我们得到一个能力更强的自动机,这个自动机与图灵机等价。  下推自动机作为一个形式系统最早于1961年出现在 Oettinger 的论文中。它与上下文无关文法的等价性是由乔姆斯基于1962年发现的。

  PDA 形式定义为 6-元组:  formula_2 这里的  计算定义 1  对于任何 PDA formula_2,计算路径是一个有序的(n+1)-元组 formula_13,这里的 formula_14,它满足如下条件:  (i) formula_15 对于 i = 0, 1, 2..., n-1,  (ii) formula_17 使得  在直觉上,PDA 在计算过程中任何一点上都面对着多种可能性,从栈顶读一个符号并把它替代为另一个符号,从栈顶读一个符号并删除它而不替换,不从栈顶读任何符号但压入另一个符号进去,或什么都不做。所有这些都同时由等式 formula_19 和 formula_20 来支配。formula_21 是紧接在第 i+1 次转移移动之前的栈内容,而 formula_22 是要从栈顶去除的符号。formula_23 是紧接在第 i+1 次转移移动之后栈内容,而 formula_24 是在第 i+1 次转移移动期间要增加到栈上的符号。  formula_22 和 formula_24 二者都可以 formula_27。  如果 formula_28 而 formula_29,则 PDA 从栈读一个符号并把它替代为另一个符号。  如果 formula_28 而 formula_31,则 PDA 从栈读一个符号并删除它而不替换。  如果 formula_32 而 formula_29,则 PDA 简单的增加一个符号到栈上。  如果 formula_32 而 formula_31,则 PDA 保持栈不变动。  注意当 n=0 时,计算路径就是单元素集合 formula_36。  计算定义 2  对于任何输入 formula_37,M 接受 w,如果存在计算路径 formula_38 和有限序列 formula_39,使得  (i) 对于每个 i = 0, 1, 2...m,formula_40 都在计算路径上。就是说  (ii) formula_44 对于每个 i = 0, 1, 2...m-1。  (iii) formula_47,如果 formula_48  (iv) formula_51 且 formula_52  注意上述定义不提供测试空栈的机制。要这么做你需要在所有计算开始前在栈上写一个特殊符号,使得 PDA 可以在检测到这个符号的时候有效的识别出栈已经空了。形式的说,实现它可通过介入转移 formula_53这里的 $ 是特殊符号。

  下面是识别语言 formula_54 的 PDA 的形式描述:  formula_55

  下面展示上述 PDA 如何计算不同的输入字符串。  (a) 输入字符串 = 0011  (b) 输入字符串 = 001  (c) 输入字符串 = formula_1

  GPDA 是在一个步骤内写入整个字符串到栈上或从栈上去除整个字符串的 PDA。  GPDA 形式定义为 6-元组 formula_2  GPDA 的计算规则同于 PDA,除了 a 和 b 现在是字符串而不是符号之外。  GPDA 和 PDA 是等价的,如果一个语言可被一个 PDA 识别,它也可被一个 GPDA 识别,反之亦然。  可以使用下列模拟公式化对 GPDA 和 PDA 的等价性的一个分析式证明:  设 formula_66(q, w, xx...x) formula_127 (q, yy...y) 是 GPDA 的转移。  这里的 q, q formula_70 Q, w formula_129, xx...x formula_130, mformula_1310, yy...y formula_130, nformula_1310。  构造 PDA 的下列转移:
在自动机理论中,下推自动机(Pushdown automaton)是使用了包含数据的栈的有限自动机。