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

(1)

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

(2)

第２章の内容

2.1 定義

2.2 正規集合の演算 2.3 Nerode の定理

2.4 非決定性の有限オートマトン 2.5 正規表現と正規集合

2.6 順序機械と状態最小化

(3)

2.1 定義

a

₁

a

₂

a

_i

q q

ヘッドテープ



有限オートマトン　

M = (K, Σ, δ, q₀, F)

 K = {q0, q1, …, qn} : 状態の集合

 Σ= {a, b, …, c} : 文字の集合（アルファベット）

 q0 : 初期状態

 δ : 遷移関数 K×Σ→ K

 F : 　受理状態の集合（ K の部分集合）

(4)

(1) δ(q, e) = q (q K)∈

(2) δ(q, ax) =δ(δ(q, a), x) (q K, a Σ, x Σ∈ ∈ ∈ ^*)

文字列 w に対して δ(q₀, w) は，その文字列を読んだときのオートマトンの状態を表す。

δ(q₀, w) = p ∈ F であるとき， M は w を受理するという。

M が受理する文字列全体： L(M) ={w | δ(q₀, w) ∈ F}

オートマトンによって受理される集合を正規言語という。

　定義つづき

遷移関数を次のように拡張する。

(5)

a b

b a

a,b

q₀ q₁

q₂ δ(q₀, aba) = δ(δ(q₀, a), ba)

= δ(q₁, ba)

= δ(d(q₁, b), a) = δ(q₀, a)

= q₁ ∈ F

状態遷移図（図２）

状態遷移

L(M) = {a(ba)ⁿ | n 0}≧

　オートマトンの例（ p8 ）

(6)

2.2 正規集合の演算



アルファベット

Σ

上の正規集合の族

R (Σ) = {L | L

は正規言語

}

は集合演算∪

, , ∩

￣のもとでブール代数をなす

R (Σ)

L₁ L₂

(7)

　補題 2.1

L

を受理するオートマトンを

M=(K, Σ, δ, q₀,F)

とするとき，

M=(K, Σ, δ, q₀, K-F)

とすると　

L(M) = L(M)

となる

.

補題

2.1

正規集合

L

の補集合

L =Σ*

－

L

は正規集合

証明

(8)

L₁, L₂ Σ * ⊆

を正規集合とする。

(1) L₁∪ L₂

は正規集合である。

(2) L₁∩ L₂

は正規集合である。

L₁ = L(M₁) 、 M₁ = (K₁, Σ, δ₁, q₀¹, F₁) とし、 L₂ に対しても M₂ を定義する。 M₁, M₂ から次の遷移関数 d と受理状態 F をつくる。

δ = ((q₁, q₂), a) = (δ₁(q₁, a), δ₂(q₂, a))

(q₁∈K₁, q₂∈K₂, a Σ)∈ F = F₁×K₂∪K₁×F₂

　補題 2.2

補題

2.2

証明

₍₁₎ _{について証明する。}

(9)

δ = ((q₁, q₂), e) = (δ₁(q₁, e), δ₂(q₂, e)) = (q₁, q₂) 任意の q₁∈K₁, q₂∈K₂ に対して，

数学的帰納法のベースステップ

δ = ((q₁, q₂), x) = (δ₁(q₁, x), δ₂(q₂, x)) ( 仮定 |x| k)≦ δ((q₁, q₂), ax) = δ(δ((q₁, q₂), a), x)

= δ((δ₁(q₁, a), δ₂(q₂, a)), x)

= (δ₁(δ₁(q₁, a), x), δ₂(δ₂(q₂, a), x))

= (δ₁(q₁, ax), δ₂(q₂, ax))

定義より

帰納法の仮定帰納法の仮定定義より

　証明つづき

(10)

x L(M) δ((q∈ ⇔ ₀¹, q₀²), x) F∈

⇔ (δ₁(q₀¹, x), δ₂(q₀², x)) F∈ ₁×K₂∪K₁×F₂

⇔ δ₁(q₀¹, x) F∈ ₁ 　または　 δ₂(q₀², x) F∈ ₂

⇔ x L(M∈ ₁) L(M∪ ₂) (2) の証明は省略

　証明つづき

(1) のときと、終状態の条件が違うだけ。

(11)

2.3 Nerode の定理



Σ* 上の関係 R は、

xRy ⇒ 任意の z Σ* ∈ に対して xzRyz を満たすとき右不変であるという。



関係 R は、 R による同値類の数が有限で

あるとき、有限指数であるという。

(12)

次の３つは同等である

.

　

(1)

集合

