|
127
|
1 -title: 非決定性オートマトンから決定性オートマトンへの変換
|
|
|
2
|
|
|
3 非決定性オートマトンは、ある状態から複数の可能な状態へ遷移する。そのうちのどれかが受理状態へ遷移すれば accept となる。
|
|
|
4
|
|
|
5 状態は有限なので、複数の可能な状態は、状態の部分集合となる。状態Qの部分集合は、
|
|
|
6
|
|
|
7 Q → Bool
|
|
|
8
|
|
332
|
9 と表すことができる。つまり、その部分集合に含まれるかどうかを表す関数が部分集合そのものになる。
|
|
|
10
|
|
|
11 これを、Bool
|
|
127
|
12 <sup>Q</sup> と書くことがある。Bool は二つの要素がある。状態数4からBoolへの関数は、2
|
|
|
13 <sup>4</sup>個ある。集合のべき乗をこのようにして定義することができる。
|
|
|
14
|
|
|
15 非決定性オートマトンを状態Qの部分集合を状態とする決定性オートマトンと考えることができる。
|
|
|
16 NAutomaton Q Σ は状態の集合Qと入力文字の集合Σからなる非決定性オートマトンだった。これから、
|
|
|
17
|
|
|
18 Automaton (Q → Bool) Σ
|
|
|
19
|
|
|
20 を作れれば、非決定性オートマトンから決定性オートマトンへの変換ができることになる。
|
|
|
21
|
|
|
22 状態Q入力文字Σの決定性オートマトンの状態遷移関数は Q → Σ → Q だったから、
|
|
|
23 この状態Qの部分集合を状態とするAutomatonの状態遷移関数は、
|
|
|
24
|
|
|
25 (Q → Bool) → Σ → (Q → Bool)
|
|
|
26
|
|
|
27 となる。右のかっこは省略可能である。
|
|
|
28
|
|
|
29 (Q → Bool) → Σ → Q → Bool
|
|
|
30
|
|
|
31 つまり、状態遷移関数は三つの入力を持つ。f i q としよう。決定性オートマトンの状態遷移関数は、
|
|
|
32
|
|
|
33 Nδ : Q → Σ → Q → Bool
|
|
|
34
|
|
|
35 だった。f : Q → Bool が入力の状態で、i : Σ が決まっている。出力状態は Q → Bool なので q を入力に持つ。
|
|
|
36
|
|
|
37 λ q → f q ∧ Nδ q i
|
|
|
38
|
|
332
|
39
|
|
|
40 --状態の部分集合を使う
|
|
|
41
|
|
|
42 true になるものは複数あるので、やはり部分集合で表される。つまり、
|
|
|
43
|
|
|
44 exists : ( P : Q → Bool ) → Q → Bool
|
|
|
45
|
|
|
46 このような関数を実装する必要がある。
|
|
|
47
|
|
|
48 --非決定性オートマトンと決定性オートマトン
|
|
|
49
|
|
|
50 record Automaton ( Q : Set ) ( Σ : Set )
|
|
|
51 : Set where
|
|
|
52 field
|
|
|
53 δ : Q → Σ → Q
|
|
|
54 aend : Q → Bool
|
|
|
55
|
|
|
56 の Q に Q → Bool を入れてみる。
|
|
|
57
|
|
|
58 δ : (Q → Bool ) → Σ → Q → Bool
|
|
|
59 aend : (Q → Bool ) → Bool
|
|
|
60
|
|
|
61 これを、
|
|
|
62
|
|
|
63 record NAutomaton ( Q : Set ) ( Σ : Set )
|
|
|
64 : Set where
|
|
|
65 field
|
|
|
66 Nδ : Q → Σ → Q → Bool
|
|
|
67 Nend : Q → Bool
|
|
|
68
|
|
|
69 これの Nδ と Nend から作れれば、NFA から DFA を作れることになる。
|
|
|
70
|
|
|
71 NFAの受理を考えると、状態の集合を持ち歩いて受理を判断している。つまり、状態の集合を状態とする Automaton を考えることになる。
|
|
|
72
|
|
|
73 遷移条件は、状態の集合を受けとって、条件を満たす状態の集合を返せば良い。条件は
|
|
|
74
|
|
|
75 Nδ : Q → Σ → Q → Bool
|
|
|
76
|
|
|
77 だった。つまり、入力の状態集合を選別する関数 f と、 Nδ との /\ を取ってやればよい。q は何かの状態、iは入力、nq は次の状態である。
|
|
|
78
|
|
|
79 f q /\ Nδ NFA q i nq
|
|
|
80
|
|
|
81 これが true になるものを exists を使って探し出す。
|
|
|
82
|
|
|
83 δconv : { Q : Set } { Σ : Set } → (exists : ( Q → Bool ) → Bool )
|
|
|
84 → ( Q → Σ → Q → Bool ) → (Q → Bool) → Σ → (Q → Bool)
|
|
|
85 δconv {Q} { Σ} exists nδ f i q = exists ( λ r → f r /\ nδ r i q )
|
|
|
86
|
|
|
87 ここで、( nδ : Q → Σ → Q → Bool ) は NFAの状態遷移関数を受けとる部分である。
|
|
|
88
|
|
|
89 終了条件は
|
|
|
90
|
|
|
91 f q /\ Nend NFA q )
|
|
|
92
|
|
|
93 で良い。 これが true になるものを exists を使って探し出す。
|
|
|
94
|
|
|
95 Q が FiniteSet Q {n} であれば
|
|
|
96
|
|
|
97 subset-construction : { Q : Set } { Σ : Set } →
|
|
|
98 ( ( Q → Bool ) → Bool ) →
|
|
|
99 (NAutomaton Q Σ ) → (Automaton (Q → Bool) Σ )
|
|
|
100 subset-construction {Q} { Σ} exists NFA = record {
|
|
|
101 δ = λ q x → δconv exists ( Nδ NFA ) q x
|
|
|
102 ; aend = λ f → exists ( λ q → f q /\ Nend NFA q )
|
|
|
103 }
|
|
|
104
|
|
|
105 という形で書くことができる。状態の部分集合を作っていくので、subset construction と呼ばれる。
|
|
|
106
|
|
|
107 λ f i → δconv exists ( Nδ NFA ) f i
|
|
|
108 は
|
|
|
109 λ f i q → δconv exists ( Nδ NFA ) f i q
|
|
|
110
|
|
|
111 であることに注意しよう。これは、Curry 化の省略になっている。省略があるので、δ : (Q → Bool ) → Σ → Q → Bool という形に見える。
|
|
|
112
|
|
|
113 これで実際に、NFAから DFA を作成することができた。
|
|
|
114 ここで、状態の exists (有限性または部分集合の決定性)を使っていることに注意しよう。
|
|
|
115
|
|
|
116 <a href=" ../agda/sbconst2.agda"> subset construction </a>
|
|
|
117
|
|
|
118
|
|
127
|
119 ---問題7.1 以下の非決定性オートマトンを決定性オートマトンへ変換せよ
|
|
|
120
|
|
|
121
|
|
|
122 <a href="../exercise/003.html"> 例題 </a> <!--- Exercise 7.1 --->
|
|
|
123
|
|
332
|
124 --subset constructionの状態数
|
|
|
125
|
|
|
126 実際にこれを計算すると、状態数 n のNFAから、最大、2^n の状態を持つDFAが生成される。しかし、この論理式からそれを
|
|
|
127 自明に理解することは難しい。しかし、f は Q → Bool なので、例えば、3状態でも、
|
|
|
128
|
|
|
129 q1 q2 q3
|
|
|
130 false false false
|
|
|
131 false false true
|
|
|
132 false true false
|
|
|
133 false true true
|
|
|
134 true false false
|
|
|
135 true false true
|
|
|
136 true true false
|
|
|
137 true true true
|
|
|
138
|
|
|
139 という8個の状態を持つ。exists は、このすべての場合を尽くすように働いている。
|
|
|
140
|
|
|
141 アルゴリズムとしてこのまま実装すると、 exists が必要な分だけ計算するようになっている。これは結構遅い。
|
|
|
142 前もって、可能な状態を Automaton として探し出そうとすると、 指数関数的な爆発になってしまう。
|
|
|
143
|
|
|
144 実際に、指数関数的な状態を作る NFA が存在するので、これを避けることはできない。
|
|
|
145
|
|
|
146 --NFAの実行
|
|
|
147
|
|
|
148 subset construction した automaton はすべての状態を生成する前でも実行することができる。
|
|
|
149 ただし、毎回、nest した exists を実行することになる。
|
|
|
150
|
|
|
151
|
