Aritalab:Lecture/Automata/PushDown

形式言語理論のトップページヘ

まとめ

ここでは言語 L = { xx^R | {0,1}{0,1}* } の受理を例として、プッシュダウンオートマトンと文脈自由言語の等価性を示します。プッシュダウンオートマトンは補助記憶としてスタックを一つ備えています。スタックの大きさは有限でないため（無限大になりうる）、言語 { 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
動作	Aを積む	Bを積む	Aを積む	状態 s1へ ポップ	ポップ	ポップ	受理

上の例でわかるように状態遷移関数からPDAの動作を推測するのは大変です。ただ、スタックを用いて xx^R が認識できることはわかります。

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

PDAはわざと非決定性に定義してあります。ここではそのメリットをフルに活かします。

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

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

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

スタックを利用できる機能は大変強力です。実は、任意の有限状態 PDA を 1 状態のPDAで模倣できます。基本は、現在状態の情報をスタック記号に加えるだけです。

入力	0	1	0	0	1	0
あるべき状態	s0	s0	s0	s1	s1	s1
スタック (上積み)	z0	s0, A	s0, B s0, A	s0, A s0, B s0, A	s0, A s0, A s0, B s0, A	失敗 !

しかしそれでは、スタックの上にある状態記号と現在の状態が、一致しないという不都合が生じます（上図の太字）。この例ではスタックから一つ取り去っても s₁ への移行が記録されず、（状態がずっとs₀ なので）スタックに積み続けてしまいます。

ここで非決定性を利用します。スタックの上に記号を積む際に、それまで上にあった記号を後で取り出すときの状態を予測して状態記号を書き換えてから新しい記号を積みます。この場合は s₀ を s₁ に書換えます。（下図の太字にした s₁ ）

入力	0	1	0	0	1	0
あるべき状態	s0	s0	s0	s1	s1	s1
スタック (上積み)	z0	s0, A	s0, B s1, A	s0, A s1, B s1, A	s1, B s1, A	....

上記の例で入力文字を太字にしたステップ、つまり σ( s₀, 0, A ) = ( s₁, ε ) を実行する時を考えてみましょう。現在状態 s₀ から s₁ に移動してスタック上の A をポップすると、ちょうど "s₁, B" という情報がスタック上に出てきます。これはあらかじめ（非決定性を用いて）スタックの記号を書換えておいたからです。しかし、予測に失敗する場合もあります。例えばスタック記号が "s₀, B" の可能性もあります。このとき、 σ( s₀, 0, A ) = ( s₁, ε ) という状態遷移を実行してはならないのですが、スタック最上にある部分だけからは、ポップして下から s₀ が出てくるのか s₁ が出てくるのかわかりません。

そこで更に工夫を施します。スタックに記号を積むときには、その下になるスタック記号の状態も併記するようにします。下のスタック図で↓s₁とあるのは、直下のスタック要素の状態が s₁ であることを示しています。こうすると、状態遷移関数を適用する際に、関数に書かれている適用後の状態と、スタックの下から出てくる状態が一致するかどうか確認できます。不一致の場合は非受理とします。

入力	0	1	0	0	1	0
あるべき状態	s0	s0	s0	s1	s1	s1
スタック (上積み)	s0, z0, ↓ε	s0, A, ↓ε	s0, B, ↓s1 s1, A, ↓ε	s0, A, ↓s1 s1, B, ↓s1 s1, A, ↓ε	s1, B, ↓s1 s1, A, ↓ε	s1, A, ↓ε	受理

結果として、状態遷移関数と整合性をもたせた形で任意のPDAを 1 状態のPDAでシミュレートできることがわかりました。実際に1状態PDAに変換するときは、"s, A, ↓s'" の三つ組をエンコードしたスタック記号を作成し、状態遷移関数もそれに合わせて書き換えることになります。また非決定性で状態を予測してスタック上に積みこむため、極めて多くの遷移関数を用意します。

グライバッハ標準形とPDAの等価性

グライバッハ標準形とは、文脈自由言語の文法規則です。常に左端に 1 個の終端記号があり、その右に任意の個数の変数が並ぶ形式を指します。（忘れた人は文脈自由言語のページをみてください。）グライバッハ標準形では、長さ n の文字列を生成するのにちょうど n 回のルールを適用します。このルール適用が、PDA の入力文字列読み込み動作に対応します。

任意の PDA を与えられたら、まず 1状態PDAに変換します。1状態PDAの各遷移関数を以下のように文法規則に変換します。1状態なので、s を組み込む必要がない点に注意してください。

σ( s, 0, A ) = ( s, Z )  ⇒  A → 0Z

１状態PDAであればスタックの上にある記号と入力文字列だけで、次にスタックの上に置く記号が定まるため、グライバッハ標準形と 1対1 に対応します。

逆に任意の文脈自由言語が与えられたら、それをグライバッハ標準形に直して状態遷移関数とみなすことで１状態PDAに等しいことがわかります。

次→　チューリング機械