第２章 「有限オートマトン」

第２章の内容 2.1 定義 2.2 正規集合の演算 2.3 Nerodeの定理 2.4 非決定性の有限オートマトン 2.5 正規表現と正規集合 2.6 順序機械と状態最小化

2.1 定義 q a1 a2 ai 有限オートマトン M = (K, Σ, δ, q0, F) 2.1 定義 有限オートマトン　M = (K, Σ, δ, q0, F) K = {q0, q1, …, qn} : 状態の集合 Σ= {a, b, …, c} : 文字の集合（アルファベット） q0 : 初期状態 δ : 遷移関数 K×Σ→ K F :　受理状態の集合（K の部分集合） q ヘッド a1 a2 ai テープ

定義つづき 遷移関数を次のように拡張する。 (1) δ(q, e) = q (q ∈ K) 　定義つづき 遷移関数を次のように拡張する。 (1) δ(q, e) = q (q ∈ K) (2) δ(q, ax) =δ(δ(q, a), x) (q∈K, a∈Σ, x∈Σ*) 文字列wに対してδ(q0, w)は，その文字列を読んだときの オートマトンの状態を表す。 δ(q0, w) = p ∈ F であるとき，M はwを受理するという。 Mが受理する文字列全体：L(M) ={w | δ(q0, w) ∈ F} オートマトンによって受理される集合を正規言語という。

オートマトンの例（p8） 状態遷移 状態遷移図（図２） a δ(q0, aba) = δ(δ(q0, a), ba) = δ(q1, ba) = δ(d(q1, b), a) = δ(q0, a) = q1 ∈ F q0 q1 b b a q2 a,b L(M) = {a(ba)n | n≧0}

2.2 正規集合の演算 アルファベットΣ上の正規集合の族 R (Σ) = {L | Lは正規言語} は集合演算∪, ∩, ￣のもとでブール代数をなす R (Σ) L1 L2

補題 2.1 補題2.1 正規集合 L の補集合 L =Σ*－L は正規集合 証明 　補題 2.1 補題2.1 正規集合 L の補集合 L =Σ*－L は正規集合 証明 Lを受理するオートマトンをM=(K, Σ, δ, q0,F)とするとき，M=(K, Σ, δ, q0, K-F) とすると　L(M) = L(M) となる.

補題 2.2 補題2.2 L1, L2 ⊆ Σ * を正規集合とする。 (1) L1∪ L2は正規集合である。 　補題 2.2 補題2.2 L1, L2 ⊆ Σ * を正規集合とする。 (1) L1∪ L2は正規集合である。 (2) L1∩ L2は正規集合である。 証明 (1)について証明する。 L1 = L(M1)、M1 = (K1, Σ, δ1, q01, F1) とし、L2に対してもM2を定義する。M1, M2から次の遷移関数 d と受理状態Fをつくる。 δ = ((q1, q2), a) = (δ1(q1, a), δ2(q2, a)) (q1∈K1, q2∈K2, a∈Σ) F = F1×K2∪K1×F2

　証明つづき 任意の q1∈K1, q2∈K2 に対して， δ = ((q1, q2), e) = (δ1(q1, e), δ2(q2, e)) = (q1, q2) 数学的帰納法のベースステップ δ = ((q1, q2), x) = (δ1(q1, x), δ2(q2, x)) (仮定 |x|≦k) δ((q1, q2), ax) = δ(δ((q1, q2), a), x) 定義より = δ((δ1(q1, a), δ2(q2, a)), x) 帰納法の仮定 = (δ1(δ1(q1, a), x), δ2(δ2(q2, a), x)) 帰納法の仮定 = (δ1(q1, ax), δ2(q2, ax)) 定義より

証明つづき x ∈ L(M) ⇔ δ((q01, q02), x) ∈ F 　証明つづき x ∈ L(M) ⇔ δ((q01, q02), x) ∈ F ⇔ (δ1(q01, x), δ2(q02, x)) ∈ F1×K2∪K1×F2 ⇔ δ1(q01, x) ∈ F1　または　 δ2(q02, x) ∈ F2 ⇔ x ∈ L(M1)∪L(M2) (2)の証明は省略 (1)のときと、終状態の条件が違うだけ。

