下推自動機（PDA）
堆疊字母表（stack alphabet）
/ Gamma = the symbol Γ /
當下推自動機在堆疊上記筆記時，它被允許用哪種「字母表」來寫？不一定是輸入中出現的那些字母。堆疊字母表記為 Γ（Gamma），是機器可以推入與彈出堆疊的「另一組」有限符號集合。把它想成機器的私人速記：輸入用一種語言，但它替自己保留的標記可以用另一種語言。
讓堆疊字母表 Γ 與輸入字母表 Σ（Sigma）分開是真的有用。PDA 可以發明專用的記帳符號，這些符號永不出現在任何輸入字串中——例如純粹用來計數 a 的單一標記 X，或一個特殊的「堆疊底」符號，用來提示「此處以下堆疊已空」。在 a^n b^n 的機器裡，輸入字母表是 {a, b}，但堆疊字母表可能是 {X, Z0}：每個 a 推入一個 X，而 Z0 是起始符號，根本從未從輸入中讀到。依慣例 Σ 與 Γ 可以重疊，但也允許是完全不同的集合。
這是一項雖小卻重要的設計自由。由於堆疊符號是獨立選取的，PDA 可以把關於自身進度的豐富資訊編碼進去，而不必侷限於回放輸入字母。日後你會看到把文法轉成 PDA 時，堆疊字母表通常同時容納文法的終端符號「與」變數——這個詞彙量遠大於輸入字母表，用來在堆疊上模擬一次推導。
對 a^n b^n：輸入字母表 Σ = {a, b}；堆疊字母表 Γ = {X, Z0}。符號 X 是純記帳用（每個 a 一個），Z0 標記堆疊底——X 與 Z0 都不會是輸入字串的一部分。
Γ（堆疊字母表）是另一個有限集合，可自由包含私用的記帳符號。
即使 Σ 與 Γ 共用某些字母，它們在概念上仍是不同集合。把兩者混為一談是常見的錯誤：一次轉移讀的是 Σ 裡的「輸入」符號，但推入與彈出的是 Γ 裡的「堆疊」符號。
又稱
另見