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, 0, A ) = ( s', Z )

と書いた場合、入力 0 によって状態 s から s' に遷移し、スタックの一番上にある記号　A を Z に置き換えることを意味します。A はスタックの先頭にある 1 文字ですが、Z は記号列　(例えば ABABAB ) で構わないことにします。

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

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

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

PDAの具体例と考え方

PDAを用いて { x x^R | x ∈ {0,1}{0,1}* } という言語の認識を考えましょう。例えば 101010 010101 や 11001 10011 などがこの言語に含まれます。

入力記号 0, 1 を読んだ時、スタックにはそれぞれ A, B の記号を積んでいきます。前半の x から後半の x^R にいつ移るかはわからないので、非決定性を用いて x を読み続ける場合と x^R を読む場合の動作をすべて続けます。前者の状態を s₀, 後者の状態を s₁ として状態遷移関数を書くと以下のようになります。

初期状態からの開始
0を読んだらAを積む	σ( s0, 0, z0 ) = ( s0, A )
1を読んだらBを積む	σ( s0, 1, z0 ) = ( s0, B )
非決定性を用いた動作
0を読んだらAを積む、 またはスタック先頭のAを取り去る	σ( s0, 0, A ) = ( s0, AA ); σ( s0, 0, B ) = ( s0, BA ) σ( s0, 0, A ) = ( s1, ε )
1を読んだらBを積む、 またはスタック先頭のBを取り去る	σ( s0, 1, B ) = ( s0, BB ); σ( s0, 1, A ) = ( s0, AB ) σ( s0, 1, B ) = ( s1, ε )
スタックから取り去りはじめた後の長さチェック
0を読んだらスタック先頭のAを取り去る	σ( s1, 0, A ) = { ( s1, ε ) }
1を読んだらスタック先頭のBを取り去る	σ( s1, 1, B ) = { ( s1, ε ) }

入力文字列 010010 に対する受理動作のスタックを左から右に記すと以下のようになります。 3文字読んだところで s₁ に状態遷移した時のみ、スタックから 1 個ずつ取り出せ、最後まで様相が存在します。

入力	0	1	0	0	1	0
状態	s0	s0	s0	s1	s1	s1	受理
スタック	z0	A	B A	A B A	B A	A

上の例でわかるように状態遷移関数から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で模倣できます。