モノイド準同型による像と逆像

2つの言語L1⊆Σ^∗, L2⊆∆^∗に対し，モノイド準同型h: Σ^∗→∆^∗はL1の像h(L1) ={h(w)|w∈L1} ⊆∆^∗ とL2の逆像h⁻¹(L2) ={w∈Σ^∗|h(w)∈L2} ⊆Σ^∗という2つの言語を定める．ここでは，正則言語のクラスREG と文脈自由言語のクラスCFLがこれら2つの操作について閉じていることを確かめる．4章以降で群の語の問題を考 える際に，逆像をとる操作で閉じた言語クラスを考えることが重要になる．

例2.48. Σ :={a,b,c},∆ :={(,)}^とし，h: Σ^∗→∆^∗をh(a) :=(), h(b) :=)(, h(c) :=εと定義する．L1:=

L((acbc)^∗)⊆Σ^∗としL2⊆∆^∗を例2.23のsemi-Dyck言語とする．このとき，h(L1) = L((())()^∗), h⁻¹(L2) = L((a∪c)^∗)となる^*11．

モノイド準同型の像をとる操作で閉じていることは，文法を用いて簡単に証明することができる．

定理 2.49. 正則言語のクラスREGと文脈自由言語のクラスCFLはモノイド準同型の像をとる操作で閉じている

(closed under homomorphism)．すなわち言語クラスL ∈ {REG,CFL}^{について，}L∈ L^かつL⊆Σ^∗でさらに h: Σ^∗→∆^∗がモノイド準同型ならばh(L)∈ L^である．

証明. i∈ {2,3}^{をとり，言語}L⊆Σ^∗を生成するi型文法G= (V,Σ, P, S)をとる(i型文法については定義2.3を 見よ)．モノイド準同型写像˜h: (V ∪Σ)^∗→(V ∪∆)^∗を

h(A) :=˜ A (A∈V のとき),

˜h(a) :=h(a) (a∈Σのとき)

と定義する．このとき，文法G^′ = (V,∆, P^′, S)をP^′:={A→h(α)˜ |A→α∈P}^とおくとG^′もi型文法であ り，h(L) =h(L(G)) = L(G^′)であることが容易にわかる．

次に，逆像をとる操作で閉じていることを示す．まず，簡単な正則言語の場合から証明する．

定理 2.50. 正則言語のクラスREGはモノイド準同型の逆像をとる操作で閉じている (closed under inverse homomorphism)．すなわち，L∈REGかつL⊆∆^∗でさらにh: Σ^∗→∆^∗がモノイド準同型ならばh⁻¹(L)∈REG である．

証明. L = L(A)となるDFAA = (Q,∆, δ, q0, F)をとる．遷移関数δ:Q×∆ → Qを以下のように拡張して ˆδ:Q×∆^∗→Qを定める^*12．

ˆδ(q, ε) :=q (q∈Q),

δ(q, bvˆ ) := ˆδ(δ(q, b), v) (q∈Q, b∈∆, v∈∆^∗).

このとき，DFAB= (Q,Σ, δ^′, q0, F)をδ^′(q, a) := ˆδ(q, h(a))と定めるとh⁻¹(L) =h⁻¹(L(A)) = L(B)∈REGを 得る．

文脈自由言語の場合には状態だけでなくスタックの内容も考慮する必要があるため，証明はもう少し複雑である．

*11h⁻¹(L2)の元がbを含みえないことは，例えばL2の元は括弧列を左側から1文字ずつ読んでいったときに常に((の個数)≥()の個数)を みたすことからわかる．

*12このˆδ(q, v)はMyhill–Nerodeの定理2.20の(1)の証明で定義したfv(q)と同じものである．

定理2.51. 文脈自由言語のクラスCFLはモノイド準同型の逆像をとる操作で閉じている．すなわち，L∈CFLか つL⊆∆^∗でさらにh: Σ^∗→∆^∗がモノイド準同型ならばh⁻¹(L)∈CFLである．

証明. L = L(A)となるPDA A= (Q,∆, Z, δ, q0, F)をとる．補題2.38よりδ⊆(Q×Q)∪(ZQ×Q)∪(Q× ZQ)∪(Q∆×Q)が成り立つと仮定してよい．自然数c:= max{h(a)|a∈Σ}^をとり，∆^≤c:=∪

k≤c∆^kとおく．

ここでPDAB= (Q^′,Σ, Z, δ^′, q₀^′, F^′)を Q^′:=Q×∆^≤c,

δ^′:={((q, ε)a,(q, h(a)))|q∈Q, a∈Σ}

∪ {(σ(q, vv^′), σ^′(q^′, v^′))|σ∈Z∪ {ε}, q, q^′ ∈Q, v∈∆∪ {ε}, vv^′ ∈∆^≤c,(σqv, σ^′q^′)∈δ}, q₀^′ := (q0, ε),

F^′:=Q× {ε}

とおく．B^{は入力文字列}w ∈ Σ^∗に対し，A^の入力h(w) ∈ ∆^∗ に対する動作を模倣する．ただし，一般に文字 a∈Σに対しh(a)∈∆^∗は2文字以上になりうるので，一旦h(a)を状態(q, h(a))∈Q^′として記憶しておき，h(a) から1文字ずつ読み込むことによりAの動作を模倣する．つまり，∆^≤c はh(a)を一時保存しておくためのバッ ファー(buffer)である．

(h⁻¹(L(A))⊆L(B)であること) 入力文字列をw=a1· · ·anan+1 ∈Σ^∗ (n≥0, ai∈Σ, an+1=ε)，それらの像を h(ai) =bi,1· · ·b_i,l(i) (l(i)≥0, bi,j ∈∆)とする．このときσ∈Z^∗, q∈Q,1≤i≤n+ 1,1≤j ≤l(i)であ れば

[

q₀h(w)=^∗⇒

δ σqb_i,j· · ·b_i,l(i)h(a_i+1)· · ·h(a_n+1) ]

=⇒ [

(q₀, ε)w=^∗⇒

δ^′ σ(q, b_i,j· · ·b_i,l(i))a_i+1· · ·a_n+1 ]

となることを，導出q0h(w)=^∗⇒

δ σqbi,j· · ·b_i,l(i)h(ai+1)· · ·h(an+1)の長さに関する帰納法で示す．長さ0の ときは(q0, ε)w=⇒

δ^′ (q0, b1,1· · ·b_1,l(1))a2· · ·an+1よりよい．長さ1以上のとき，最後に用いられた書き換え 規則が入力文字列を消費したかどうかで場合分けする．

(δ∩((Q×Q)∪(Q×ZQ)∪(ZQ×Q))の元とき) このとき導出は q₀h(w)=^∗⇒

δ σqb_i,j· · ·b_i,l(i)h(a_i+1)· · ·h(a_n+1) =⇒

δ σ^′q^′b_i,j· · ·b_i,l(i)h(a_i+1)· · ·h(a_n+1) という形をしているので，帰納法の仮定と合わせて

q0w=^∗⇒

δ^′ σ(q, bi,j· · ·b_i,l(i))ai+1· · ·an+1=⇒

δ^′ σ^′(q^′, bi,j· · ·b_i,l(i))ai+1· · ·an+1

を得る．

(δ∩(Q∆×Q)の元とき) このとき，導出がj < l(i)について q0h(w)=^∗⇒

δ σqbi,jbi,j+1· · ·bi,l(i)h(ai+1)· · ·h(an+1) =⇒

δ σq^′bi,j+1· · ·bi,l(i)h(ai+1)· · ·h(an+1) という形をしているならば，帰納法の仮定と合わせて

q0w=^∗⇒

δ′ σ(q, bi,jbi,j+1· · ·bi,l(i))ai+1· · ·an+1=⇒

δ′ σ(q^′, bi,j+1· · ·bi,l(i))ai+1· · ·an+1

となり，j=l(i)のときは q₀h(w)=^∗⇒

δ σqb_i,l(i)b_i+1,1· · ·b_i+1,l(i+1)h(a_i+2)· · ·h(a_n+1)

=⇒

δ σq^′b_i+1,1· · ·b_i+1,l(i+1)h(a_i+2)· · ·h(a_n+1)

2.4 言語クラスの閉包性 39

という形だから，帰納法の仮定と合わせて q0w=^∗⇒

δ′ σ(q, bi,l(i))ai+1ai+2· · ·an+1=⇒

δ′ σ(q^′, ε)ai+1ai+2· · ·an+1

=⇒

δ^′ σ(q^′, bi+1,1· · ·b_i+1,l(i+1))ai+2· · ·an+1

を得る．

(L(B)⊆h⁻¹(L(A))であること) δ^′の定め方から，どんなσ∈Z^∗, q∈Q, v∈∆^≤c, u∈Σ^∗に対しても [

(q₀, ε)w=^∗⇒

δ^′ σ(q, v)u ]

=⇒ [

q₀h(w)=^∗⇒

δ σqvh(u) ]

が成り立つことが(導出の長さに関する帰納法で)容易にわかるのでよい．

以上よりh⁻¹(L) =h⁻¹(L(A)) = L(B)∈CFLを得る．

群から定まる言語とグラフ

41

第 3 ^章

群論再入門

第 4 ^章

群の語の問題

43

第 5 ^章

群の Cayley ^グラフ

遠くから見たグラフと木

第 IV ^部

Bass–Serre ^理論入門

付録

47

付録 A

形式言語理論続論

A.1 決定性プッシュダウンオートマトンと決定性文脈自由言語