2.3 Nerode の定理 Σ*上の関係 R は、 xRy ⇒ 任意の z∈Σ* に対して xzRyz を満たすとき右不変であるという。 関係 R は、R による同値類の数が有限で あるとき、有限指数であるという。

定理2.4 （Nerodeの定理） 定理2.4 次の３つは同等である. (1) 集合 L⊆Σ* は正規である。 　(2) L はある有限指数で右不変な同値関係 R による同値類の和として表される。 　(3) 関係 ≡ は有限指数である。ただし≡は x≡y ⇔ 任意の z∈Σ* に対して xz, yz∈L であるか xz, yz∈L である。 L L L 「xz∈L と yz∈L が同等である」の意

証明 (1)⇒(2) L = L(M)、 M=(K, Σ, δ, q0, F) とし、関係 R を 　証明 (1)⇒(2) L = L(M)、 M=(K, Σ, δ, q0, F) とし、関係 R を xRy ⇔ δ(q0, x) =δ(q0, y) と定義すると、明らかに R は有限指数の同値関係である。 （L が R の同値類の和として表されることもほとんど自明） あとはRが右不変であることをいえばよろしい 任意のx, y に対してδ(q, xy)=δ(δ(q, x), y) であるので xRy ⇒ δ(q0, x)= δ(q0, y) ⇒ δ(δ(q0, x), z) = δ(δ(q0, y), z) ⇒ δ(q0, xz)= δ(q0, yz) ⇒ xzRyz より、R は右不変である。

証明 (2)⇒(3)、(3)⇒(1) (2)⇒(3) xRy ⇒ xzRyz (z∈Σ*) ⇒ xz∈L ⇔ yz∈L 　証明 (2)⇒(3)、(3)⇒(1) (2)⇒(3) xRy ⇒ xzRyz (z∈Σ*) ⇒ xz∈L ⇔ yz∈L ⇒ x≡y 。　よって≡は有限指数。 L L (3)⇒(1) 同値関係≡のxを代表元とする同値類を[x]で表す。 L K’={[x] | x∈Σ*} δ’([x], a) = [xa] q’0 = [ε] F’ = {[x] | x∈L} とするとδ’(q’0, x) =δ’([ε], x) = [εx] = [x] であるので x∈L(M’) ⇔ [x]∈F’ ⇔ x∈L ゆえに L(M’) = L である。 L は正規ってこと

例2.2 Nerodeの定理は、ある言語 L が正規でない ことを示すときに有効な道具となる。 　例2.2 Nerodeの定理は、ある言語 L が正規でない ことを示すときに有効な道具となる。 Σ={a, b}上の言語を L={anbn | n≧0} とする。 L を正規と仮定すると、ai≡aj となる整数 i, j (i<j)が存在し、≡は右不変であるので aibi≡ajbi となるはずである。 ところがこれは成立しないので矛盾である。 すなわち、L は正規でない。 L L L

2.4 非決定性の有限オートマトン これまでのオートマトンは、文字 a と状態 q に対してδ(q, a)は一意に定まった。このようなオートマトンを決定性であるという。 非決定性のオートマトン 非決定性のオートマトンとは M=(K, Σ, δ, Q0, F)のことである。ただし Q0⊂K でδは K×Σから 2K への関数である。その他の要素は決定性と同様。

遷移関数と受理状態 非決定性の遷移関数の定義域を次のようにして K×Σから K×Σ*へ拡張する。 これはさらに 2K×Σ* に拡張される。 　遷移関数と受理状態 非決定性の遷移関数の定義域を次のようにして K×Σから K×Σ*へ拡張する。 δ(q, e) = {q} δ(q, ax) = ∪ δ(p, x) (q∈K, a∈Σ, x∈Σ*) p∈δ(q, a) これはさらに 2K×Σ* に拡張される。 δ(S, x) = ∪ δ(q, x) q ∈S そして, x∈Σ* が M によって受理されるとは、 δ(Q0, x)∩F ≠Φ であることをいう。

