|
37
|
1 -title: 正規表現とオートマトン
|
|
|
2
|
|
326
|
3 正規表現は、Automaton と同じ言語であることが期待される。つまり、
|
|
|
4
|
|
|
5 正規表現から、それと同じ language を受け付ける Automaton
|
|
|
6
|
|
|
7 を作ればよい。
|
|
|
8
|
|
|
9 --ε遷移と非決定性オートマトンの合成による方法
|
|
|
10
|
|
|
11 教科書にはこの方法が記述されている。
|
|
37
|
12
|
|
|
13 文字の入力がなくても状態遷移が可能であるとすると、オートマトンの組合せが楽になる。
|
|
|
14
|
|
|
15 文字を消費しない遷移を ε遷移と言う。ε遷移可能な状態をまとめて一つの状態と見れば、ε遷移のないNFAに変換できる。
|
|
|
16
|
|
326
|
17 そして、それを subset construction で DFA にすれば良い。
|
|
37
|
18
|
|
326
|
19 実際に、M-Concat などで合成を実行することができる。
|
|
37
|
20
|
|
326
|
21 しかし、もう少し直接的な方法も存在する。
|
|
37
|
22
|
|
|
23 --微分法
|
|
|
24
|
|
326
|
25 ある正規表現を考えた時に、それを
|
|
|
26
|
|
|
27 空列を受け付けるかどうか
|
|
|
28 個々の文字列を一文字受け付けたらどうなるか
|
|
|
29
|
|
|
30 と考える。
|
|
|
31
|
|
141
|
32 <center><img src="fig/derivation.svg"> </center>
|
|
|
33
|
|
326
|
34 まず空列を受け付けるかどうか判定する。
|
|
|
35
|
|
|
36 empty? : Regex Σ → Bool
|
|
|
37 empty? ε = true
|
|
|
38 empty? φ = false
|
|
|
39 empty? (x *) = true
|
|
|
40 empty? (x & y) = empty? x /\ empty? y
|
|
|
41 empty? (x || y) = empty? x \/ empty? y
|
|
|
42 empty? < x > = false
|
|
|
43
|
|
|
44 正規表現の変形を実行する
|
|
|
45
|
|
|
46 derivative : Regex Σ → Σ → Regex Σ
|
|
|
47 derivative ε s = φ
|
|
|
48 derivative φ s = φ
|
|
|
49 derivative (x *) s with derivative x s
|
|
|
50 ... | ε = x *
|
|
|
51 ... | φ = φ
|
|
|
52 ... | t = t & (x *)
|
|
|
53 derivative (x & y) s with empty? x
|
|
|
54 ... | true with derivative x s | derivative y s
|
|
|
55 ... | ε | φ = φ
|
|
|
56 ... | ε | t = y || t
|
|
|
57 ... | φ | t = t
|
|
|
58 ... | x1 | φ = x1 & y
|
|
|
59 ... | x1 | y1 = (x1 & y) || y1
|
|
|
60 derivative (x & y) s | false with derivative x s
|
|
|
61 ... | ε = y
|
|
|
62 ... | φ = φ
|
|
|
63 ... | t = t & y
|
|
|
64 derivative (x || y) s with derivative x s | derivative y s
|
|
|
65 ... | φ | y1 = y1
|
|
|
66 ... | x1 | φ = x1
|
|
|
67 ... | x1 | y1 = x1 || y1
|
|
|
68 derivative < x > s with eq? x s
|
|
|
69 ... | yes _ = ε
|
|
|
70 ... | no _ = φ
|
|
|
71
|
|
|
72 ここで、
|
|
|
73
|
|
|
74 eq? : (x y : Σ) → Dec (x ≡ y)
|
|
|
75
|
|
|
76 があることを使っている。
|
|
|
77
|
|
|
78 これの繰り返しで選れる正規表現の集合を data を使って表現できる。
|
|
|
79
|
|
|
80 data regex-states (x : Regex Σ ) : Regex Σ → Set where
|
|
|
81 unit : regex-states x x
|
|
|
82 derive : { y : Regex Σ } → regex-states x y → (s : Σ) → regex-states x ( derivative y s )
|
|
|
83
|
|
|
84 record Derivative (x : Regex Σ ) : Set where
|
|
|
85 field
|
|
|
86 state : Regex Σ
|
|
|
87 is-derived : regex-states x state
|
|
|
88
|
|
|
89 これを状態にして Automaton を構成できる。
|
|
|
90
|
|
|
91 regex→automaton : (r : Regex Σ) → Automaton (Derivative r) Σ
|
|
|
92 regex→automaton r = record { δ = λ d s → record { state = derivative (state d) s
|
|
|
93 ; is-derived = derive-step d s} ; aend = λ d → empty? (state d) } where
|
|
|
94 derive-step : (d0 : Derivative r) → (s : Σ) → regex-states r (derivative (state d0) s)
|
|
|
95 derive-step d0 s = derive (is-derived d0) s
|
|
|
96
|
|
|
97 実際に match を実行するには以下のようにする。
|
|
|
98
|
|
|
99 regex-match : (r : Regex Σ) → (List Σ) → Bool
|
|
|
100 regex-match ex is = accept ( regex→automaton ex ) record { state = ex ; is-derived = unit } is
|
|
|
101
|
|
|
102 ここではいくつかの問題が残っている。
|
|
|
103
|
|
|
104 生成される状態は有限か? (つまり微分法は停止するのか)
|
|
|
105
|
|
|
106 停止するかどうかに関係なく、regex-match は具体的な有限文字列に対して実行可能である。
|
|
|
107
|
|
|
108 ただし、Agda では具体的ではない文字列も用意できる。
|
|
|
109
|
|
|
110 微分法で定義した Automaton は、正規表現でしていされた言語に一致するのか?
|
|
|
111
|
|
|
112 これも証明する必要がある。
|
|
|
113
|
|
37
|
114 --オートマトンから正規表現を生成する
|
|
|
115
|
|
|
116 状態遷移の条件を正規表現した一般化オートマトンを考える。
|
|
|
117
|
|
|
118 普通のオートマトンから始めて、状態を組み合わせて遷移条件を正規表現にしていく。
|
|
|
119
|
|
|
120 状態が一つになったら正規表現が得られる。
|
|
|
121
|
|
|
122 --実際の正規表現エンジン
|
|
|
123
|
|
|
124 grep のソースコード
|
|
|
125
|
|
|
126 --Boyer-Moore Search
|
|
|
127
|
|
|
128 固定文字列を検索するなら、正規表現よりも高速な手法がある。
|
|
|
129
|
|
|
130 例えば、engine を検索するとする。
|
|
|
131
|
|
|
132 6文字目がeでなければ、先頭の文字列からengineであることはない
|
|
|
133
|
|
|
134 なので、6文字見なくてもだめなことはわかる。しかし、7文字目からengineを探すと、
|
|
|
135
|
|
|
136 xxxxxn
|
|
|
137 the engine
|
|
|
138
|
|
|
139 を見落とす可能性がある。つまり、
|
|
|
140
|
|
|
141 6文字目が検索文字列に含まれる文字列だと途中からマッチする可能性がある
|
|
|
142
|
|
|
143 何文字目からマッチする可能性があるかは、あらかじめ調べることができる。
|
|
|
144
|
|
|
145 e 6文字目
|
|
|
146 n 2文字目
|
|
|
147 g 3文字目
|
|
|
148 i 4文字目
|
|
|
149 ? 7文字目
|
|
|
150
|
|
|
151 これを繰り返せば良い。
|
|
|
152
|
|
|
153 .*engine
|
|
|
154
|
|
|
155 をDFAに変換して探す場合とどれくらい速度が違うか調べてみよう。
|
|
|
156
|
|
|
157 --複数文字列に対する Boyer-Moore Search
|
|
|
158
|
|
46
|
159 ---問題6.1 正規表現の決定性オートマトンへの変換
|
|
37
|
160
|
|
46
|
161 <a href="../exercise/005.html"> 例題 </a> <!--- Exercise 6.1 --->
|
|
37
|
162
|
