|
37
|
1 -title: 正規表現とオートマトン
|
|
|
2
|
|
|
3 --ε遷移とオートマトンの組合せ
|
|
|
4
|
|
|
5 文字の入力がなくても状態遷移が可能であるとすると、オートマトンの組合せが楽になる。
|
|
|
6
|
|
|
7 文字を消費しない遷移を ε遷移と言う。ε遷移可能な状態をまとめて一つの状態と見れば、ε遷移のないNFAに変換できる。
|
|
|
8
|
|
|
9 <a href="../agda/epautomaton.agda"> ε automatocn </a>
|
|
|
10
|
|
|
11 --正規表現とオートマトンの組合せ
|
|
|
12
|
|
|
13 <a href="../agda/regex.agda"> regex.agda </a>
|
|
|
14
|
|
|
15 --微分法
|
|
|
16
|
|
141
|
17 <center><img src="fig/derivation.svg"> </center>
|
|
|
18
|
|
37
|
19 --オートマトンから正規表現を生成する
|
|
|
20
|
|
|
21 状態遷移の条件を正規表現した一般化オートマトンを考える。
|
|
|
22
|
|
|
23 普通のオートマトンから始めて、状態を組み合わせて遷移条件を正規表現にしていく。
|
|
|
24
|
|
|
25 状態が一つになったら正規表現が得られる。
|
|
|
26
|
|
|
27 --実際の正規表現エンジン
|
|
|
28
|
|
|
29 grep のソースコード
|
|
|
30
|
|
|
31 --Boyer-Moore Search
|
|
|
32
|
|
|
33 固定文字列を検索するなら、正規表現よりも高速な手法がある。
|
|
|
34
|
|
|
35 例えば、engine を検索するとする。
|
|
|
36
|
|
|
37 6文字目がeでなければ、先頭の文字列からengineであることはない
|
|
|
38
|
|
|
39 なので、6文字見なくてもだめなことはわかる。しかし、7文字目からengineを探すと、
|
|
|
40
|
|
|
41 xxxxxn
|
|
|
42 the engine
|
|
|
43
|
|
|
44 を見落とす可能性がある。つまり、
|
|
|
45
|
|
|
46 6文字目が検索文字列に含まれる文字列だと途中からマッチする可能性がある
|
|
|
47
|
|
|
48 何文字目からマッチする可能性があるかは、あらかじめ調べることができる。
|
|
|
49
|
|
|
50 e 6文字目
|
|
|
51 n 2文字目
|
|
|
52 g 3文字目
|
|
|
53 i 4文字目
|
|
|
54 ? 7文字目
|
|
|
55
|
|
|
56 これを繰り返せば良い。
|
|
|
57
|
|
|
58 .*engine
|
|
|
59
|
|
|
60 をDFAに変換して探す場合とどれくらい速度が違うか調べてみよう。
|
|
|
61
|
|
|
62 --複数文字列に対する Boyer-Moore Search
|
|
|
63
|
|
46
|
64 ---問題6.1 正規表現の決定性オートマトンへの変換
|
|
37
|
65
|
|
46
|
66 <a href="../exercise/005.html"> 例題 </a> <!--- Exercise 6.1 --->
|
|
37
|
67
|
