Mercurial > hg > Members > kono > Proof > automaton

comparison a07/lecture.ind @ 127:0e8a0e50ed26

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add some files
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 23 Nov 2019 12:59:45 +0900
parents
children 6f3636fbc481
comparison
equal deleted inserted replaced
126:a79e2c2e1642 127:0e8a0e50ed26
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