第 8 回 非決定性

本日の内容

• 8-1. 非決定性の計算
• 8-2. オートマトン理論
• 8-3. 宿題
• 8-4. 次週の予告

8-1. 非決定性の計算

非決定性の計算を取り上げます。 非決定性の計算を行うコンピュータは存在しません。 しかし、非決定性の計算モデルを考えると、実存する多くの問題の複雑さを明 らかにすることができ、有用です。

次の状態が一意に定まらない計算を 非決定性 と言います。 ここでは、最終的な答として、 yes か no を出力する計算を考えます。 非決定性の計算を通常のプログラミング言語にさせるためには、通常 guess 命令と accept 命令と reject 命令を使用します。 guess 命令は変数を伴い、これは最終的に accept 命 令にたどり着けるような、都合の良い値を変数に代入します(時間計算量は代 入する長さに比例するものとします)。 一つでも accept 命令にたどり着けるように guess できたら、答 えは yes になります。 但し、どのように guess しても accept 命令にたど り着けない場合は、答が no になります。

例8-1

入力 n が合成数かどうかを判定するには……

1. guess x( $2\le x\le \sqrt{n}$ );
2. if( n が x で割り切れる) { accept; } else{ reject; }

例8-2

巡回セールスマン問題(Traveling Salesman Problem)は次の通りです。

入力

• 都市間の交通費(あらゆる組合せを与える) c(x,y)
• 予算 B

質問

予算内で全ての都市を回ることができるか?

これを解く非決定性のプログラムは次の通りです。

1. guess v₁, ... , v_n (都市を訪れる順番を guess する)
2. $\mathrm{sum}=\sum c\left(v_i,v_{i+1}\right)$
3. if(sum≦ B) accept else reject

8-2. オートマトン理論

ここでは、オートマトン理論の結果を復習し、非決定性の計算を考える有用性 について考えます。

オートマトン

Turing 機械をすでに定義している立場では、オートマトンとは、 書き込み不可で一方向にしかヘッドが動かないテープが入力用に用意されてい るだけで、他にテープを使用できない Turing 機械であると定義できます。 入力によって、状態を変えることはできますが、テープに値を保存することは 出来ません。 従って、次のような構文でプログラムを書くことになります。

数学的に定義すると Turing 機械と同様に (Q, Σ, δ, q₀, F) と 5 つの組みになりますが、 δ関数は次のようになります。

オートマトン

δ:Q×Σ→Q

Turing 機械(参考)

δ:Q×Σ→Q×Σ×{L, S, R}

このように Turing 機械を制限すると、どれくらい能力が落ちるのでしょうか? これに関しては、オートマトンで受理できる言語と、正規文法で定義できる言 語が一致すると言う結果が分かっています。

正規文法

正規文法とは次のような規則で定める文法のことです。

1. 文字そのもの
2. 複数の文字の連続
3. x, y が文法の表現だとすると、 (x|y) は x または y を表し、 これも正規文法の表現になる。
4. x が文法の表現だとすると、(x*) は x の 0 個以上の繰り返しを表し、正則文法になる。

例えば、自然数を考えた場合、一番大きい位の桁は 1 から 9 で、二番目以降 の桁は 0 から 9 までとなるので、次のようになります。

正規文法は、整数、浮動小数点、名前など、プログラミング言語で使用するよ うな文字の固まりを良く表現できます。 従って、これらをプログラミング言語で使用できるよう、 C 言語では lexx という「オートマトンの定義」から「C 言語のプログラム」へ変換するコンパ イラコンパイラがあります。 また、Awk や Perl 言語のように標準的に組み込んでいるものもあります。

オートマトンと正規文法

正規文法とオートマトンの関係を調べましょう。

オートマトンは正規文法で表せる

オートマトンが正規文法で表せることを示します。 証明は参考文献岩田茂樹/笠井琢美「有限オートマトン入門」森北出版 (1986) を参考にしました。

