2015-A : : September 25, 2017

教員

: 入力: 高橋光輝

September 25, 2017

1

本講義の資料(教科書およびハンドアウト) は理学部ホームページの「蓮尾一郎」→

「TEACHING」→「形式言語」から入手できる。

Intrduction

オートマトンとは Automatic という単語は、automaton(複数形は automata) から

生まれた単語である。 オートマトンは ˆ ノードとエッジを持ち、(グラフと一緒) ˆ エッジ: 文字でラベル付けされる ˆ 丸と二重丸の区別がある ˆ 文字列(aaa, ab, a100_b100_{,· · ·})_{を受理したり、しなかったりする(単純な) 機械} ˆ 最後に行き着く状態 (state/node) が二重丸ならば受理される ˆ (枝分かれによって、「うまく選んで二重丸に辿り着ける」) 定義 スクリプト M がオートマトンであるとき、 L (M ) :={Mがaccept する文字列全体} Q. Is there L ⊆ Σ∗_{s.t. L ̸= L (M), ∀M: オートマトン} ただし Σ∗は文字列全体である。

言い換えると、Is any L represented by some automaton M? A. No if restrict to nite automaton.

A2. Yes if we allow innitely many states. For example, 文字列 w と状態 q が 1 対 1 対応するようなオートマトンに対して、w ∈ L な状態を二重丸と定義する。

オートマトンの先 FA(nite autom) → PDA(pushdown autom) → TM(turing ma-chine) という順に計算能力が上がるが、チューリングマシン以上の計算能力は存在しない。 実際に研究で扱う際にはチューリングマシン相当の計算能力だけでなく、オートマト ン相当の計算能力もしばしば研究対象として用いられる。 なぜオートマトンなのか?→そこまでパワフルではなく、オートマトン上の諸問題の多 くはdecidable(アルゴリズムで解ける) だから。 例: 定理 入力されたオートマトン M1, M2に対して、L (M1)⊆ L (M2)を判定する アルゴリズムが存在する。L (M1)および L (M2)は無限集合だが、M1, M2は有限な ので、そちらを操作して判定することが可能である。 これはPDA および TM では不可能である。ここから、システム検証への応用が可能 とされる。例えば、M1をネットワークプロトコル、M2を安全性仕様とすると、ネッ トワークプロトコルが安全に運用可能かを判定することができる。

Chapter 1

(

素朴

)

集合論の記法

