13
正則言語を受理する機械として有限状態オートマトンがあるように、文脈自由言語を受理する機
2
械としてプッシュダウン・オートマトン（pushdown automaton）が考案されています。「プッシュ
3
ダウン」とは「最後に記憶された情報が最初に検索される」ことを意味します1。このようなデー
4
タ構造としてすぐに
スタック
（stack）が連想されますが、プッシュダウン・オー5
トマトンとはまさに スタックを持つオートマトン に他なりません。
6
なお、以下ではプッシュダウン・オートマトンを簡単にPDAと呼ぶこととします。
7
ǡǧǫǗƣງ߰
# A A A
q0 q1
(a,#→#A) (a,A→AA)
(b,A→ϵ)
(b,A→ϵ)
ۆभઆശ
ద݈֗་ƣߢƿ aaaabb...
q2 (ϵ,#→#) ہޟƣभઆ
q0
図 13.1: anbnを認識するプッシュダウン・オートマトン
(a) 記号aを読んだときには、スタックの状態に関わらず、記号Aをスタックに積みます。
1
(b) 記号bを読んだときに、スタックの頂上の記号がAならば、Aをスタックから降ろし
2
ます。そしてq1へ遷移します。
3
(c) 上の二つに当てはまらない場合には、オートマトンの動作は失敗と見なし、入力記号列
4
は受理されません。
5
4. 状態q1 において
6
(a) 記号bを読んだときに、スタックの頂上の記号がAならば、Aをスタックから降ろし
7
8 ます。
(b) スタックの頂上の記号が#ならば、入力記号を読まないで、状態q2 へ遷移します（こ
9
れはε遷移です）。
10
(c) 上の二つに当てはまらない場合には、オートマトンの動作は失敗と見なし、入力記号列
11
は受理されません。
12
5. 状態q2 において入力記号を全て読み終えたならば、オートマトンの動作は成功です。さも
13
なくば失敗です。
14
このオートマトンの動作のポイントは、読み込んだ入力記号aと同じ個数のA をスタックに積む
15
ことです。そして次に入力記号bを読むときにはAをスタックからひとつずつ降ろしていきます。
16
そして、aと同じ個数の bを読み終えたならば、スタックの頂上には# が見えているはずです。
17
つまり、スタックを用いて記号 aの個数を記憶するのです。このような記憶装置はDFA、NFA、
18
ε-NFAにはありませんでした。
19
ところで、ある状態 pにおいて、入力記号がa であり、かつスタックの頂上の記号がZ であ るときに、状態qへ遷移し、スタックからZ を下ろし、新たにスタックに記号Z1、Z2、...、Zk
（k≥0）をこの順に積むという動作を行うと仮定します。これをオートマトンの状態遷移図に表す ために、状態遷移図のpからqへの枝に以下のラベルを付けると約束します。
(a, Z→Z1Z2...Zk) 記号を読まないε遷移の場合には以下の通りとします。
(ε, Z→Z1Z2...Zk) スタックに何も積まない場合には以下の通りとします。
(a, Z→ε) 図13.1の状態遷移図には上のようなラベルを付けています。
1
図13.1に基づいて、実際に入力記号列aaaabbbbを読み込んでみましょう。
2
その準備として、オートマトンの実行の様子を的確に知るために、オートマトンの状態 q、ス
3
タックの内容γ、（まだ読み込まれていない）入力記号列の残りuを以下のように並べて表します。
4
状態 スタック 入力列の残り
q γ u
5
これを一般に
時点表示
（instantaneous description）2と呼びます。そうすると、6
例題のPDA で入力記号列aaaabbbbを読むときの初期の時点表示は以下の通りです。
7
状態 スタック 入力列の残り
q0 # aaaabbbb
8
ここでオートマトンが記号aを読み、上の規則3.(a)によって時点表示は以下のように変化します。
9
状態 スタック 入力列の残り
q0 #A aaabbbb
10
同じく、残りの三つのaを読むと、変化は以下の通りです。
11
状態 スタック 入力列の残り
q0 #AA aabbbb
q0 #AAA abbbb
q0 #AAAA bbbb
12
次にbを読むと、上の3.(b)の規則によって、状態はq1 に遷移し、スタック上の記号Aがひとつ
13
減ります。
14
2読んで字のごとく、オートマトンの各時点での状態を表した式のことです。
状態 スタック 入力列の残り
q0 #A aaabbbb
q0 #AA aabbbb
q0 #AAA abbbb
q0 #AAAA bbbb
q1 #AAA bbb
q1 #AA q1 #A q1 # q2 #
図13.2: 図13.1のプッシュダウン・オートマトンの動作例（まとめ）
状態 スタック 入力列の残り
q1 #AAA bbb
1
さらに4.(a)の規則を3回適用し、時点表示は以下のように変化します。
2
状態 スタック 入力列の残り q1 #AA
q1 #A q1 #
3
最後に4.(b)の規則を適用すると、
4
状態 スタック 入力列の残り q2 #
5
となり、状態q2 において入力列は全て読み終えました。よって記号列aaaabbbb は受理されまし
6
た。この一連の動作を図13.2にまとめました。
7
考察 入力記号列がε、aaabb、aabbbのときのオートマトンの動作をそれぞれ調べなさい。
8
考察 言語{anbn |n≥0} を受理する PDA を検討しなさい。ここに上の例とは異なり、n= 0
9
の場合が含まれることを注意する。
10
考察（難問） 以下の文脈自由文法に対応するPDAを検討しなさい。
1
1: E→E + F 2: E→F
3: F →id 4: F →(E )
2