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)是使用了包含資料的棧的有限自動機。