例2.3 b b q0 q1 q1 a,b 例えば abb に対しては δ(q0, abb) = δ(q0, bb) 　例2.3 b b q0 q1 q1 a,b 非決定性有限オートマトンの状態図 例えば abb に対しては δ(q0, abb) = δ(q0, bb) = δ(q0,b)∪δ(q1,b) = {q0}∪{q1}∪{q2} = {q0, q1, q2} となり q2∈F であるから abb∈L(M) である。

　定理2.5 定義より、決定性の有限オートマトンは |δ(q, a)| = 1 であるような非決定性オートマトンの特別な場合である。 しかしながらこれらのオートマトンの能力には差はないことが示される。 定理2.5 L⊆Σ* が正規であるための必要十分条件は，L が 非決定性の有限オートマトンによって受理されることである。 証明の方針 任意の非決定性のM に対して、L(M) = L(M’) となる 決定性のM’ を構成できることを示せば十分である。

定理2.5の証明 非決定性の有限オートマトン M=(K, Σ, δ, Q0, F) を考える。 Kの任意の部分集合に１つの状態を割り当て、 　定理2.5の証明 非決定性の有限オートマトン M=(K, Σ, δ, Q0, F) を考える。 Kの任意の部分集合に１つの状態を割り当て、 それらに対して次の決定性のM’をつくる。 ポイント！ K’ = 2K δ’(S, a) = ∪ δ(q, a) q ∈S q’0 = Q0 F’ ={R | R ∈ K’ かつ R∩F≠Φ} このオートマトンは M の状態の集合を１つの状態とみなして( {q1, q2,…, qk} = p という具合に) 書き直しただけであり、 L(M) = L(M’) が成立することはすぐに分かる。

例2.4 例2.3 の非決定性オートマトンMに対して、証明の方法に従って M’ を構成すると以下のようになる. 　例2.4 例2.3 の非決定性オートマトンMに対して、証明の方法に従って M’ を構成すると以下のようになる. K={Φ, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}} q’0={q0} F={{q2},{q0, q2}, {q1, q2}, {q0, q1, q2}} a b {q0} {q0} {q2} a a a,b {q0, q1, q2} {q0, q2} a b a b b b b {q0, q1} φ {q1, q2} a a,b

2.5 正規表現と正規集合 この節で分かること 正規表現の（数学的な）定義と意味づけ 2.5 正規表現と正規集合 この節で分かること 正規表現の（数学的な）定義と意味づけ 正規表現は文字列処理において重要な概念 UNIXシステムやプログラミング言語（Perl、Ruby等）で用いられる正規表現は（実用的に）拡張されている 有限オートマトンと正規表現とが、 言語を定義する能力において同等である 正規表現で定義される言語Ｌを受理する 有限オートマトンが存在する その逆もいえる

Unix等における正規表現 ファイル名の正規表現 検索ツールGrepの正規表現 プログラミング言語Perlの正規表現 > rm ＊.txt > cp Important[0-9].doc 検索ツールGrepの正規表現 > grep –E “for.+(256|CHAR_SIZE)” ＊.c プログラミング言語Perlの正規表現 $line = m|^http://.+\.jp/.+$|

正規表現の定義 アルファベットΣ上の正規表現とは A={), (, f, ・, +, *} を用いて次のように定義される。 　正規表現の定義 アルファベットΣ上の正規表現とは A={), (, f, ・, +, *} を用いて次のように定義される。 (1) φとΣの要素は正規表現である (2) αとβが正規表現ならば (α・β)も正規表現である (3) αとβが正規表現ならば (α+β)も正規表現である (4) αが正規表現ならば α* も正規表現である (5) 上から導かれるものだけが正規表現である 例： (a・(a+b)*)