L Σ* ⊆

は正規である。

　

(2) L

はある有限指数で右不変な同値関係

R

による同値類の和として表される。

　

(3)

関係 ≡ は有限指数である。ただし≡

は

x y ≡ ⇔

任意の

z Σ* ∈

に対して

xz, yz L ∈

であるか

xz, yz L ∈

である

。

　定理 2.4 （ Nerode の定理）

定理

2.4

L

L L

「 xz L ∈ と yz L ∈ が同等である」の意

(13)

L = L(M) 、 M=(K, Σ, δ, q₀, F) とし、関係 R を xRy δ(q⇔ ₀, x) =δ(q₀, y)

と定義すると、明らかに R は有限指数の同値関係である。

（ L が R の同値類の和として表されることもほとんど自明）

任意の x, y に対して δ(q, xy)=δ(δ(q, x), y) であるので xRy δ(q⇒ ₀, x)= δ(q₀, y)

⇒ δ(δ(q₀, x), z) = δ(δ(q₀, y), z)

⇒ δ(q₀, xz)= δ(q₀, yz)

⇒ xzRyz より、 R は右不変である。

　証明 (1) (2) ⇒

あとはRが右不変であることをいえばよろしい

(14)

(2) (3)⇒ xRy xzRyz (z Σ*) xz L yz L⇒ ∈ ⇒ ∈ ⇔ ∈

⇒ x y ≡ 。　よって≡は有限指数。

(3) (1)⇒ 同値関係≡の x を代表元とする同値類を [x] で表す。

K’={[x] | x Σ*}∈ δ’([x], a) = [xa]

q’₀ = [ε]

F’ = {[x] | x L}∈

とすると δ’(q’₀, x) =δ’([ε], x) = [εx] = [x] であるので x L(M’) [x] F’ ∈ ⇔ ∈ ⇔ x L∈

　証明 (2) ⇒ (3) 、 (3) ⇒ (1)

L L

L

ゆえに L(M’) = L である。^L ^{は正規ってこと}

(15)

Nerode

の定理は、ある言語

L

が正規でないことを示すときに有効な道具となる。

Nerode

の定理は、ある言語

L

が正規でないことを示すときに有効な道具となる。

Σ={a, b}

上の言語を

L={aⁿbⁿ | n 0} ≧

とする。

L

を正規と仮定すると、

aⁱ≡a^j

となる整数

i, j (i<j)

が存在し、≡は右不変であるので

aⁱbⁱ≡a^jbⁱ

となるはずである。

ところがこれは成立しないので矛盾である。

すなわち、

L

は正規でない。

　例 2.2

L

L L

(16)

非決定性のオートマトンとは

M=(K, Σ, δ, Q₀, F)

のことである。ただし

Q₀⊂K

で

δ

は

K×Σ

から

2^K

への関数である。その他の要素は決定性と同様。

2.4 非決定性の有限オートマトン



これまでのオートマトンは、文字

a

と状態

q

に対して

δ(q, a)

は一意に定まった。このような

オートマトンを決定性であるという。

非決定性のオートマトン

(17)

非決定性の遷移関数の定義域を次のようにして

K×Σ

から

K×Σ*

へ拡張する。

δ(q, e) = {q}

δ(q, ax) =

∪

δ(p, x) (q K, a Σ, x Σ*)∈ ∈ ∈

p∈δ_{(q, a)}

これはさらに

2^K×Σ*

に拡張される。

δ(S, x) =

∪

δ(q, x)

q S∈

そして

, x Σ* ∈

が

M

によって受理されるとは、

δ(Q , x) F ≠Φ ∩

であることをいう。

　遷移関数と受理状態

(18)

b q₁ q₁

q₀ b

a,b

例えば abb に対しては δ(q₀, abb) = δ(q₀, bb)

= δ(q₀,b) δ(q∪ ₁,b)

= {q₀} {q∪ ₁} {q∪ ₂}

= {q₀, q₁, q₂} となり q₂∈F であるから abb L(M) ∈ である。

　例 2.3

非決定性有限オートマトンの状態図

(19)

定義より、決定性の有限オートマトンは |δ(q, a)| = 1 であるような非決定性オートマトンの特別な場合である。しかしながらこれらのオートマトンの能力には差はないことが示される。

L Σ* ⊆ が正規であるための必要十分条件は， L が

非決定性の有限オートマトンによって受理されることである。

任意の非決定性の M に対して、 L(M) = L(M’) となる

　定理 2.5

定理

2.5

証明の方針

(20)

K の任意の部分集合に１つの状態を割り当て、

