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では受理状態というものを定義せず、入力文字列を読み終わったときにスタックが空であれば受理とみなします。こうすると、後で文脈自由言語との等価性を示すのが楽になるからです。

文脈自由言語とPDAの等価性

PDAはわざと非決定性に定義してあります。その使い方をまず説明しましょう。

任意の決定性有限オートマトン (DFA) は、プッシュダウンオートマトンで動作を模倣できる

DFA にスタックを足したのが PDA ですが、DFAには受理状態の定義がありPDAにはありません。与えられた DFA Mを PDA で模倣するには、M の入力文字列が終わったときに受理状態にあればスタックを空に、そうでなければスタックが空で無いように設定しなくてはなりません。ここで非決定性を利用します。入力文字列を読み込む度に、行き先が M の受理状態ならスタック初期記号 z₀ をポップする場合と、しない場合の両方に遷移しておく。もし入力文字列がそこで終わるなら、 ( s, ε, ε ) に行き着くので PDA は受理になるし、入力文字列が終わっていない場合は ( s, y, ε ) という様相から移動せずに非受理にできます。この動作は、決定性の PDA だと実現できません。

任意のPDAと1状態PDAの等価性

スタックを利用できる機能は大変強力で、実は任意の有限状態 PDA を 1 状態のPDAで模倣できます。