オートマトンが与えられた時、それから正規文法を一つ作る作り方を与えます。 まず、受理状態へ遷移できない状態をすべて取り除きます。 また、新たに一つ別の受理状態を加え、現存のすべての受理状態に対して、そ の状態は受理ではなくし、そこからλ(空の文字列)の入力で新しい受理状態に 遷移するように修正します。 この修正により、オートマトンの入力としてλを許してしまいますが、受理状 態はただ一つのオートマトンにします。 そして、次のルールを適応しながら、オートマトンを変形していきます。 もともとのオートマトンは文字一つで状態遷移を行いましたが、このルールを 適応することで、入力を正規文法に拡張して、状態を減らしていきます。 最終的に初期状態から唯一の受理状態まで、一つの正規文法により遷移するよ うに変形できたら、それが求めるオートマトンと等価な正規文法になります。

ルール1(平行辺の削除)

一つの状態から別の一つの状態へ、複数の辺があり、それぞれ s₁, ...,s_l を入力としてと る場合、それらの辺を取り除き、新たに (s₁|...|s_l) を一つの入力とした辺を付け加える。

ルール2(ループの削除)

ある状態から、入力 s により自分自身へ戻り、別の入力 r₁, ...,r_l によりそれぞれ 別の状態へ分岐する時、自分自身へ戻る辺を取り除き、 それぞれの別の分岐に対しては (s*r₁), ...,(s*r_l) を入力とするように修正する。

ルール3(状態の削除)

状態 p_i からは入力 s_i で 状態 q に遷移するとします(0≦ i≦k)。 一方、状態 q から入力 r_j で状態 p'_j に遷移するとします(0≦ j≦ l)。 その時、状態 q を取り除き、 状態 p_i から p'_j へは入力 s_ir_j で遷移するように辺を付け替えます。

このようにすると、平行辺とループを取り除けば必ず一つ状態を削除できます ので、最終的に目的の初期状態から受理状態への一本の辺だけになるまで変形 を繰り返すことができます。

正規文法は非決定性オートマトンで表せる

任意の正規文法が非決定性オートマトンで表せることを示します。 非決定性のオートマトンとして、「入力が来なくても複数の状態に非決定的に 遷移できる」ように、入力文字λを導入します。 これが割り当てられた辺には、入力が来なくても非決定的に遷移できるとしま す。 さて、正規文法が与えられた時、次のようにして非決定性オートマトンで表し ます。r を受理する非決定性オートマトンを M_r、s を受理する非決定性オートマトンを M_s とします。

rs(連結)

単純に M_rの受理状態から M_sの初期状態へ入力λの辺で結ぶ。

r|s

新たな初期状態 q₀と受理状態 q_f を用意し、 q₀から入力λ で M_rと M_s の初期状態へ結び、 M_rと M_s の受理状態から 入力λ で q_fへ結ぶ。

r*

あらたな受理状態 q_f を用意し、 q_f から入力λでM_rの初期状 態へ結び、 M_rの受理状態 から入力λで q_f へ結ぶ。

非決定性オートマトンは決定性オートマトンに変形できる

ラベル(状態)の巾集合を考えます。そして、その要素(つまりラベルの全ての 組合せ)に対して、状態の遷移を考えます。 状態 a は 0 の入力で状態 b へ、 状態 c は 0 の入力で状態 d へ遷移する時、 状態 { a,c} は 0 の入力で状態 {b,d }へ推移すると考えます。 そして、これらのラベルの組合せを新しいラベルと思って、オートマトンを構 成すると、次の状態は一意に定まります。 そして、受理するラベルを含むラベルは受理を意味するとします。 このようにすると、もしもとのオートマトンでひとつでも受理に向かう計算が 存在する時、新しく作ったオートマトンでは受理状態に入ることになります。

8-3. 宿題

1

与えられた地図を 3 色で塗れるかどうかを判定するような非決定性のプログ ラムを書きなさい。

2

ナップザック問題を解く非決定性のプログラムを書きなさい。 但しナップザック問題とは 荷物を選んで、ナップザックに丁度一杯になるように詰められるかどうかを判 断する問題です。

入力

荷物の体積

v₁, v₂, ..., v_n

ナップザックの容量

C

出力

• 荷物をいくつか選ぶと丁度体積が C になるなら「yes」
• 体積が C になるような荷物の選び方がないなら「no」

8-4. 次週の予告

次回は NP 完全問題についてお話します。