Aritalab:Lecture/Automata/PushDown

まとめ

ここではプッシュダウンオートマトンと文脈自由言語の等価性を示します。プッシュダウンオートマトンは補助記憶としてスタックを一つ備えています。スタックの大きさは有限ではなく（無限大になりうる）、言語 { 0ⁿ1ⁿ | n ≥ 0 } も簡単に認識できます。0を読んでスタックに 0 を積み、その後 1を読んだ数だけスタックから 0 を取り出します。読み終わったときにスタックがちょうど空になった時だけ受理すれば良いのです。

プッシュダウンオートマトン

状態 K, 入力記号　Σ, スタック記号 Γ の各有限集合を与えられたとき、プッシュダウンオートマトン (PDA) は M = ( K, Σ, Γ, δ, s₀, z₀ ) で与えられます。s₀ ∈ K, z₀ ∈ Γ はそれぞれ初期状態、スタック上の初期記号です。δ は状態遷移関数ですが、有限オートマトンの時と異なり、K × Σ × Γ から K × Γ^* の有限部分集合族の中への写像となっています。（有限オートマトンの時は、有限部分集合族ではなく、K × Γ^* 中への写像でした。）つまり、最初から非決定性のオートマトンとして定義します。またスタック初期記号 z₀ を利用するのは、状態遷移関数の定義としてスタックの中身が最初に空であると困るからです。ここで PDA の定義に受理状態 F ⊂ K が入っていない理由は後述します。

様相

動作途中におけるPDAの状況を様相と呼び、状態 s, 読み残している入力記号列 y ∈ Σ^*, スタックの内容 σ ∈ Γ^* の組 ( s, y, σ ) で表します。様相が与えられれば、PDAの動作は一意に決まる点に注意してください。

様相 S₁ から S₂ に状態遷移関数によって移るとき S₁ ⇒ S₂　と書きます。何ステップかで移動するときは、S₁ ⇒^* S₂ と書きます。ある文字列 x を入力としてPDAを動かし、スタックの中身がちょうど空になるとき、 x は PDA によって受理されるといいます。様相で書くと

( s₀, x, z₀ ) ⇒^* ( s, ε, ε )

です。PDAでは受理状態というものを定義せず、入力文字列を読み終わったときにスタックが空であれば受理とみなします。