それらに対して次の決定性の M’ をつくる。

K’ = 2^K

δ’(S, a) =

∪

δ(q, a)

q S∈

q’₀ = Q₀

F’ ={R | R K’ ∈ かつ R F≠Φ}∩

このオートマトンは M の状態の集合を１つの状態とみなして ( {q₁, q₂,…, q_k} = p という具合に ) 書き直しただけであり、

L(M) = L(M’) が成立することはすぐに分かる。

　定理 2.5 の証明

非決定性の有限オートマトン M=(K, Σ, δ, Q₀, F) を考える。

ポイント！

(21)

例 2.3 の非決定性オートマトン M に対して、証明の方法に従って M’ を構成すると以下のようにな

るK={Φ, {q. ₀}, {q₁}, {q₂}, {q₀, q₁}, {q₀, q₂}, {q₁, q₂}, {q₀, q₁, q₂}}

q’₀={q₀}

F={{q₂},{q₀, q₂}, {q₁, q₂}, {q₀, q₁, q₂}}

　例 2.4

b

a {q₀} a

{q₀, q₁, q₂} b {q₀, q₂} a

b a

b

{q₀} a

{q₂} a,b b

b

(22)

2.5 正規表現と正規集合



この節で分かること



正規表現の（数学的な）定義と意味づけ

 正規表現は文字列処理において重要な概念

 UNIX システムやプログラミング言語

（ Perl 、 Ruby 等）で用いられる正規表現は（実用的に）拡張されている



有限オートマトンと正規表現とが、

言語を定義する能力において同等である

 正規表現で定義される言語Ｌを受理する有限オートマトンが存在する

 その逆もいえる

(23)

Unix 等における正規表現



ファイル名の正規表現

> rm

＊

.txt

> cp Important[0-9].doc



検索ツール Grep の正規表現

> grep –E “for.+(256|CHAR_SIZE)”

＊

.c



プログラミング言語 Perl の正規表現

$line = m|^http://.+\.jp/.+$|

(24)

　正規表現の定義



アルファベット

Σ

上の正規表現とは

A={), (, f,

・

, +, *}

を用いて次のように定義され

る。

 (1) φ と Σ の要素は正規表現である

 (2) α と β が正規表現ならば (α ・ β) も正規表現である

 (3) α と β が正規表現ならば (α+β) も正規表現である

 (4) α が正規表現ならば α* も正規表現である

 (5) 上から導かれるものだけが正規表現である



例：

(a

・

(a+b)*)

(25)



正規表現を

Σ*

の部分集合に写像する

 (i) ||φ|| =φ

 (ii) a Σ∈ に対して ||a|| = {a}

 (iii) 正規表現 α,β に対して ||(α ・ β)|| = ||α|| ・ ||β||

 (iv) 正規表現 α,β に対して ||(α+β)|| = ||α||+||β||

 (v) 正規表現 α に対して ||α*|| = ||α||*



例：

 ||(a ・ (a+b)*)||

= {ax | x {a,b}*}∈

　正規表現の意味づけ

a _q

q₀ 1

b

a,b

(26)



定理 2.10 　（正規表現→正規集合）



補題

2.2(1) （ 2.2

節より、和

L₁∪L₂

は正規集合）



補題

2.6

（空集合は正規集合）



補題

2.7

（任意の一文字は正規集合）



補題

2.8

（積

L₁・ L₂

は正規集合）



補題

2.9

（閉包

L*

は正規集合）



定理 2.12 　（正規集合→正規表現）



補題

2.11 （ ||αij(k)|| = Rij(k)

）

割と簡単

結構たいへん

2.5 節の構成（同等の証明）

(27)

　例 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*

・・・

(28)

2.6 順序機械と状態最小化

atcgaatccg...

オートマトン有限オートマトン有限

YesYes or NoNo

atcgaatccg...

順序機械順序機械

00101100010...

順序機械とは

(29)

　順序機械の概念図

q q

ヘッド

a

₁

a

₂

a

_i

入力テープ

b

₁

b

₂

b

_i

出力テープ

(30)

　順序機械の数学的定義



順序機械は、 5 つ組 S=(K,Σ, ,δ,λ) ⊿

K

：状態の（空でない）集合

Σ

：入力アルファベット



⊿：出力アルファベット

δ

：遷移関数　

K×Σ K→

　　（

K×Σ* K→

）

λ

：出力関数　

K×Σ→⊿

　　（

K×Σ*→⊿*

）



（本当はスタート地点を表す

q₀

もいる）

λ(q,ε)=ε

　　（

q K∈

）

