|
127
|
1 -title: 非決定性オートマトンから決定性オートマトンへの変換
|
|
|
2
|
|
|
3 非決定性オートマトンは、ある状態から複数の可能な状態へ遷移する。そのうちのどれかが受理状態へ遷移すれば accept となる。
|
|
|
4
|
|
|
5 状態は有限なので、複数の可能な状態は、状態の部分集合となる。状態Qの部分集合は、
|
|
|
6
|
|
|
7 Q → Bool
|
|
|
8
|
|
|
9 と表すことができる。つまり、その部分集合に含まれるかどうかを表す関数が部分集合そのものになる。これを、Bool
|
|
|
10 <sup>Q</sup> と書くことがある。Bool は二つの要素がある。状態数4からBoolへの関数は、2
|
|
|
11 <sup>4</sup>個ある。集合のべき乗をこのようにして定義することができる。
|
|
|
12
|
|
|
13 非決定性オートマトンを状態Qの部分集合を状態とする決定性オートマトンと考えることができる。
|
|
|
14 NAutomaton Q Σ は状態の集合Qと入力文字の集合Σからなる非決定性オートマトンだった。これから、
|
|
|
15
|
|
|
16 Automaton (Q → Bool) Σ
|
|
|
17
|
|
|
18 を作れれば、非決定性オートマトンから決定性オートマトンへの変換ができることになる。
|
|
|
19
|
|
|
20 状態Q入力文字Σの決定性オートマトンの状態遷移関数は Q → Σ → Q だったから、
|
|
|
21 この状態Qの部分集合を状態とするAutomatonの状態遷移関数は、
|
|
|
22
|
|
|
23 (Q → Bool) → Σ → (Q → Bool)
|
|
|
24
|
|
|
25 となる。右のかっこは省略可能である。
|
|
|
26
|
|
|
27 (Q → Bool) → Σ → Q → Bool
|
|
|
28
|
|
|
29 つまり、状態遷移関数は三つの入力を持つ。f i q としよう。決定性オートマトンの状態遷移関数は、
|
|
|
30
|
|
|
31 Nδ : Q → Σ → Q → Bool
|
|
|
32
|
|
|
33 だった。f : Q → Bool が入力の状態で、i : Σ が決まっている。出力状態は Q → Bool なので q を入力に持つ。
|
|
|
34
|
|
|
35 λ q → f q ∧ Nδ q i
|
|
|
36
|
|
|
37 ---問題7.1 以下の非決定性オートマトンを決定性オートマトンへ変換せよ
|
|
|
38
|
|
|
39
|
|
|
40 <a href="../exercise/003.html"> 例題 </a> <!--- Exercise 7.1 --->
|
|
|
41
|