正規表現の意味づけ 正規表現をΣ*の部分集合に写像する 例： a b a,b (i) ||φ|| =φ 　正規表現の意味づけ 正規表現をΣ*の部分集合に写像する (i) ||φ|| =φ (ii) a∈Σに対して ||a|| = {a} (iii) 正規表現α,βに対して ||(α・β)|| = ||α||・||β|| (iv) 正規表現α,βに対して ||(α+β)|| = ||α||+||β|| (v) 正規表現αに対して ||α*|| = ||α||* 例： ||(a・(a+b)*)|| = {ax | x∈{a,b}*} a q1 q0 q2 b a,b

2.5節の構成（同等の証明） 定理2.10 （正規表現→正規集合） 定理2.12 （正規集合→正規表現） 　2.5節の構成（同等の証明） 定理2.10　（正規表現→正規集合） 補題2.2(1) （2.2節より、和L1∪L2は正規集合） 補題2.6 （空集合は正規集合） 補題2.7 （任意の一文字は正規集合） 補題2.8 （積L1・L2は正規集合） 補題2.9 （閉包L*は正規集合） 定理2.12　（正規集合→正規表現） 補題2.11 （||αij(k)|| = Rij(k)） 割と簡単 結構たいへん

　例2.7 図2.9の有限オートマトンに対する正規表現 γ=α11(3) + α13(3) α11(3) = α11(2) + α13(2)・(α33(2))*・α31(2) α11(2) = α11(1) + α12(1)・(α22(1))*・α21(1) α11(1) = α11(0) + α11(0)・(α11(0))*・α11(0) =(a+φ*)+(a+φ*)・(a+φ*)*・(a+φ*) =a* α12(1) = α12(0) + α11(0)・(α11(0))*・α12(0) = b+(a*・b) α22(1) = α22(0) + α21(0)・(α11(0))*・α12(0) = a・a*・b α21(1) = α21(0) + α21(0)・(α11(0))*・α11(0) = a・a* ・・・ γ= a*+a*(baa*)*+a*(baa*)*bbb*+・・・

2.6 順序機械と状態最小化 順序機械とは atcgaatccg... atcgaatccg... 00101100010... 2.6 順序機械と状態最小化 順序機械とは atcgaatccg... atcgaatccg... 有限 オートマトン 順序機械 Yes or No 00101100010...

　順序機械の概念図 a1 a2 ai 入力テープ q ヘッド b1 b2 bi 出力テープ

順序機械の数学的定義 順序機械は、5つ組 S=(K,Σ,⊿,δ,λ) K： 状態の（空でない）集合 Σ： 入力アルファベット 　順序機械の数学的定義 順序機械は、5つ組 S=(K,Σ,⊿,δ,λ) K： 状態の（空でない）集合 Σ： 入力アルファベット ⊿： 出力アルファベット δ： 遷移関数　K×Σ→K　　（K×Σ*→K） λ： 出力関数　K×Σ→⊿　　（K×Σ*→⊿*） （本当はスタート地点を表す q0 もいる） λ(q,ε)=ε　　（q∈K） λ(q,ax)=λ(q,a)λ(δ(q,a), x) （q∈K, a∈Σ, x∈Σ*）

　例2.8 （図2.11） q0 q3 q5 q1 q2 q4 0/0 1/1 1/0 λ(q0, 011) =λ(q0, 0)λ(δ(q0,0), 11) = 0λ(q4, 11) = 0λ(q4, 1)λ(δ(q4,1), 1) = 01λ(q5, 1) = 010

Σ*上の言語から⊿*上の言語への翻訳を意味する 　一般順序機械 一般順序機械とは 順序機械の出力関数を K×Σ→⊿* に拡張したもの 一般順序機械 S = (K,Σ,⊿,δ,λ) に対して S(x) =λ(q0, x) (x∈Σ*) gsm写像 L⊆Σ*に対して S(L) = {λ(q0, x) | x∈L} 語 x の Ｓ による変換 Σ*上の言語から⊿*上の言語への翻訳を意味する

