計算理論 - 北海道大学

代入と準同型写像
凖同型の 特徴づ け
おわり
計算理論
Thomas Zeugmann
北海道大学 大学院情報科学研究科
アルゴ リズ ム研究室
http://www-alg.ist.hokudai.ac.jp/∼thomas/ToC/
第 8 回： CF と準同型写像
(日本語訳： 湊 真一， 大久保 好章)
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 I
こ の 講義では引き 続き ，文脈自由言語の 有用な性質と特徴づ け に
ついて述べる．まず 代入演算から見ていこ う ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 I
こ の 講義では引き 続き ，文脈自由言語の 有用な性質と特徴づ け に
ついて述べる．まず 代入演算から見ていこ う ．
定義 1
Σ と ∆ を任意の 2 つの 有限アルファベットとする．
写像 τ : Σ −→ ℘(∆∗ ) の こ とを代入 (substitution) と呼ぶ．我々は
τ を写像 τ : Σ∗ −→ ℘(∆∗ ) (つまり文字列) に 拡張する．た だし 次
の よう に 定義する．
(1) τ(λ) = λ,
(2) すべての w ∈ Σ∗ と x ∈ Σ に 対し て τ(wx) = τ(w)τ(x).
写像 τ は 次の よう に し て言語 L ⊆ Σ∗ に 一般化される．
[
τ(L) =
τ(w)
w∈L
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 II
つまり，代入演算は， Σ の 各記号を ∆ 上の 言語に 置き 換え る．１
つの 記号に 対応する言語は，有限集合でも無限集合でもよい．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 II
つまり，代入演算は， Σ の 各記号を ∆ 上の 言語に 置き 換え る．１
つの 記号に 対応する言語は，有限集合でも無限集合でもよい．
例． 1
Σ = {0, 1}, ∆ = {a, b} とすると， τ(λ) = λ, τ(0) = {a} および
τ(1) = {b}∗ に より定義される写像 τ は代入である．
τ(010) を計算し てみよう ．定義より
τ(010) = τ(01)τ(0) = τ(0)τ(1)τ(0) = {a}{b} ∗ {a} = ahbia ,
た だし ，最後の 等式は正規表現の 定義に よる．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 III
次に ，代入演算に 関する言語族 L の 閉包が何を意味するかを定義
し よう ．こ こ で特別な考慮が必要である．最初に ちょっ と考え る
と，可能なすべての 代入演算 τ に ついて，条件 τ(L) ∈ L を満たす
必要があるよう に 思われる．
し かし ，こ の 要求は強すぎる． なぜか ?
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 III
次に ，代入演算に 関する言語族 L の 閉包が何を意味するかを定義
し よう ．こ こ で特別な考慮が必要である．最初に ちょっ と考え る
と，可能なすべての 代入演算 τ に ついて，条件 τ(L) ∈ L を満たす
必要があるよう に 思われる．
し かし ，こ の 要求は強すぎる． なぜか ?
Σ = {0, 1}, ∆ = {a, b} かつ L = REG とし よう ．さらに ， τ(0) = L
と仮定する．た だし L は ∆ 上の 任意の 言語であっ て，再帰的に 列
挙可能だが非再帰的な言語であるとする．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 III
次に ，代入演算に 関する言語族 L の 閉包が何を意味するかを定義
し よう ．こ こ で特別な考慮が必要である．最初に ちょっ と考え る
と，可能なすべての 代入演算 τ に ついて，条件 τ(L) ∈ L を満たす
必要があるよう に 思われる．
し かし ，こ の 要求は強すぎる． なぜか ?
Σ = {0, 1}, ∆ = {a, b} かつ L = REG とし よう ．さらに ， τ(0) = L
と仮定する．た だし L は ∆ 上の 任意の 言語であっ て，再帰的に 列
挙可能だが非再帰的な言語であるとする．
すると明らかに τ({0}) = L もまた 成り立つ．し た がっ て
τ({0}) < REG である．一方， {0} ∈ REG であるから, REG は代入
演算に 関し て閉じていないこ とに なる．同様に し て CF も代入に
関し て閉じていないこ とが示される．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 IV
こ こ で考え ないといけ ない点は，許される代入演算の 集合を， Σ
の 要素から L に 属する言語への 写像だけ に 制限し なけ ればいけ な
いという こ とである．し た がっ て，以下の 定義に た ど り着く ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入 IV
こ こ で考え ないといけ ない点は，許される代入演算の 集合を， Σ
の 要素から L に 属する言語への 写像だけ に 制限し なけ ればいけ な
いという こ とである．し た がっ て，以下の 定義に た ど り着く ．
定義 2
Σ を任意の アルファベットとし ，L を Σ 上の 任意の 言語族とする．
もし もすべての 写像 τ : Σ −→ L とすべての L ∈ L に 対し て，
τ(L) ∈ L が成り立つならば， L は代入に 関して閉じ てい る
(closed under substitutions) と言う ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
凖同型写像 I
定義 3
Σ と ∆ を任意の ２ つの 有限アルファベットとする．写像
ϕ : Σ∗ −→ ∆∗ は，
すべての v, w ∈ Σ∗ に 対し てϕ(vw) = ϕ(v)ϕ(w) .
ならば準同型写像 (homomorphism) であると言う ．さらに ，
すべての w ∈ Σ∗ に 対し てϕ(w) = λ ならば w = λ .
ならば， ϕ は λ-自由 (λ-free) 凖同型写像であるという ．そ し て,
ϕ : Σ∗ −→ ∆∗ が凖同型写像ならば， ϕ の逆写像 (inverse)
ϕ−1 : ∆∗ −→ ℘(Σ∗ ) を定義でき る．ただし 各々の s ∈ ∆∗ に ついて
ϕ−1 (s) = {w | w ∈ Σ∗ かつ ϕ(w) = s} .
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
凖同型写像 II
し た がっ て，凖同型写像は代入の 特殊なケースで ある．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
凖同型写像 II
し た がっ て，凖同型写像は代入の 特殊なケースで ある．
すなわち，凖同型写像は， Σ の 各記号を単一要素 (Singleton) の 集
合に 対応づ け る．凖同型写像の 定義より明らかに ， Σ の 各記号に
対する写像 ϕ を決めておけ ば十分である．なお，凖同型写像を扱
う 場合，１個の 文字列だけ を含む言語を表すた めに ， そ の 文字列
そ の もの を記述するこ とが一般的で ある．
（すなわち， {s} と書く
代わりに ，単に s と書く ．
）
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
凖同型写像 II
し た がっ て，凖同型写像は代入の 特殊なケースで ある．
すなわち，凖同型写像は， Σ の 各記号を単一要素 (Singleton) の 集
合に 対応づ け る．凖同型写像の 定義より明らかに ， Σ の 各記号に
対する写像 ϕ を決めておけ ば十分である．なお，凖同型写像を扱
う 場合，１個の 文字列だけ を含む言語を表すた めに ， そ の 文字列
そ の もの を記述するこ とが一般的で ある．
（すなわち， {s} と書く
代わりに ，単に s と書く ．
）
例． 2
Σ = {0, 1}， ∆ = {a, b} とする．ϕ(0) = ab および ϕ(1) = λ と定
義された 写像 ϕ : Σ∗ −→ ∆∗ は準同型であるが λ-自由な準同型で
はない.
ϕ に 1100 を与え ると，
ϕ(1100) = ϕ(1)ϕ(1)ϕ(0)ϕ(0) = λλabab = abab が生成され，
言語 1h0i1 に 対し ては ϕ(1h0i1) = habi となる.
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
注意 点
今導入された 概念の 重要性を知るた めに ，言語
L = {an bn | n ∈ N} を考え てみよう ．こ の 言語は文脈自由である
から，直感的に は {0n 1n | n ∈ N} もまた 文脈自由である．なぜな
らば，我々は文法をた ど りながら，出現するすべての a を 0 に ，
b を 1 に 置き 換え れば良いからである．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
注意 点
今導入された 概念の 重要性を知るた めに ，言語
L = {an bn | n ∈ N} を考え てみよう ．こ の 言語は文脈自由である
から，直感的に は {0n 1n | n ∈ N} もまた 文脈自由である．なぜな
らば，我々は文法をた ど りながら，出現するすべての a を 0 に ，
b を 1 に 置き 換え れば良いからである．
こ の 観察から，もし も出現するすべての a と b を，文字列 v と w
に そ れぞれ置き 換え た とき に ， やはり文脈自由言語が得られるよ
う に 思え る．し かし ，もし も出現するすべての a と b を，文脈自
由な文字列集合 V と W に そ れぞれ置き 換え た とすると，そ れが
文脈自由言語に なるかど う かは，直感的に は，さほど 明らかでは
ない．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
注意 点
今導入された 概念の 重要性を知るた めに ，言語
L = {an bn | n ∈ N} を考え てみよう ．こ の 言語は文脈自由である
から，直感的に は {0n 1n | n ∈ N} もまた 文脈自由である．なぜな
らば，我々は文法をた ど りながら，出現するすべての a を 0 に ，
b を 1 に 置き 換え れば良いからである．
こ の 観察から，もし も出現するすべての a と b を，文字列 v と w
に そ れぞれ置き 換え た とき に ， やはり文脈自由言語が得られるよ
う に 思え る．し かし ，もし も出現するすべての a と b を，文脈自
由な文字列集合 V と W に そ れぞれ置き 換え た とすると，そ れが
文脈自由言語に なるかど う かは，直感的に は，さほど 明らかでは
ない．
し かし ながら, 我々はこ の 閉包性を証明するこ とを目指す． 以下
では，代入の 定義と同じよう に ，常に ２ つの 有限アルファベット
Σ と ∆ を仮定する.
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 I
定理 1
CF は代入演算に 関し て閉じている．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 I
定理 1
CF は代入演算に 関し て閉じている．
(証明) ある１つの 言語 L ∈ CF と ある代入 τ を考え る．た だし す
べての a ∈ Σ に 対し て τ(a) は文脈自由言語であるとする．我々は
τ(L) が文脈自由であるこ とを示さなけ ればならない. そ の た めに ，
L(G) = τ(L) となるよう な文脈自由文法 G = [T , N, σ, P] を作ろう ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 I
定理 1
CF は代入演算に 関し て閉じている．
(証明) ある１つの 言語 L ∈ CF と ある代入 τ を考え る．た だし す
べての a ∈ Σ に 対し て τ(a) は文脈自由言語であるとする．我々は
τ(L) が文脈自由であるこ とを示さなけ ればならない. そ の た めに ，
L(G) = τ(L) となるよう な文脈自由文法 G = [T , N, σ, P] を作ろう ．
L ∈ CF であるから，L = L(G) となるよう なチョムスキー標準形の
文脈自由文法 G = [Σ, N, σ, P] が存在する．次に ，Σ = {a1 , . . . , an }
とし て，すべての a ∈ Σ に 対し て， τ(a) を考え る．仮定より，す
べての a ∈ Σ に 対し て τ(a) ∈ CF である．よっ て，すべての
a ∈ Σ に 対し て τ(a) = L(Ga ) となるよう な文脈自由文法
Ga = [Ta , Na , σa , Pa ] が存在する．こ こ で，集合 N, Na1 , . . . , Nan
が，互いに 素であると仮定し ても一般性は失われない．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 II
こ こ で，先に 進む た め のアイデ アが必要である．そ れを得るた め,
G に おけ る可能な導出を調べてみよう ．次の 導出
∗
σ =⇒ x1 x2 · · · xm ,
G
をすべての xi ∈ Σ (i = 1, . . . , m) に ついて考え よう ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 II
こ こ で，先に 進む た め のアイデ アが必要である．そ れを得るた め,
G に おけ る可能な導出を調べてみよう ．次の 導出
∗
σ =⇒ x1 x2 · · · xm ,
G
をすべての xi ∈ Σ (i = 1, . . . , m) に ついて考え よう ．すると， G
はチョムスキー標準形であるから， 生成規則(hxi → xi ) ∈ P,
i = 1, . . . , m, が必ず 存在し ，そ れに よっ て以下の 導出
∗
m
G
G
σ =⇒ hx1 hx2 · · · hxm =⇒ x1 x2 · · · xm ,
(1)
が，すべての hxi ∈ N に ついて行われるはず である．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 III
像 (写像の 行き 先)τ(x1 · · · xm ) が
τ(x1 )τ(x2 ) · · · τ(xm )
に よっ て計算でき るこ とを考慮すると， こ の 像に 含まれる各文字
列 w1 w2 · · · wm に 対し て，次の 導出
∗
σxi =⇒ wi
i = 1, . . . , m .
G xi
が存在し なけ ればならない．こ の こ とから直ちに G を構築するア
イデアが生まれる．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 IV
hx1 hx2 · · · hxm が得られた とき に ，式 (1) の 導出 を中断するこ と
を考え よう ．x1 x2 · · · xm を導出する代わりに 必要なこ とは，
σx1 · · · σxm を生成するこ とであり，すなわち， i = 1, . . . , m に つ
いて，生成規則 (hxi → xi ) ∈ P を (hxi → σxi ) ∈ P で置き 換え
る必要がある. し た がっ て，以下を定義する．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 IV
hx1 hx2 · · · hxm が得られた とき に ，式 (1) の 導出 を中断するこ と
を考え よう ．x1 x2 · · · xm を導出する代わりに 必要なこ とは，
σx1 · · · σxm を生成するこ とであり，すなわち， i = 1, . . . , m に つ
いて，生成規則 (hxi → xi ) ∈ P を (hxi → σxi ) ∈ P で置き 換え
る必要がある. し た がっ て，以下を定義する．
[
T =
Ta
a∈Σ
N = N∪
[
Na
a∈Σ
σ = σ
P =
[
a∈Σ
Pa
!
!
∪ P[a//σa ] .
こ れを用いて G = [T , N, σ, P] とする．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 V
τ(L) = L(G) を示す作業が残っ ている．
主張 1. τ(L) ⊆ L(G).
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 V
τ(L) = L(G) を示す作業が残っ ている．
主張 1. τ(L) ⊆ L(G).
∗
もし ， xi ∈ Σ に ついて σ =⇒ x1 · · · xm であり， wi ∈ Tx∗i に
G
∗
ついて σxi =⇒ wi ならば（ i = 1 . . . , m）， x1 · · · xm は
G xi
∗
∗
G
G
σ =⇒ hx1 · · · hxm =⇒ x1 · · · xm ,
と導出される（た だし hxi ∈ N）．すると明らかに ，
∗
∗
∗
G
G
G
σ =⇒ hx1 · · · hxm =⇒ σx1 · · · σxm =⇒ w1 · · · wm .
を生成でき る．以上に より主張 1 は示された ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 VI
主張 2. L(G) ⊆ τ(L).
∗
∗
∗
今度は σ ⇒ w (w ∈ T ) から始めよう ．た だし ， w ∈ T である．
もし w = λ ならば，σ → λ も P に 含まれるの で主張は示される．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 VI
主張 2. L(G) ⊆ τ(L).
∗
∗
∗
今度は σ ⇒ w (w ∈ T ) から始めよう ．た だし ， w ∈ T である．
もし w = λ ならば，σ → λ も P に 含まれるの で主張は示される．
そ う でなけ れば， G を構築すれば， w の 導出が以下の 通りである
こ とが確認される．
∗
∗
G
G
σ =⇒ σx1 · · · σxm =⇒ w .
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 VI
主張 2. L(G) ⊆ τ(L).
∗
∗
∗
今度は σ ⇒ w (w ∈ T ) から始めよう ．た だし ， w ∈ T である．
もし w = λ ならば，σ → λ も P に 含まれるの で主張は示される．
そ う でなけ れば， G を構築すれば， w の 導出が以下の 通りである
こ とが確認される．
∗
∗
G
G
∗
σ =⇒ σx1 · · · σxm =⇒ w .
構成法より，式 (1) で示し た 通り， σ =⇒ x1 · · · xm であるこ とが
G
わかっ ている．
さらに ，すべての i = 1, . . . , m に 対し て， w = w1 · · · wm かつ
∗
∗
σxi =⇒ wi となるよう な文字列 w1 , . . . , wm ∈ T が存在する．
G xi
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 VII
以上より wi ∈ τ(xi ) であり，よっ て w ∈ τ(L) が示された ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 VII
以上より wi ∈ τ(xi ) であり，よっ て w ∈ τ(L) が示された ．
最後に ，主張 1 と 2 を合わせ て，
τ(L) = L(G)
を得る．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
代入に 関する 閉包 VII
以上より wi ∈ τ(xi ) であり，よっ て w ∈ τ(L) が示された ．
最後に ，主張 1 と 2 を合わせ て，
τ(L) = L(G)
を得る．
我々の 定理は，次の 好まし い系を持つ．
系2
CF は凖同型写像に 関し て閉じている.
(証明) 凖同型写像は代入の 特殊な形なの で，すべての 単一要素の
部分集合が文脈自由であるこ とを議論すれば十分である．し かし
こ れは自明である．なぜならば，すべての 有限な言語は REG に
属するこ とと， REG ⊆ CF であるこ とは，すでに 証明し ている．
よっ てこ の 系は正し い．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
ダ イク言語 I
文脈自由言語の 講義を始める際に 強調し た こ とは，多く の プログ
ラミング言語では，複数の 種類の バランスの 取れた 括弧を使用す
るという こ とである．し た がっ て，括弧からなる言語をもっ と詳
し く 見ていこ う ．そ の よう な言語はダイク言語 (Dyck languages)
と呼ばれている.
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
ダ イク言語 I
文脈自由言語の 講義を始める際に 強調し た こ とは，多く の プログ
ラミング言語では，複数の 種類の バランスの 取れた 括弧を使用す
るという こ とである．し た がっ て，括弧からなる言語をもっ と詳
し く 見ていこ う ．そ の よう な言語はダイク言語 (Dyck languages)
と呼ばれている.
ダイク言語を定義するた めに ， 以下の 記法が必要である．
n ∈ N+ とし ，
Xn = {a1 , a1 , a2 , a2 , . . . , an , an } .
とする．Xn は，相異なる括弧記号の 集合であっ て， ai は開く 括
弧，ai はそ れに 対応する閉じる括弧である．つまり Xn は n 種類
の 異なる括弧記号の 集合である．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
ダ イク言語 II
以上でダイク言語を定義する準備が整っ た ．
定義 4
次の 条件を満た すとき ，言語 L は n 種類の 括弧記号からなるダ イ
ク言語 (Dyck language) であると言う ．そ の 条件は，文法
Gn = [Xn , {σ}, σ, Pn ]，た だし ，
Pn = {σ → λ, σ → σσ, σ → a1 σa1 , . . . , σ → an σan }
に より生成される言語 Dn と， L が同型 (isomorphic) なこ とで
ある．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
ダ イク言語 II
以上でダイク言語を定義する準備が整っ た ．
定義 4
次の 条件を満た すとき ，言語 L は n 種類の 括弧記号からなるダ イ
ク言語 (Dyck language) であると言う ．そ の 条件は，文法
Gn = [Xn , {σ}, σ, Pn ]，た だし ，
Pn = {σ → λ, σ → σσ, σ → a1 σa1 , . . . , σ → an σan }
に より生成される言語 Dn と， L が同型 (isomorphic) なこ とで
ある．
ダイク言語の 重要性は，こ の 後すぐ明らかに なる．なぜならば，
我々はこ れを用いて，文脈自由言語の 美し い特徴を示す定理を証
明するからである．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 I
定理 3 (Chomsky-Schützenberger の定理)
すべての 文脈自由言語 L に 対し て，以下の 式が成り立つよう な，
n ∈ N+ と凖同型写像 h と正規言語 RL が存在する．
L = h(Dn ∩ RL ) .
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 II
(証明) 任意の １つの 文脈自由言語 L を考え る．こ こ で λ < L を仮
定し ても一般性は失われない．さらに ， L = L(G) であるよう な
チョムスキー標準形の 文脈自由文法 G = [T , N, σ, P] を考え る．
T = {x1 , . . . , xm } とし て， P に 含まれるすべての 生成規則を考え
る．G はチョムスキー標準形であるから， すべての 生成規則は
hi → hi0 hi00 また は hj → x の 形をし ている．非終端の 生成規則
（すなわち hi → hi0 hi00 ）の 総数を t とする．なお，そ の よう な生
成規則から任意の 2 つを選んだとき ，全部ではないがいく つかの
非終端記号が重複するこ とは， 当然あり得る．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 III
全部で m 個の 終端記号と t 個の 生成規則がある．そ こ で，以下の
アルファベットに 対するダイク言語 Dm+t を作っ てみよう ．
Xm+t = {x1 , . . . , xm , xm+1 , . . . , xm+t ,
xm+1 , . . . , xm+t , x1 , . . . , xm } .
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 III
全部で m 個の 終端記号と t 個の 生成規則がある．そ こ で，以下の
アルファベットに 対するダイク言語 Dm+t を作っ てみよう ．
Xm+t = {x1 , . . . , xm , xm+1 , . . . , xm+t ,
xm+1 , . . . , xm+t , x1 , . . . , xm } .
次に ，以下の 通り定義される写像 χm+t : Xm+t −→ T ∗ を考え る．
xj , た だし 1 6 j 6 m ;
χm+t (xj ) =
λ, た だし m + 1 6 j 6 m + t .
そ し て，すべての j = 1, . . . , m + t に 対し χm+t (xj ) = λ とする．
χm+t が凖同型写像であるこ との 証明は，演習問題とし て残し て
おく ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 IV
こ こ までで，以下の 文法を定義する準備ができ た ．
GL = [Xm+t , N, σ, PL ], た だし
PL = {h → xi xi | 1 6 i 6 m かつ (h → xi ) ∈ P}
∪ {h → xi xi xm+j hj00 | 1 6 i 6 m, (h → xi ) ∈ P, 1 6 j 6 t}
∪ {hj → xm+j hj0 | 1 6 j 6 t} .
明らかに GL は 正規文法である．そ こ で RL = L(GL ) とおいて，
L = χm+t (Dm+t ∩ RL ) .
を証明するこ とを目指そ う ．こ れはこ の 後の 主張と補題に より示
される．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 V
主張 1. L ⊆ χm+t (Dm+t ∩ RL ).
主張 1 の 証明は主に 以下の 補題に よっ て示される．
補題 4
G は上記の L を生成する文法であるとし ， GL は RL を生成する文
法であるとする．そ し て h ∈ N とする．もし も
1
1
1
1
1
G
G
G
G
G
h =⇒ w1 =⇒ w2 =⇒ · · · =⇒ wn−1 =⇒ wn ∈ T ∗
∗
ならば，h =⇒ q かつ χm+t (q) = wn となるよう な q ∈ Dm+t が
GL
存在する．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 VI
こ の 補題は，導出の 長さ n に 関する数学的帰納法で証明される．
帰納法の 基底とし て n = 1 とおく ．すると，
1
h =⇒ w1 ∈ T ∗
G
と仮定される． G はチョムスキー標準形であるから，
(h → w1 ) ∈ P が言え る．し た がっ て，チョムスキー標準形の 定
義より，ある x ∈ T に 対し て w1 = x でなけ ればならない．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 VII
∗
我々は， h =⇒ q かつ χm+t (q) = x であるよう な q ∈ Dm+t が
GL
存在するこ とを示さなけ ればならない．定義より明らかに ，生成
規則 h → xx は PL に 属し ている（ PL の 定義の 第 1 の 集合を参
照）．よっ て，単に q = xx とし てよい．すると帰納法の 基底が示
される．なぜならば χm+t の 定義から直ちに 以下が導かれるから
である．
χm+t (q) = χm+t (xx) = χm+t (x)χm+t (x) = xλ = x .
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 VIII
n > 1 に おけ る帰納法の 仮定に 基づ き ，n + 1 に 対する帰納ステッ
プを進めよう ．そ こ で，
1
1
1
1
G
G
G
G
h =⇒ w1 =⇒ · · · =⇒ wn =⇒ wn+1 ∈ T ∗
という 長さ n + 1 の 導出を考え る．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 VIII
n > 1 に おけ る帰納法の 仮定に 基づ き ，n + 1 に 対する帰納ステッ
プを進めよう ．そ こ で，
1
1
1
1
G
G
G
G
h =⇒ w1 =⇒ · · · =⇒ wn =⇒ wn+1 ∈ T ∗
という 長さ n + 1 の 導出を考え る．
n > 1 であっ て，導出の 長さが少なく とも 2 であるから，w1 を導
出するた めの 生成規則は h → h 0 h 00 （た だし h, h 0 , h 00 ∈ N）と
いう 形でなけ ればならない．し た がっ て，ある j が存在し て，
1 6 j 6 t かつ h = hj かつ w1 = hj0 hj00 とならなけ ればならない．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 IX
以上の 考察より，ある v1 , v2 が存在し て， wn+1 = v1 v2 かつ
∗
hj0 =⇒ v1
G
かつ
∗
hj00 =⇒ v2
G
となるはず である．完全な導出の 長さが n + 1 であるから， v1 と
v2 の 導出の 長さは，ど ちらも n 以下でなけ ればならない．し た
がっ て，帰納法の 仮定を適用でき る．すなわち， q1 , q2 ∈ Dm+t
かつ χm+t (q1 ) = v1 かつ χm+t (q2 ) = v2 であるよう な文字列 q1
と q2 が存在する．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 X
さらに ，帰納法の 仮定から，以下がわかる．
∗
hj0 =⇒ q1
かつ
∗
hj00 =⇒ q2 .
GL
GL
(hj → hj0 hj00 ) ∈ P であるこ とを考慮すると，明らかに ，生成規
則 hj → xm+j hj0 は PL に 含まれる．よっ て，
1
∗
GL
GL
h = hj =⇒ xm+j hj0 =⇒ xm+j q1
は正規文法の 導出である．さらに ，こ の 導出の 最後の ステップは，
次の 形をし ているはず である．
1
xm+j q10 hk =⇒ xm+j q10 xx .
GL
た だし 生成規則 hk → xx が適用されており， x は条件
q1 = q10 xx を満た すもの とする．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 XI
こ こ で最後の ステップを，こ れもまた PL に 属する 生成規則
hk → xxxm+j hj00 で置き 換え ると，
1
∗
GL
GL
h = hj =⇒ xm+j hj0 =⇒ xm+j q1 xm+j hj00
∗
=⇒ xm+j q1 xm+j q2 =: q ∈ Dm+t .
GL
が得られる．Dm+t に 属するの は，ダイク言語の 定義に 加え ， q1
の 回りに 括弧 xm+j と xm+j が正し く 使われているこ と，および ，
q2 ∈ Dm+t であるこ とに よる．最後に χm+t の 定義より
χm+t (xm+j q1 xm+j q2 ) = v1 v2 であるこ とは確かである．以上に
より補題が証明され， h = σ に 対し て直ちに 主張 1 が示される．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 XII
主張 2. L ⊇ χm+t (Dm+t ∩ RL ).
こ れもまた ，次に 述べる補題に より証明する．
補題 5
G は先に 定めた L を生成する文法であるとし ， GL は RL を生成す
る文法であるとする．そ し て h ∈ N とする．もし も
1
1
1
GL
GL
GL
h =⇒ w1 =⇒ · · · =⇒ wn ∈ Dm+t
∗
ならば h =⇒ χm+t (wn ) である．
G
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 XIII
こ の 補題は，導出の 長さに 関する数学的帰納法で 証明される．帰
納法の 基底とし て n = 1 とする．
1
h =⇒ w1 ∈ Dm+t .
GL
を考え ると， (h → w1 ) ∈ PL となるはず である．し た がっ て，
w1 = xi xi , 1 6 i 6 m かつ (h → xi xi ) ∈ PL となるよう な xi xi
が必ず 存在する． PL の 定義より， (h → xi ) ∈ P が言え る．し た
がっ て，
1
h =⇒ xi = χm+t (xi xi ) = χm+t (w1 ) .
G
以上で帰納法の 基底が示された ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
チ ョ ムスキー ・シ ュツェンベルガ ー の定理 XIV
帰納ステップはテキストに 示されている．
主張 2 は， h = σ に 対する補題より直接導かれる．
主張 1 と主張 2 を合わせ て，定理が示された ．
計算理論
c
Thomas
Zeugmann
代入と準同型写像
凖同型の 特徴づ け
おわり
Thank you!
計算理論
c
Thomas
Zeugmann