λ(q,ax)=λ(q,a)λ(δ(q,a), x)

（

q K, a Σ, x Σ∈ ∈ ∈

*

）

(31)

　例 2.8 （図 2.11 ）

q₀

q₃

q₅

q₁ q₂

q₄ 0/0

1/1

1/1 0/0

0/0 0/0

0/0 1/0 0/0

1/0

1/1

λ(q₀, 011)

=λ(q₀, 0)λ(δ(q₀,0), 11)

= 0λ(q₄, 11)

= 0λ(q₄, 1)λ(δ(q₄,1), 1)

= 01λ(q₅, 1)

= 010

(32)

　一般順序機械



一般順序機械とは



順序機械の出力関数を

K×Σ→⊿*

に拡張したもの



一般順序機械

S = (K,Σ, ,δ,λ) ⊿

に対して

S(x) =λ(q₀, x) (x Σ*)∈



gsm 写像

L Σ*⊆

に対して

S(L) = {λ(q₀, x) | x L}∈

語 x のＳによる変換

Σ* 上の言語から⊿ * 上の言語への翻訳を意味する

(33)

　同値・等価・既約

 Si=(Ki,Σ, ,δ⊿ _i,λi) (i=1,2)

について



状態

p K∈ ₁

と

q K∈ ₂

は、任意の

x

に対して

λ1(p, x) =λ2(q, x)

であるとき同値といい

p q≡

とかく　

（ p q ≡ ならば δ1(p,x) =δ2(q,x) ）

S1

と

S2

は任意の

p K∈ ₁

に対して

p q ≡

となる

q K∈ ₂

が存在し、その逆の場合も成り立つとき

等価であるといい

S1≡S₂

とかく

 S=(K,Σ, ,δ,λ) ⊿

は



任意の

p, q K ∈

に対して

p q ≡

ならば

p=q

であるとき既約であるという

補題 2.13

(34)

　定理 2.14

定理

2.14

[p]

を ≡ による

p

を含む同値類として、

これを状態とする順序機械を構成する

（略：教科書

p25

）証明

任意の順序機械

S

に対して

S S’ ≡

と

なる既約な順序機械

S’

が存在する

(35)

　定理 2.15

定理

2.15

証明

既約な順序機械は、それと等価な順序機械のうちで、状態数が最小である

ほぼ自明

p

既約な

S q

r

S’

|K|

＞

|K’|

p≡r, q≡r p≡q

⇒

(36)

　順序機械の状態を最小にする手順



等価で既約な S’ を作ればよい



定理

2.14 →

既約なものが存在することを保証



k 同値

λ(p,x)=λ(q,x)

がすべての

|x| k≦

なる

x Σ* ∈

に対して成り立つとき、

p

と

q

は

k

同値であるといい

p q≡

とかく

 C_k

を ≡ による

K

の同値類の集合とする

k

(37)

　定理 2.16

定理

2.16

順序機械 S=(K,Σ, ,δ,λ) ⊿ に対して次の関係が成立する 1. p q ≡ であるための必要十分条件は、 p q ≡ かつ

任意の a Σ∈ に対して δ(p,a) δ(q,a) ≡ となること

2. C_k+1=C_k ならば j k ≧ なるすべての j に対して C_k=C_j 3. C_k+1=C_k であれば、 p q ≡ となる必要十分条件は p q≡ 4. |C₁|=1 ならば、 C₂= C₁

5. n=|K| 2 ≧ ならば、 C_n= C_n-1

k+1 k

k

k=1,2,…,n の順に C を計算していくと、必ず C = C となる

(38)

　例 2.9

q₀

q₃

q₅

q₁ q₂

q₄ 0/0

1/1

1/1 0/0

0/0 0/0

0/0 1/0 0/0

1/0

1/1

p₀ p₂

p₃ p₁

0/0

0/0 0/0

0/0

1/1 1/1

1/0 1/0

変換

(39)

　有限オートマトンの状態最小化のしかた



有限オートマトン

M

に等価で、状態数が最小

Nerode の定理より、同値関係≡のもとで同値類を

状態にもつ有限オートマトン M’



状態を最小化する手順

定理 2.17 （定理 2.16 とほぼ同じ）による

具体的には

 離れ小島になっている状態を削除

 同値関係≡による同値類 C_k を計算するここで関係≡は

p q 任意の |x| k なる x Σ* に対して

L

k k k

(40)

　例 2.10

q₀ q₃

q₅

q₁ q₂

q₄

a

a b

b

b b

a b

a _p

p₀ 1

p₂

b a b

a,b

変換

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