同値・等価・既約 Si=(Ki,Σ,⊿,δi,λi) (i=1,2) について S=(K,Σ,⊿,δ,λ) は 　同値・等価・既約 Si=(Ki,Σ,⊿,δi,λi) (i=1,2) について 状態 p∈K1 と q∈K2 は、任意の x に対して λ1(p, x) =λ2(q, x) であるとき同値といい p≡q とかく　（p≡q ならばδ1(p,x) =δ2(q,x)） S1 と S2 は任意の p∈K1 に対して p≡q となる q∈K2 が存在し、その逆の場合も成り立つとき 等価であるといい S1≡S2 とかく S=(K,Σ,⊿,δ,λ) は 任意の p, q∈K に対して p≡q ならば p=q で あるとき既約であるという 補題2.13

定理2.14 定理2.14 任意の順序機械 S に対して S≡S’ となる 既約な順序機械 S’ が存在する 証明 　定理2.14 定理2.14 任意の順序機械 S に対して S≡S’ となる 既約な順序機械 S’ が存在する 証明 [p] を ≡ による p を含む同値類として、 これを状態とする順序機械を構成する （略：教科書p25）

定理2.15 定理2.15 既約な順序機械は、それと等価な順序機械のうちで、状態数が最小である 証明 ほぼ自明 |K|＞|K’| 　定理2.15 定理2.15 既約な順序機械は、それと等価な順序機械のうちで、状態数が最小である 証明 ほぼ自明 |K|＞|K’| p≡r, q≡r p ⇒ r p≡q q 既約なS S’ 矛盾!

順序機械の状態を最小にする手順 等価で既約な S’ を作ればよい k同値 定理2.14 →既約なものが存在することを保証 　順序機械の状態を最小にする手順 等価で既約な S’ を作ればよい 定理2.14 →既約なものが存在することを保証 k同値 λ(p,x)=λ(q,x)がすべての|x|≦kなるx∈Σ* に対して成り立つとき、p と q は k同値であるといいp≡q とかく Ck を ≡ による K の同値類の集合とする k k

定理2.16 定理2.16 順序機械 S=(K,Σ,⊿,δ,λ) に対して次の関係が成立する 　定理2.16 定理2.16 順序機械 S=(K,Σ,⊿,δ,λ) に対して次の関係が成立する p ≡ q であるための必要十分条件は、p≡q かつ 任意の a∈Σに対してδ(p,a)≡δ(q,a) となること Ck+1=Ck ならば j≧k なるすべての j に対して Ck=Cj Ck+1=Ck であれば、p≡q となる必要十分条件は p≡q |C1|=1 ならば、C2 = C1 n=|K|≧2 ならば、Cn = Cn-1 k+1 k k=1,2,…,n の順に Ck を計算していくと、必ず Ck+1 = Ck となる k が求まり、このとき Ck は≡による同値類の集合に等しい

　例2.9 変換 q0 q3 q5 q1 q2 q4 0/0 1/1 1/0 p0 p2 p3 p1 0/0 1/1 1/0

有限オートマトンの状態最小化のしかた 有限オートマトン M に等価で、状態数が最小 状態を最小化する手順 　有限オートマトンの状態最小化のしかた 有限オートマトン M に等価で、状態数が最小 Nerodeの定理より、同値関係≡のもとで同値類を状態にもつ有限オートマトン M’ 状態を最小化する手順 定理2.17 （定理2.16とほぼ同じ）による 具体的には 離れ小島になっている状態を削除 同値関係≡による同値類 Ck を計算する ここで関係≡は p≡q ⇔ 任意の|x|≦k なる x∈Σ* に対して 　　δ(p, x)∈F←→δ(q, x)∈F L k k k

　例2.10 q0 q3 q5 q1 q2 q4 a b a p1 p0 p2 b a,b 変換