アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

4.1

 決定性プッシュダウン・オートマトン

111

バランスのとれた括弧のDPDAの規則を、この形式にしたがって書き直すのは簡単です。

●

状態1で開き括弧を読むと、文字

$

をポップし、文字

b$

をプッシュし、状態2に移動する。

●

状態2で開き括弧を読むと、文字

b

をポップし、文字

bb

をプッシュし、状態2にとどまる。

●

状態2で閉じ括弧を読むと、文字

b

をポップし、文字をプッシュせずに、状態2にとどまる。

●

状態2で（何も文字を読まずに）、文字

$

をポップし、文字

$

をプッシュし、状態1に移動する。

これらの規則を図に示すと以下のようになります。DPDAの図はNFA の図とよく似ていますが、矢

印には、入力から読む文字とともに、規則によってポップおよびプッシュされる文字をラベル付けする

必要があります。入力から

a

を読み、スタックから

b

をポップし、スタックに

cd

をプッシュする規則を

表現するのに、

a;b/cd

という表記を使うことにしましょう。この機械は次のようになります。

図4-2

4.1.3

　決定性

次の問題は、PDAにおける決定性が何を意味しているのか、明確に定義することです。DFAの場

合には「矛盾がないこと」という制約がありました。競合する規則が複数あることで、機械の次の状態

があいまいになるような状態があってはいけません。同じ考え方をDPDAにも適用しましょう。たとえ

ば、機械が状態2にいて、次の入力文字が開き括弧で、スタックのトップに

b

があるとき、適用される

規則は1つだけになります。入力を読まない自由