Def1.1 |x|: x の言の個数 例 |Σ∗_{| = +∞(if Σ ̸= ⊘)} Def1.2 f が単射 (injective) であるとは、 f : X→ Y def.⇔ (x ̸= x′⇒ f (x) ̸= f (x′)) ⇔ (f (x) = f (x′_{)⇒ x = x}′₎ fが全射(surjective) であるとは、 def. ⇔ ∀y ∈ Y, ∃x ∈ X, f (x) = y fが全単射(bijection) であるとは、 def. ⇔ f が全射かつ単射 Def.1.4. f : X (∋ x) → Y, V ⊆ X について、 f (V ) :={f (x) |x ∈ V } ⊆ Y 3

をV の f による像 と呼ぶ。 W ⊆ Y について、 f−1(W ) :={x ∈ X|f (x) ∈ W } ⊆ X をW の f による逆像 と呼ぶ。 Prop.1.1. f : X → Y, V ⊆ X, W ⊆ Y について、 1. f(f−1(W ))⊆ W 証明例1 f(f−1(x))={f (x)|x ∈ f−1(W )} ={f (x) |f (x) ∈ W } ={y ∈ W |∃x.y = f (x)} ⊂ W 証明例2 y ∈ f(f−1(W ))とする。(Aim. y ∈ W ) f(f−1(W ))のdef. より、ある x ∈ f−1(W )に対して y = f (x)、また f−1(x) の定義より f (x)∈ W 。以上より y ∈ W 2. f: surjection⇒ f(f−1(W ))= W 3. V ⊆ f−1_{(f (V ))} 4. f : injective ⇒ V = f−1_{(f (V ))} Thm.1.1 2X = p (X) ={v ⊆ X} ={Xの部分集合全体} 例 Σ ={a, b} のとき、 p (Σ) = 2Σ={{} , {a} , {b} , {a, b}}

CHAPTER 1. (素朴) 集合論の記法 5

第

2

回

有限と無限のせめぎあい コンピューターが扱うものは基本的に「無限」のものであ る。振る舞いが停止する場合を考えるときを可能無限、振る舞いが停止しない場合を 考えるときを実無限と呼ぶ。 参考文献: 野矢茂樹『無限論の教室』 しかし、実際に人間が扱う際には有限のものであるため、コンピューターの振る舞い を記述するプログラムは有限の長さでなければならない。このように、有限の記述で 無限の振る舞いを規定できるのが、一種の形式言語理論の面白さである。 そこで前回は L≤ Σ∗で∀M : 有限オートマトン L ̸= L (M) なるものは存在するか? という問いを設けた。これに対する回答はYes である。 Σ ={a, b}

L ={anbn|n ∈ N} (∋ ε, ab, aabb, aaabbb, · · · )

Def1.5 X∪ Y = {z|z ∈ Xorz ∈ Y } X∩ Y = {z|z ∈ Xandz ∈ Y } X− Y = {z|z ∈ Xandz /∈ Y } Def1.7 X1,· · · , Xnを集合として、 X1× · · · × X = {(x1,· · · , xn)|xi∈ Xi}

このような集合を(Kartesian) product 集合と呼ぶ。ただし (· · · ) は順序対 (ordered tuple) である。 Def1.8 X を集合、Y ⊆ X として、 χY :x→ {0, 1} x7→ { 1 (x∈ Y ) 0 (x /∈ Y )

Def1.9 X1,· · · , Xnを集合として、X1,· · · , Xn上の n 項関係(n-ary relation) とは、

R⊆ X1× X2× · · · × Xn

のことである。

例えば X ={BO, IH, KM} として、R ⊆ X × X となる集合、例えば、

R ={(BO, KM) , (IH, BO) , (IH, KM) , (KM, BO)}

のような集合を考えると、これは X 内の要素どうしの関係を表現していることが分 かる。 則ち、「x と y の間に R の関係がある」とは、 (x, y)∈ R (⊆ X × Y ) である。 Def1.10 R ⊆ X × Y なる二項関係を考える。このとき、R が部分関数 (partial function) であるとは、 ∀x ((x, y) ∈ R ∧ (x, y′_{)∈ R ⇒ y = y}′₎ である。 また、R が関数(function) であるとは、 ˆ R が部分関数であり、 ˆ ∀x.∃y. (x, y) ∈ R である。 Def1.11 R ⊆ X × X なる二項関係を考える。 1. R が反射的 (reexible) であるとは、 ∀x ∈ X, (x, x) ∈ R である。 2. R が推移的 (transitive) であるとは、 (x, y)∈ R, (y, z) ∈ R ⇒ (x, z) ∈ R である。 3. R が対照的 (symmetric) であるとは、 (x, y)∈ R ⇒ (y, x) ∈ R である。

CHAPTER 1. (素朴) 集合論の記法 7 Def R ⊆ X × X なる二項関係を考える。R の反射的推移閉包 (reexible and tran-sitive closure)R∗_{を次のように定義する。} (x, x)∈ R∗, (x, y)∈ R∗| (y, z) ∈ R∗ (x, z)∈ R∗ , (x, y)∈ R (x, y)∈ R∗ Lem. (x, y) ∈ R∗_{であるとき、} ∃n ∈ N, ∃x0, x1,· · · , xn∈ X, x = x0Rx1R· · · Rxn= y ただし R∗は R の0 回以上の繰り返しで s る。 教科書では、R+_{(R の 1 回以上の繰り返し) を R の transitive closure であるとして} いる。

1.1

記号列、アルファベット、言語

Def1.12 文字 a および文字の集合 Σ とし、 a∈ Σ とする。 Def1.13 Σ 上の word(string) とは、 a1a2· · · an(n∈ N, ai∈ N) である。

length 0 の word を ε(empty word) と書く。 また、|x| を word x の長さとする。(e.g. |ε| = 0)

余談であるが、無限word(a0a1a2· · · (ai∈ Σ)) をオートマトンで受理することを考え

るとき、オートマトンの二重丸を無限回踏めばaccept とする、B ü chi acceptance

condition というオートマトンも今後登場する。 Def1.14 x = x1x1· · · xm, y = y1y2· · · ynなるwords を考える。このとき、x と y の 連結(concatenation)x · y を、 x· y = x1x2· · · xmy1y2· · · yn とする。 また、xk ₌ k回 z }| { x· x · · · x である。

Def1.15 prex, sux, subword, subsequence: (省略)

例えば、AAAAA の subword は 6 個、ABCDE の subword はそれ以上存在する。 Def1.17 Σ∗= ∪ n∈N Σn = Σ0∪ Σ1∪ Σ2∪ · · · = {words over Σ} という。 Σ+= Σ∗\ {ε}

={words over Σ of length ≥ 1} Def1.18 xR_{: reversed} Def1.19 Σ 上の言語 (language) とは、L ⊆ Σ∗_{のことである。} e.g. L =⊘ L = Σ∗ Def1.20 L1, L2⊆ Σ∗なるlanguages を考える。 L1· L2:={x1· x2|x1∈ L1, x2∈ L2} Q 言語の積について、単位元および零元は何となるか? A 単位元: L = {ε} 零元: L = ⊘ Def1.21 L∗= ∪ n∈N Ln= ∪ n∈N L· · · L | {z } n回 ={x1x2· · · xn|n ∈ N, xi∈ L} L+= ∪ n≥1 Ln

Chapter 2

有限オートマトンと正則言語

2.1

序章

省略

2.2

有限オートマトンの定義

Def2.1 非決定性有限オートマトン (nondeterministic nite automaton: NFA) とは、

M = (Q, Σ, δ, q0, F )

によって与えられる。このとき、Q は有限の状態集合、Σ はアルファベット、δ は

δ⊆ Q × Σ × Q なる集合で遷移関係と呼び、q0は q0∈ Q なる元で initial state、F は

F⊆ Q なる集合で nite state である。

(q, a, q′) ∈ δ は、状態 q が a で状態 q′ に遷移することを表し、δ が関数である時

(Q × Σ → Q)、M を決定的有限オートマトン (deterministic nite automaton: DFA) と呼ぶ。 Def2.2 M = (Q, Σ, δ, q0, F )なるオートマトンを考える。 M上のcomputation(run) とは、 q0 a1 −→ q1 a2 −→ · · ·_{−−→ q}an n であって、 9

ˆ q0はinitial ˆ (qi, ai+1, qi+1)∈ δ (i ∈ [0, n − 1]) なるものをいう。 このcomputation が accepting であるとは、 qn∈ F である。

worda1a2· · · anが M にaccepted であるとは、a1a2· · · an上の M のaccepting

com-putation があることである。 Def M を NFA とする。このとき、 L (M ) :={x∈ Σ∗|M は x を accept}⊆ Σ∗ を「M は L (M ) を認識(recognize) する」という。

第

3

回

M: an NFA / a DFA M = (Q, Σ, δ (⊆ Q × Σ × Q) , q0(⊆ Q) , F ) L (M ) := { x∈ Σ∗ ( =∪_n≥0Σn )

|x is accepted(⇔ ∃accepting computation) by M}

The language recognized by M (accepted/受理するとも言うが、本講義では使用し ない)

Def. L ⊆ Σ∗_{: Language, M: NFA}

M recognizes L ⇔ L (M) = L ⇔ ∀x ∈ Σ∗(x ∈ L ⇔ x is accepted by M)

※ x∈ L ⇒ x is accepted by M ではない

教科書図2.3 は、

L (M ) ={x|x の中に 0 が偶数個、1 が偶数個含まれる}

CHAPTER 2. 有限オートマトンと正則言語 11 注意 L :={02n12n|n ∈ N} then ∀x ∈ Σ∗_{(x ∈ L ⇒ x ∈ L (M), 逆は成り立たない)} (p.14 下) Def2.4 M = (Q, sig, δ, q0F ) δを次のように δ∗: Q× Σ∗→ Q に拡張する。 δ∗(q, ε (∈ Σ∗)) := δ∗(q, xa) := δ (δ (q, x) , a) (x∈ Σ∗, a∈ Σ) Σ∗の構成に関する帰納法(induction) Σ∗≃ {ε} + Σ∗× Σ Proposition 2.1 M = (Q, Σ, δ, q0, F ): DFA

TFAE(The Following Are Equivalent) 1. x is accepted by M 2. δ∗_(q 0, x)∈ F 例 2.3 M2 s.t. (Σ = {0, 1}) L (M2) = { x|x を 2 進数と見たとき 3 の倍数} 練 2.1.4 L00= { x|x は 00 を sux に持つ} 例 2.7.2 L00をrecofnize する NFA は?

Prop 2.3 M: NFA

M′: M(の initial state) から unreachable な stae を除いた NFA

then

L (M ) = L (M′)

2.3 Equivalance between NFAs & DFAs

Thm 2.1 任意の lang L ⊆ Σ∗_{について次は同値}

1. ∃M: NFA.L = L (M) 2. ∃M: DFA.L = L (M)

注 Nondet. B ü chiautom. ≠ det. B ü chiautom Proof 2. → 1. は明らか (DFA は NFA)

1. → 2. を証明する。 L = L (M )、M はNFA と仮定する。このとき、 DFA : ˜M = ( ˜ Q, Σ, ˜δ, ˜q0, ˜F ) を次のように定義する。 ˜ Q :={S|S ⊆ Q} ˜ δ := ˜Q× Σ → ˜Q (S, a)7→ {q′|∃q ∈ S1, (q, a, q′)∈ δ} ˜ q0:={q0} ( 一点集合: singleton) ˜ F :={S ⊆ Q|S ∩ F ̸= ⊘} 特に M7→ ˜M をpowerset construction という。

Def 言語 L ⊆ Σ∗_{のとき、L is regular ⇔ (def) ∃M : NFA.L = L (M) ⇔ (Thm}

CHAPTER 2. 有限オートマトンと正則言語 13

2.4 ε-NFA

ˆ NFA + ε-transition ˆ これは教科書のあとのほうで使用する (reg.exp. 7→ DFA) Def. An ε-NFA is M = (Q, Σ, δ, q0, F ) の δ⊆ Q × (Σ × {ε}) × Q (in NFA, δ ⊆ Q × Σ × Q) であるもののことである。

Def. A computation of ε-NFA M over a1, a2,· · · , an∈ Σ∗is

q0 ε − → · · · ε − → ·_{−→ q}a1 1 ε − → · · · ε − → ·_{−→ q}a2 2 ε − → · · ·_{−−→ q}an n ε − → · · · ε − → q′ n

Def. x is accepted ⇔ (def) ∃ accepting computation Thm 2.2 L ⊆ Σ∗ _TFTE

1. ∃M: ε-NFA, L = L (M) 2. ∃M: DFA, L = L (M) By the powerset construction,

˜ q0:= { q′|q−→ · · ·ε −→ qε ′ } ˜ δ (S, a) = { q′|∃q ∈ S, q −→ ·a −→ · · ·ε −→ qε ′ } 例 (図省略) L (M ) ={0n1₁n2₂n3|n 1, n2, n3∈ N}

2.5 Pumping Lemma(

反復補題

)

Thm 2.3 (Pumping Lemma) L ⊆ Σ∗_{をregular と仮定すると、}

∃N ≧ 1.∀x ∈ L (|x| ≥ N ⇒ ∃u, v, w ∈ Σ∗_{(x = uvw∧ 1 ≤ |v| ≤ N ∧ ∀m ∈ N.uv}m_{w∈ L))}

Proof L: regular より、∃M.DFA s.t. L = L (M)

N :=(M の状態数)

第

4

回

自主休講

第

5

回

Quiz Input: M1, M2: NFA

Answer: L (M1) = L (M2)かどうか判定

Algolithm L (M1)⊆ L (M2)はcheck できる。L (M2)⊆ L (M1)もcheck 可能。

次回レポート 練習問題2.9: オートマトンの最小化アルゴリズムを実際に実行して理 解を深めてみること。 Prop.2.6 とりあえず skip

2.6

正則表現

2.7

有限オートマトンと正則表現

RegExpΣ → (変換) → ε-NFA (Σ∋) s, t := ⊘ |a (∈ Σ)| s + t |st| sk, L (s)⊆ Σ∗

CHAPTER 2. 有限オートマトンと正則言語 15 Thm.2.7 任意の RegExpS に対して、L (s) = L (Ms)となるような、(|F | = 1 かつ 受理状態からの遷移が存在しない)ε-NFAMsが構成できる(=存在*構成方法 (計算方 法))。 Proof. s ∈ RegExpΣ の構成に関する帰納法。 Base Case 1 s = ⊘ のとき (L (s) = L (⊘) = ⊘)、 (図省略) Base Case 2 s = a ∈ Σ のとき、 L (s) ={a} (⊆ Σ∗) (図省略) Step Case 1 s = t + u のとき、 L (s) = L (t)∪ L (u) 帰納法の仮定より、 L (Mt) = L (t) , L (Mu) = L (u) となる ε-NFAMt, Muの構成が済んでいるとする。 このとき、(図省略) Step Case 2 s = t · u のとき、同様に Mt, Muをとると、(図省略) Step Case 3 s = t∗_{のとき、(図省略)} Thm M: DFA とすると、tM ∈ RegExpΣ が存在して、L (tM) = L (M )となる。しかも構成できる。 Proof. M = (Q, Σ, δ, q0, F ) とする。また Q ={q1, q2,· · · , qn} とする。

アイデア tij ∈ RegExpΣ (i, j ∈ [1, n]) s.t.L (tij) = { x∈ Σ∗|qi x −→ qj } となる tijを作ると、 tM = ∑ js.t.tj∈F t1j アイデア2 tk_ijs.t.L(tk_ij)= { x∈ Σ∗|qi x −→ qj } ただし中間の状態は q1, q2,· · · , qkのみ 各 i, j∈ [1, n] , k ∈ [0, n] に対して、tkijを次のように定義する。 t0_ij =    ∑ as.t.qi a −→qj a i̸= j ∑ as.t.qi a −→qja +⊘ ∗ _{i = j} tk+1_ij = tk_i(k+1) ( tk_(k+1)(k+1) )_∗ tk_(k+1)j+ tkij tij := tnijとすると、 L (tij) = { x∈ Σ∗|qi x −→ qj } tM := ∑ j_s.t.qj∈F tij とすればよい。

2.8 Reg.Lang.

の性質

Thm.2.8 (reg.lang. の closure property) L1, L2: reg のとき、次も regular で

ある。 1. L1∪ L2

L1= L (s) , L2= L (t)なるreg.exp.s, t があって、このとき

L (s + t) = L (s)∪ L (t)

CHAPTER 2. 有限オートマトンと正則言語 17 Corollary 勝手な s ∈ RegExpΣ について、 L (s)⊆ Σ∗ はregular である。 Quiz I: 無限集合のとき、正則言語 Liから生成される ∪ i∈ILiは正則では ない。 例: Li= { 0i₁i} 2. L1∩ L2 3. Σ∗_{\L1(補集合: complement)} Proof. L1= L (M )となるDFA をとる。 M = (Q, Σ, δ, q0, F ) に対して M = (Q, Σ, δ, q0, Q\F ) とすると、 L(M)= Σ∗\L (M) よって Σ∗\L1もreg.

注(重要) NFA で丸と二重丸を反転しても、recognized language は反転しない。

2. の Proof. de Morgan の法則より、 L1∩ L2= ( L1∪ L2 ) 理論上はこのように計算できるが、現代的なオートマトンにおいては

Comple-mentation is expensive である。DFA を反転させる際には MDFA 7→ MDFAで

大きくならないが、NFA を反転させようとすると、MNFA7→ MDFAd 7→ MdDFA

でNFA から DFA の変換が exponential であるため、計算量が爆発的に増えて

Lem. M1= ( Q1, Σ, δ1, q (1) 0 , F1 ) , M2= ( Q2, Σ, δ2, q (2) 0 F2 ) なるNFA を考え る。いま、このようなNFAM1× M2について、 L (M1× M2) = L (M1)∩ L (M2) M1× M2= ( Q1× Q2, Σ, δ, ( q(1)₀ , q(2)₀ ) , F1× F2 ) ただし、 ((q, q′) , a, (q′′, q′′′))∈ δ ⇔ (q, a, q′′)∈ δ1∧ (q′, a, q′′)∈ δ2 Thm.2.10 L1, L2⊆ Σ∗で L2: reg のとき、L1\L2もregular である。 Thm.2.11 L1, L2⊆ Σ∗で L2: reg のとき、L2/L1もregular である。

第

6

回

Σ∗をClassify する有限 formalizm としての相互変換

2.9

ブール行列による有限オートマトンの表現

2.10

最小オートマトン

Q L を L ⊆ Σ∗_{の正則言語として、L = L (M ) なるDFAM で状態数最小のものは} あるか? A ある。 Q そのようなオートマトンは一意であるか? A (同型を除いて) 一意である。 Q そのような最小オートマトンを計算することはできるか?

CHAPTER 2. 有限オートマトンと正則言語 19 A できる。 Intro M を DFA とする。「M 上で同じ役割を果たす語」とは何か。正確に言うと、 δ∗(q0, x1) = δ∗(q0, x2) いま、Σ∗を「役割」でチーム分けする→チーム数は M の状態数と同じになる。 同値関係(equivalent relation) 同値関係とは、「抽象的等号」「ある性質において 一致」という意味である。 Def.2.12 ≡⊆ X × X, X 上の二項関係とする。 ≡ が equiv. rel であるとは、 1. 反射性 (reecivility): ∀x ∈ X.¬ → x ≡ x 2. 対称性 (symmetry): x ≡ y → y ≡ x 3. 推移性 (transitivity): x ≡ y ∧ y ≡ z → x ≡ z 例 ˆ ≡3⊆ N × N x≡3y⇔_defx≡ y (mod 3) ˆ M: DFA, ≡M⊆ Σ∗× Σ∗ x≡M y⇔defδ∗(q0, x) = δ∗(q0, y) X上のequiv.rel.≡⊆ X × X とする。x ∈ X に対して x の同値類であるとは、 [x] :={y ∈ x|x ≡ y} ⊆ X のことをいう。 また、 X/≡:= {[x] |x ∈ X} を X の≡ による商集合 (quotient set) という。

例 N/ ≡3={[0] , [1] , [2] · · · } ={[3] , [4] , [2]} ={{0, 3, 6, · · · } , {1, 4, 7, · · · } , {2, 5, 8, · · · }} Def.2.13 R, R′_{⊆ X × X の X 上の equiv.rel. とする。} R′が R の細分(renement) であるとは、 xR′y⇒ xRy であることをいう。 例 ≡6は≡3のrenement である。 Def.2.14. R ⊆ Σ∗_{× Σ}∗_{のequiv.rel. とする。} Rが右不変(right-invariant) であるとは、 xRy⇒ (∀z ∈ Σ∗.xzRyz) である。

Def.2.15. (Myhill-Nerode relation) L ⊆ Σ∗_{の言語とする。(正則とは限らない)}

RL⊆ Σ∗× Σ∗を

xRLy⇔_def(∀z ∈ Σ∗. (xz∈ L ⇔ yz ∈ L))

とする。

Prop.2.10. RL⊆ Σ∗× Σ∗はequiv.rel. かつ right-invariant である。

CHAPTER 2. 有限オートマトンと正則言語 21 Prop.2.11. L ⊆ Σ∗_{の言語とする。(正則とは限らない)} 決定性オートマトン(有限とは限らない)ML= ( QL, Σ, δL, q0L, F2 ) を次のように定義 する。 QL:= { [x]_R L|x ∈ Σ ∗}_{= Σ}∗_/R L δL:=QL× Σ → Q ([x]_L, a)7→ [xa]_L 例: δL([x]_L, a) := [xa]_L 注: ∀t ∈ QL.∃x ∈ Σ∗.t = [x]L 注2: [x]RL= [y]RL ⇔ xRLy qL₀ := [ε]_L F2:={[x]L|x ∈ L} δL, FLのwell-denedness を check する必要がある。 Lem xRLx′⇒ [xa]_RL = [x′a]_RL(⇔ xaRLx′a) は RLのright-invariance により明らか。 Lem xRLy⇒ (x ∈ L ⇔ y ∈ L) は RLの定義から明らか Prop.2.11.(続き) MLは L をrecognize する。 Proof δ_L∗(q0, x) = [x]_RL δ∗_L(q0, x)∈ FL⇔ x ∈ L

Thm.2.16. (Myhill-Nerode) L ⊆ Σ∗_{としたとき、以下は同値である。}

1. L. regular

2. ∃R ⊆ Σ∗_{× Σ}∗_{(equiv.rel, right-invariant, nite-index)}

∃x1,· · · , xn ∈ Σ∗.s.t.L = [x1]R∪ [x2]R∪ · · · ∪ [xn]R

3. RL is nite-index

Proof. 1. → 2. L = L (M) なる DFAM をとり、R =≡M とする。すると R は

equiv.rel, right-inv, nit-index となる。 しかも、 L = ∪ q0∈F {x|δ∗_(q 0, x) = q} ( =⊘or [xq]_≡M ( ただしδ∗(q0, xq) = q )) Proof. 2. → 3. ˆ 2. の R が RLのrenement であることを示す。(やるだけ) ˆ よって RLもnite-index

Proof. 3. → 1. ML(Prop.2.11.) は L = L (M2)を満たし、QL= Σ∗/RLよりDFA

である。よって L はregular。 Thm.2.17. M = (Q, Σ, δ, q0, F ) , L = L (M )とすると、Q φ −→ QLなる全射 φ が存 在する。 Proof. φ を以下のように定義する。 Q−→ Qφ L q7→ { [x]_R L if ∃x ∈ Σ.s.t.q = δ ∗_(q 0, x) [ε]_R L otherwise

CHAPTER 2. 有限オートマトンと正則言語 23 注 φはwell-dened ∵δ∗_{(q0, x) = δ}∗_{(q0, y)とする。(aim.[x]} RL = [y]RL ⇔ xRLy) 以下省略

第

7

章

Myhill-Nerode L ⊆ Σ∗_{を言語、x, y∈ Σ}∗_として、 x≡cy⇔ ∀z ∈ Σ∗. (xz∈ L ⇔ yz ∈ L) と定義する。即ち、x, y が「L に属するか」について同じ役割を持つということである。 Cor.2.3. (modied) L からカノニカル (canonical. ⇔ arbitrary) に構成される

オートマトン MLを ML= ( QL ( =Σ∗_/≡ L= { [x]_≡ L|x ∈ Σ ∗})_{, Σ, δ} L, q0L, FL ) なお [x]_≡Lを [x]Lとも書く。 Mが決定的オートマトン、L (M ) = L、M = (Q, Σ, δ, q0, F )であるとき、 (q7→_∃[x]_L) Q−→ φ QL (ただし δ∗_{(q0, x) = q) 寄って特に |Q| ≥ |QL|} また、L:regular ⇔ ML:DFA

Cor. L:regular とすると、MLは L をrecognize する状態数最小の DFA

次に、φ : Q→ QLは「ただの関数」よりも性質がいいことを示す。 Def.2.17. M1= ( Q1, Σ, δ1, q10, F1 ) M2= ( Q2, Σ, δ2, q20, F2 ) なるDFAs を考える。 M1から M2へのDFA 準同型 (homomorphism) とは、φ : Q1→ Q2の型の関数で、

1. φ (δ1(q, a)) = δ2(φ (q) , a) ,∀q ∈ Q1,∀a ∈ Σ 2. φ(q1 0 ) = q2 0 3. q ∈ F1⇔ φ (q) ∈ F2∀q ∈ Q1 なるものをいう。 Cor.2.3. (補足) Cor.2.3. で引き起こされる φ : Q↠ QL はDFA-homomorphism である。 Proof. (一部) q ∈ Q, a ∈ Σ とし、δ∗_(q 0, x) = qとする。(i.e.φ (q) = [x]_≡L) すると、 φ (δ (q, a)) = φ (δ (δ∗(q0, x) , a)) = φ (δ∗(q0, xa)) = [xa]_≡ L また、 δL(φ (q) , a) =δL ( [x]_≡ L, a ) = [xa]_≡ L よって等しい。(残りは省略)

ここから、minimal DFA の uniqueness が示せる。 注

{0, 1, 2} ̸={りんご, みかん, なし}

{0, 1, 2} ≃{りんご, みかん, なし}

Def.2.18. M1, M2:DFA で M1と M2が同型(isomorphic) であるとは、M1から M2

へのDFA-homomorphismφ : Q1→ Q2で、全単射であるものが存在するということ

CHAPTER 2. 有限オートマトンと正則言語 25 Ex. φ が全単射で DFA-hom ならば φ−1_{: Q2→ Q1も(自動的に)DFA-hom となる。}

(やってみよう)

Thm.2.18. L;reg.lang. とすると、L を recognize する minimal DFA は同型を除き 一意(unique up to isomorphisms) である。 即ち、 L = L (M1) = L (M2) M1, M2: minimal ⇒ M1 φ −→ ≃ M2 Proof. Cor.2.3. より、 Q1 φ1 −→ QL φ2 ←− Q2 しかし、M1:minimal より φ1は全単射、φ2も全単射。ゆえに M1, M2, MLはすべて 同型。 coalgebla Lem. φ : Q1→ Q2,M1から M2へのDFA-hom ⇒ L (M1) = L (M2) Proof. x∈ L (M1)⇔ x ∈ L (M2) を|x| についての帰納法で示す。 Prop.2.14. 以下は同値である。 1. x ≡Ly 2. x\L (= {z|xz ∈ L}) = y\L Proof. やるだけ

Thm.2.19. L ⊆ Σ∗_{を言語として、} M_L′ :=(Q′_L, Σ, δ_L′, q′L₀ , F_L′) Q′_L:={x\L|x ∈ Σ∗} q₀′L= L δ_L′ : Q′_L× Σ → Q′_L((x\L, a) 7→ (xa) \L) F_L′ ={X ∈ Q′_L|ε ∈ X} (= {x\L|x ∈ L}) とすると、ML′ と MLはisomorphic である。 Proof. 略 例 L = L (0∗10∗) (図省略) 0\L = {x|0x ∈ L (0∗10∗)} =L (0∗10∗) =L 1\L = {x|1x ∈ L (0∗10∗)} =L (0∗) 11\L = {x|11x ∈ L} =⊘ 3 つ目の minimal DFA の作り方 L = L (M )⇝ minimal DFA M すなわち、 M ⇝(オートマトン最小化)M′ ↑partition-renement algorithm による

CHAPTER 2. 有限オートマトンと正則言語 27 idea ˆ 「最低限必要な区別」を求める ˆ 区別の必要のない state は同一視 (「つぶす」) Def.2.10. p と q が distinguishable であるとは、 ∃z ∈ Σ∗_{. (δ}∗_{(p, q)∈ F ̸⇔ δ}∗_{(q, z)∈ F )} である。 Thm.2.20. M:DFA、≡M:indiistinguishability on M とする。ただし、 p≡M q⇔ ∃z. (δ∗(p, q)∈ F ⇔ δ∗(q, z)∈ F ) と定義される。すると、M_/≡ Mがwell-dened で minimal となる。 Q ≡M は計算できるか? A できる。 例.2.18. (図省略) 1. 8 × 8 matrix (実は半分で OK) ではじめは空とする。 2. (x, y) ←{x∈ F, y /∈ F または x /∈ F, y ∈ F}にÖ をつける 3. x a −→ x′_{, y} a −→ y′_{, (x}′_{, y}′_{)がÖ → (x, y) も Ö} 4. saturate するまで 3. を繰り返す 5. (x, y) が Ö なら x ̸≡ny、そうでないなら x≡nyである。

第

8

回

Chapter 3



入力待ち

第

9

回

{0n₁n_{|n ∈ N} っは、not regular, but context-free.}

{

S→ 0 1

S→ 0 S 1 ⇝ derivation trees production rules r∈ V × (V × T )

(図省略: derivation tree) 前回

G = (V, T, P, S)

w⇒ aw′(w, w′∈ (V ∪ T )∗)

⇔def∃α, β ∈ (V ∪ T )∗.∃ (A, γ) ∈ P.w = αAβ, w′= αγβ

CHAPTER 3.  29 Def. w ∈ T∗_とする。 wが G(CFG) によって導出される (derived) とは、 S ⇒∗_Gw L (G) :={w ∈ T∗|S ⇒∗_Gw} 例.3.3. L (G) ={w|(aの個数)=(bの個数)} V ={S, A, B} T ={a, b} P =                              S→ aB S→ bA A→ a A→ aS A→ bAA B→ b B→ bS B→ aBB

Q Given w ∈ T∗ _{and G, can we check if w ∈ L (G)?}

Def. L ⊆ T∗_{is context-free とは、}

∃G : CFG.L = L (G)

Ex.3.2. (Closure properties of CFL) L1, L2:CFL とする。このとき L1∪ L2は

CFL である。 _{

S→ S1

S→ S2

ˆ L1∩ L2はCFL でない。

ˆ L1· L2はCFL である。(s → S1S2) ˆ L∗ 1はCFL である。 ({ s→ ε s→ S1S ) ˆ LR 1 はCFL である。(G1のprod.rule の RHS を revise)

§

3.1.1

導出木(derivation rule)=構文木 (parse tree) Consider a := ( {E} , {+, (, ), id} , { E→ id E→ (E + E) , E ) L (G)∋ id, id + id, id + id + id 問題: id + id + id は複数の derivation tree を持つ Def.3.6. ˆ G:CFG とする。G が ambiguous であるとは、 ∃w ∈ T ˆ L ⊆ T∗_{がingerently ambiguous であるとは、} L = L (G)⇒ G : ambiguous である。 Agenda

ˆ CFG の簡素化、正規化 (Chomsky normal form) ˆ → Pumping Lemma

CHAPTER 3.  31 Lem.3.7. 例      S→ ε S→ B B→ BB とすると、これが生成する言語は{ε} となり、2 番目と 3 番目の式が無駄になる。 G⇝_変形G′ ˆ L (G) = L (G′₎ ˆ G′_{の任意のnonterminal A について、∃w ∈ T}∗_.A⇒∗ G′ w Lem.3.2. 例: _{ S→ ab A→ a Aはunreachable なので無駄である。 Thm.3.4. 例: _     S → BC B → ε C→ ε において B, C は無駄である。 Thm.3.5. { S→ A A→ a において A は無駄である。 Thm.3.5. G = (V, T, P, S):CFG Gを次の条件を満たすCFG G′に変形できる。 ˆ ∀A ∈ V.∃w, w′ _{∈ (V ∪ T )}∗_{.S ⇒}∗ G′ wAw′

ˆ ∀A ∈ V.∃w ∈ T∗_.A⇒∗ G′ w ˆ ∀A ∈ V. (A → ε) /∈ P ˆ ∀A, B ∈ V. (A → B) /∈ P ˆ ∀w ∈ T∗_{(= T}∗_{\ {ε}) .w ∈ L (G) ⇔ w ∈ L (G}′₎ Thm.3.6. G:CFG とする。G を次の条件を満たす CFG G′_{に変形できる。} ˆ ∀w ∈ T∗_{(= T}∗_{\ {ε}) .w ∈ L (G) ⇔ w ∈ L (G}′_{)、すなわち} L (G)\ {ε} = L (G′)\ {ε} ˆ Production rule が全て _{ A→ BC A→ a の形(nonterminal 2 つか、terminal1 つ) 証明 例で、 _{ S→ SaS S→ b

Step 1: terminal a, b に対して fresh な nonterminal Ca, Cbを導入する

         S→ CaS S→ Cb Ca→ a Cb→ b

Step 2: terminal が現れるのは必ず A → a の形。他の rule は必ず

A→ B1B2· · · Bn1 の形。                S→ SD1 D→ CaS S→ Cb Ca→ a Cb→ b

CHAPTER 3.  33 最初の G がThm.3.5. のように simplify されていれば、こうして Chomsky nf. に変形 できる。

§

3.4. CFG の Pumping Lem

(図省略) Thm.3.7. L: context-free language このとき、 ∃N ∈ N.∀z ∈ T∗_{(|z| ≥ N ⇒ ∃u, v, w, x, y ∈ T}∗_{. [condition])} ここでcondition は、 1. z = uvwxy 2. |vx| ≥ 1 3. |vwx| ≤ N 4. ∀n ∈ N.uvn_wtn_{y∈ L} Proof L:CFL なので、∃G : CFG s.t. L = L (G)

Thm.3.6. より G は chomsky normal form としてよい。G の deriv. tree に対して図 のように考える。

Q N = |V | + 1_ 2(|V |+1)_?

A N = 2|V |_{+ 1}

なぜなら、(図省略)

Thm.3.4.1. {|an_bn_cn_{| n ≥ 1} は not CFL}

第

10

回

Regular lang. ⇒ CFL. ⇒ languages (ingeneral) は成り立つが、逆は成り立たない。反例は例えば、 {0n₁n_{|n ∈ N}} はCFL だが Regular lang. ではなく、 {0n₁n₀n_{|n ∈ N}} はlanguage だが CFL ではない。 Thm.3.9. {0n₁n₀n_{|n ∈ N} は context-free でない。}

Proof. L を context-free と仮定し、pubping lemma の定数 N をとり、0N₁N₀N_を

考える。ここで 0N₁N₀N _{∈ L である。}

Pum;ing Lemma より、∃u, v, w, x, y ∈ Σ∗_s.t.

ˆ 0N₁N₀N _{= uvwxy} ˆ v ̸= εorx ̸= ε ˆ |vwx| ≤ N ˆ ∀n ∈ N.uvn_wxn_{y∈ L} 0N1N0N と uvwxy のいち関係による場合分けを行う。 1. v と x がともに最初の 0 のブロックに含まれる uv0wx0yは明らかに L に属さない。矛盾 2. x が 0 と 1 にまたがっている。 xn_{の中で0 と 1 が n 回 ip し、明らかに uv}n_wxn_{y /∈ L である} 3. v が最初の 0 のブロック、x が 1 のブロックに含まれる uv0wx0yは明らかに L に属さない。矛盾 4. v が最初の 0 のブロック、x が最後の 0 のブロックに含まれる |vwx| ≤ N より、不可能 以上より証明完了

CHAPTER 3.  35 Thm.3.10. (Ogden's Lemma) L: CFL とすると、∃N s.t. |z| ≥ N ⇒ ∃u, v, w, x, y s.t. ˆ z = uvwxy ˆ |vx| ≥ 1 vx は少なくとも 1 つの区間を含む ˆ |uwx| ≤ N vwx はたかだか N この区間を含む ˆ ∀n.uvn_wxn_{y∈ L} Proof. 省略 Thm.3.9.1. {0n₁n₀n_{|n ∈ N} は、context-free でない。} Proof. さっきと同じく 0N₁N₀N を考えて、最初の 0N を特定位置とする。

3.5 CFG の membership problem.

input: CFGG と w ∈ Σ∗ output: w ∈ L (G) or not? 例 3.10 _         S→ AB|BC A→ BA|a B→ CC|b C→ AB|a =: G w = baaba = w1w2· · · w5(wi∈ Σ) ideas 1. Vij= { X ∈ V |X−→ wG iwi+1· · · wi+j₋₁ } 2. G は Chomsky normal form

3. V2,3 ={X|X ⇒ w2w3w4} ={X|X → Y Z, (Y ∈ V2,1∧ Z ∈ V3,2)∨ (Y ∈ V2,2∧ Z ∈ V4,1)}

第

11

回

入力待ち

第

12

回

Chapter 4

Turing Machines

intuitions

1. tape を走査する head は q ∈ Q (nite set) なる internal state を持つ 2. The length of the tape is unbounded (before: |tape| = |input word|) 3. head can move to the left and the right (before: only →)

4. The head can write in the tape Def.4.7. A Turing machine is

M = (Q, Σ, Γ, δ, q0, B, F )

Q: nite set of head's states

Σ: input alphabet, Σ ⊆ Γ, B /∈ Σ Γ: tape alpabet

δ: Q × Γ → Q × Γ × {L, R}(Q: current set (of the head), Γ: symbol read, →: partial

function (can be undened), Q: next state, Γ: symbol to write, {L, R}: movement)

B: blank symbol, B ∈ Γ (B ∈ Γ\Σ) F: the set of accepting states F ⊆ Q

Def.4.2,4.3. Skip Turing machines' tasks is

ˆ word classier

ˆ compute functions (§ 4.2) Def.4.4. M: TM

L (M )⊆ Σ∗is dened by L (M) = {w ∈ Σ∗|read w and state changes from q_0 and q, ∃q ∈ F }

しかし! TM は word classier としては、オートマトンとはだいぶ違う。 word が受理される場合は有限時間でわかるが、受理されない場合は、 ˆ δ (q, a) が undened(detect 可能) ˆ 同じ ID に戻る (堂々巡り。detect 可能) ˆ その他、無限に動き続ける

cf. The Halting Problem is undecidable (停止問題の非決定性)

これを決定するalgorithm はない。

In other words, What is the mightiest notion of computation/machine? (theory of computational models)

It turns out...

TM = aTM = nondet. TM = λ-calculus = recursive functions

⇒Church's thesis: Def. A computable funtction if what is computable by TM. Algorithms for automata

ˆ state minimization ˆ emptiness check  Given: M: NFA  Answer: L (M) = ⊘ ˆ inclusion check  Given: M1, M2  Answer: L (M1)⊆ L (M2)

CHAPTER 4. TURING MACHINES 39 おまけ 帰納的= decidable = computable

帰納的可算集合= semidecidable = semiconputable

Negation Theorem P と notP が両方 semidecidable であるとき、P は decidable である。