プッシュダウン・オートマトン (PDA)

有限オートマトンにスタックを1本足したもの。 これが受理できる言語のクラスが文脈自由言語 (CFL) とぴったり一致する。有限オートマトンは状態しか持てないが、PDA は状態 + スタックトップで遷移を決められるぶんだけ強い。

形式的定義

7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$:

記号	意味	プログラマの感覚
$Q$	状態集合	enum
$\Sigma$	入力アルファベット	読む文字
$\Gamma$	スタックアルファベット	スタックに積む記号
$\delta$	遷移関数	後述
$q_0$	初期状態
$Z_0$	スタック初期記号	底のマーカー
$F$	受理状態集合

肝は遷移関数の形:

δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)

「今の状態・入力文字・スタックトップ」の3つを見て、「次の状態」と「スタックトップを何に書き換えるか（複数記号 = push、ε = pop、1記号 = 据え置き）」を決める。有限オートマトンの $\delta: Q \times \Sigma \to Q$ に「× スタックトップ」が増えただけ。

// 有限オートマトン: 状態だけで判断
type FA  = (state: string, input: string) => string;

// PDA: 状態 + スタックトップで判断し、スタックも書き換える
type PDA = (state: string, input: string | "ε", stackTop: string)
  => Array<{ next: string; replaceTop: string[] }>;
//                                          ^^^^^^^^ [] = pop, [x] = 据え置き, [a,b] = push

Σ ∪ {ε} の ε に注目 — 入力を読まずにスタックだけ操作する遷移が許される。これが PDA の表現力の一部を支えている。

受理の2方式は等価

最終状態受理: 入力を読み切ったとき状態が $F$ に入っていれば受理
空スタック受理: 入力を読み切ったときスタックが空なら受理

どちらの方式でも受理できる言語クラスは同じ（互いに変換可能）。底マーカー $Z_0$ を使えば一方を他方でシミュレートできる。

最大の罠: NPDA ≠ DPDA

有限オートマトンでは非決定性(NFA)を決定性(DFA)に必ず変換できる(部分集合構成法)。PDA ではこれが成り立たない。

// 非決定性 PDA (NPDA) = 全選択肢を試す（バックトラック/並行探索）
// 決定性 PDA (DPDA)  = 各時点で遷移先がたかだか1つ

	受理できる言語
NPDA	文脈自由言語 (CFL) 全体
DPDA	決定性文脈自由言語 (DCFL) — CFL の真部分集合

決定化できない具体例が回文 ${w w^R}$。中央がどこか入力を見ただけでは分からないので、「ここが折り返し地点だ」と非決定的に賭けるしかない。DPDA には先読みで中央を当てる手段がなく、回文語は DPDA では受理できない。

// a^n b^n は DPDA でいける（a→push, b→pop で機械的）
// w w^R（回文）は NPDA が必要（折り返し位置の推測が要る）

これが理論上重要なのは、「非決定性は飾りではなく本質的な計算力の差」を示す数少ない例だから。正規言語では非決定性は便利さでしかなかった。

パーサ理論との接続

実用のパーサが扱うのは DCFL（= DPDA で読める範囲）。バックトラックなしで線形時間に処理したいから、言語設計の側を DPDA に収まるよう制約する。

// 再帰下降パーサ = コールスタックを PDA のスタックとして使う DPDA
function parseExpr(): Expr {
  if (peek() === "(") {
    consume("(");          // push 相当（再帰に入る）
    const e = parseExpr(); // スタックが伸びる
    consume(")");          // pop 相当
    return e;
  }
  return parseAtom();
}
// LL(k) / LR(k) はいずれも「k 文字先読みで遷移を一意化した DPDA」

2スタックにするとチューリング完全

スタックを2本にした PDA はチューリングマシンと等価になる。

スタック1 = テープの左側、スタック2 = テープの右側
ヘッドの左移動 = stack1.pop() → stack2.push()
ヘッドの右移動 = stack2.pop() → stack1.push()

1本のスタックでは「片側からしか触れない」制約が CFL の壁を作っていたが、2本あれば任意位置のメモリを再現できてしまう。PDA の限界はスタックが1本だったことに尽きる、という見方ができる。

限界（1本スタックの壁）

// a^n b^n c^n は PDA では判定できない
// a を push して b で pop し終えた時点でスタックは空
// → c の個数を照合する手がかりがもう残っていない
// これが Type 2 ⊊ Type 1 の境界（→ ポンピング補題で厳密に証明される）