文脈自由文法とプッシュダウンオートマトンの等価性

ここでは文脈自由文法とPDAが同等の表現能力を持つことを証明する．まず，PDAが文脈自由文法による文字列 の生成を模倣するのに十分な能力を持っていることから確認する．

定理2.36. どんな文脈自由文法Gに対しても，L(A) = L(G)となるPDA Aを構成することができる．

証明. 文脈自由文法G= (V,Σ, P, S)に対し，PDA A= (Q,Σ, Z, δ, q0, F)を Q:={q₀, q₁, q₂},

Z:=V ∪Σ∪ {$},

δ:={(q0,$q1)} ∪ {(q1a, aq1)|a∈Σ} ∪ {(αq1, Aq1)|A→α∈P} ∪ {($Sq1, q2)}, F:={q₂}

と定義する．

(L(G)⊆L(A)であること)． w ∈L(G)をとると，補題2.27と同様にして最右導出(rightmost derivation)S = β0 =⇒

P β1 =⇒

P · · · =⇒

P βn = wがとれる．このとき各i = 0,1, . . . , n−1に対し，βi = γiAiwi (γi ∈ (V ∪Σ)^∗, Ai ∈V, wi∈Σ^∗)と書ける．導出の各段階においてAi→αi∈Pという規則が適用されるとする と，βi+1=γi+1Ai+1wi+1=γiαiwiである．各i=n−1, . . . ,1,0に対して帰納的にq0w=^∗⇒

δ $γiαiq1wiと なることを示す．i=n−1のときはw=γ_n−1α_n−1w_n−1だから

q0w=⇒

δ $q1w=^∗⇒

δ $γn−1αn−1q1wn−1

となるのでよい．q0w=^∗⇒

δ $γi+1αi+1q1wi+1のとき，(αiq1, Aiq1)∈δより

$γ_i+1α_i+1q₁w_i+1=⇒

δ $γ_i+1A_i+1q₁w_i+1

ここでγi+1Ai+1wi+1=βi=γiαiwiかつ，最右導出であることよりAi+1はγiαi中に出現するから

=∗⇒

δ $γiαiq1wi

となる．よってi= 0について q0w=^∗⇒

δ $γ0α0q1w0=$α0q1=⇒

δ $Sq1=⇒

δ $q2∈F となり，w∈L(A)を得る．

(L(A)⊆L(G)であること)． A^が文字列w∈Σ^∗を受理する際の導出はA^{の作り方より} q0w=⇒

δ $q1w=α1=⇒

δ α2=⇒

δ · · ·=⇒

δ αn−1=⇒

δ αn =$Sq1=⇒

δ q2

の形しかありえない．ここでモノイド準同型写像h: (Z∪Q)^∗ →Z^∗を，Qの元と$を削除する写像，すな わち

h(A) :=A (A∈V のとき), h(a) :=a (a∈Σのとき), h(q) :=ε (q∈Qのとき), h($) :=ε

と定める．このとき

S=h(αn)=^≤⇒¹

P h(αn−1)=^≤⇒¹

P · · ·=^≤⇒¹

P h(α2)=^≤⇒¹

P h(α1) =w はGによる導出S=^∗⇒

P wを与えている．

例2.37. 文脈自由文法G= (V,Σ, P, S)を

V :={S, A}, Σ :={a,b}, P :=

{

S→a|AS, A→a|bA

とするとき，定理2.36の証明に沿ってGに対応するPDAA= (Q,Σ, Z, δ, q₀, F)を構成すると Q={q0, q1, q2},

Z={a,b, S, A,$},

δ={(q₀,$q₁),(q₁a,aq₁),(q₁b,bq₁),(aq₁, Sq₁),(ASq₁, Sq₁),(aq₁, Aq₁),(bAq₁, Aq₁),($Sq₁, q₂)}, F ={q2}

2.3 文脈自由言語 31

となる．このとき，Gの最右導出 S=⇒

P AS=⇒

P AAS=⇒

P AAa=⇒

P AbAa=⇒

P Abaa=⇒

P abaa に対応するA^の導出は

q0abaa=⇒

δ $q1abaa=⇒

δ $aq1baa=⇒

δ $Aq1baa=⇒

δ $Abq1aa=⇒

δ $Abaq1a=⇒

δ $AbAq1a

=⇒

δ $AAq1a=⇒

δ $AAaq1=⇒

δ $AASq1=⇒

δ $ASq1=⇒

δ $Sq1=⇒

δ q2

となる．

次に，PDAによる文字列の受理を模倣する文脈自由文法を構成する．こちらの構成は先程よりやや複雑である．話 を簡単にするために，PDAを一度に1文字ずつしか入力を読み込んだりスタックを操作したりできないようなものに 変形できることを示しておく．

補題2.38. どんなPDAA= (Q,Σ, Z, δ, q0, F)に対しても，PDAB= (Q^′,Σ, Z, δ^′, q0, F)で，2条件

• L(A) = L(B)，

• δ^′ ⊆(Q^′×Q^′)∪(ZQ^′×Q^′)∪(Q^′×ZQ^′)∪(Q^′Σ×Q^′)^*9 をみたすものを構成することができる．

ここでQ^′×Q^′, ZQ^′×Q^′, Q^′×ZQ^′, Q^′Σ×Q^′の元はそれぞれε遷移，1文字ポップする遷移，1文字プッシュす る遷移，1文字読み込む遷移であることに注意する．

証明. PDAA= (Q,Σ, Z, δ, q₀, F)をとる．δ中の各遷移を，1文字ずつ操作する小さな遷移に分解することを考え る．新たなPDAB= (Q^′,Σ, Z, δ^′, q₀, F)を

Q^′:=Q∪







[q^t],[zlq^t], . . . ,[z1· · ·zmq^t], [z₁· · ·z_mq^tw₁], . . . ,[z₁· · ·z_mqw₁· · ·w_l],

[y1· · ·ynr¯^t], . . . ,[yn¯r^t],[¯r^t]

t= (z1· · ·zmqw1· · ·wl, y1· · ·ynr)∈δ





,

δ^′:=













(q,[q^t]),(zj[zj+1· · ·zmq^t],[zjzj+1· · ·zmq^t]), ([z₁· · ·z_mq^tw₁· · ·w_i]w_i+1,[z₁· · ·z_mq^tw₁· · ·w_iw_i+1]),

([z1· · ·zmq^tw1· · ·wl],[y1· · ·ynr¯^t]), ([ykyk+1· · ·yn¯r^t], yk[yk+1· · ·ynr¯^t]),([¯r^t], r)

t= (z1· · ·zmqw1· · ·wl, y1· · ·ynr)∈δ, 1≤j≤m, 0≤i < l, 1≤k≤n













とおく．すなわち，B^はA^における

q w1· · ·wl, z1· · ·zm→y1· · ·yn r

*9むしろPDAの定義にこれに類似した条件を採用している文献の方が多いかもしれない．

という遷移を

q [q^t] [zmq^t] [z1· · ·zmq^t]

[z1· · ·zmq^tw1] [z1· · ·zmq^tw1· · ·wl]

[y₁· · ·y_n¯r^t] [y_nr¯^t] [¯r^t] r ε, ε→ε ε, z_m→ε

w1, ε→ε

ε, ε→ε

ε, ε→yn ε, ε→ε

という遷移の連なりに変換したものである．作り方から条件δ^′⊆(Q^′×Q^′)∪(ZQ^′×Q^′)∪(Q^′×ZQ^′)∪(Q^′Σ×Q^′) は明らかに成り立っている．

(L(A)⊆L(B)であること) 任意にw ∈L(A)をとると，あるσ∈Z^∗とq∈F に対し導出q0w=c0 =⇒

δ c1 =⇒

δ

· · ·=⇒

δ c_n=σq (c_i∈Z^∗QΣ^∗)がとれる．このとき各iに対し，構成からc_i =⇒

δ c_i+1ならばc_i =^∗⇒

δ^′ c_i+1で あるので，導出q0w=^∗⇒

δ^′ σqが得られ，w∈L(B)がわかる．

(L(B)⊆L(A)であること) 任意に w ∈ L(B)をとると，ある σ ∈ Z^∗ と q ∈ F に対し導出 q0w = c0 =⇒

δ^′

c1 =⇒

δ^′ · · · =⇒

δ^′ cn = σq (ci ∈ Z^∗Q^′Σ^∗)がとれる．ここでi < j についてci, cj ∈ Z^∗QΣ^∗ かつ，どの k∈ {i, i+ 1, . . . , j}^{についても}ck ∈Z^∗(Q^′−Q)Σ^∗となっているとする．このときδ^′の定め方より，ある t∈δが存在し，各kについてck= [σkq^twk] (σk ∈Z^∗, wk∈Σ^∗)という形をしている．よってci=⇒

δ cjと なるから導出q₀w=^∗⇒

δ σqが得られ，w∈L(A)がわかる．

例2.39. PDAA= (Q,Σ, Z, δ, q₀, F)を Q:={q0, q1}, Σ :={a,b}, Z:={z},

δ:={t1= (q0a,zq0), t2= (zq0b, q0), t3= (q0, q1)}, F :={q1}

とおく．このAに対応する状態遷移図は

q0 q1

a, ε→z

b,z→ε

ε, ε→ε

である．文字列w∈Σ^∗に含まれる文字a∈Σの個数を|w|aと書くと，このA^{が認識する言語は}L(A) ={w∈ Σ^∗| ∀v≼w[|v|a≥ |v|b]}^{である．補題}2.38に従ってPDAB= (Q^′,Σ, Z, δ^′, q0, F)を構成すると

Q^′={q₀, q₁,[q₀^t1],[q₀^t1a],[z¯q₀^t1],[¯q^t₀¹],[q^t₀²],[zq^t₀²],[zq₀^t2b],[¯q₀^t2],[q₀^t3],[¯q^t₁³]},

δ^′=







(q₀,[q^t₀¹]),([q^t₀¹]a,[q^t₀¹a]),([q₀^t1a],[z¯q₀^t1]),([z¯q₀^t1],z[¯q₀^t1]),([¯q₀^t1], q₀), (q0,[q^t₀²]),(z[q^t₀²],[zq^t₀²]),([zq₀^t2]b,[zq₀^t2b]),([zq^t₀²b],[¯q^t₀²]),([¯q^t₀²], q0]),

(q0,[q₀^t3]),([q₀^t3],[¯q^t₁³]),([¯q₁^t3], q1)







2.3 文脈自由言語 33

となり，対応する状態遷移図は

q0

[q^t₀¹] [q₀^t1a] [z¯q₀^t1] [¯q^t₀¹]

[q^t₀²] [zq^t₀²] [zq₀^t2b] [¯q^t₀²] [q^t₀³] [¯q₁^t3] q1

ε, ε→ε

a, ε→ε ε, ε→ε ε,z→ε

ε, ε→ε

ε, ε→ε

ε,z→ε b, ε→ε ε, ε→ε ε, ε→ε

ε, ε→ε ε, ε→ε ε, ε→ε

となる．

証明を簡潔にするために，もう一つだけ簡単な変形を施しておく．

補題2.40. どんなPDAA= (Q,Σ, Z, δ, q0, F)に対しても，PDAB= (Q^′,Σ, Z, δ^′, q0, F^′)で，4条件

• L(A) = L(B)，

• δ^′ ⊆(Q^′×Q^′)∪(ZQ^′×Q^′)∪(Q^′×ZQ^′)∪(Q^′Σ×Q^′)

• 受理状態がただ一つ，すなわちある状態qaccept∈QについてF^′={qaccept}^，

• 入力を受理するならばスタックが空の状況で受理できる，つまりL(B) ={w∈Σ^∗|q0w=^∗⇒

δ qaccept} をみたすものを構成することができる．

証明. 補題2.38よりA^は前半の2条件をみたすとしてよい．このときPDAB= (Q^′,Σ, Z, δ^′, q₀, F^′)を Q^′:=Q∪ {qaccept} (ただしqaccept̸∈Q),

δ^′:=δ∪ {(q, qaccept)|q∈F} ∪ {(zqaccept, qaccept)|z∈Z}, F^′:={qaccept}

とおけば，Bは所望の条件をみたす．

それでは定理の証明に入ろう．

定理2.41. どんなPDAA^{に対しても，}L(G) = L(A)となる文脈自由文法Gを構成することができる．

証明. 補題2.40より，PDAA= (Q,Σ, Z, δ, q0, F)は

• δ⊆(Q×Q)∪(ZQ×Q)∪(Q×ZQ)∪(QΣ×Q)，

• 受理状態がただ一つ，すなわちある状態qaccept∈QについてF ={qaccept}^，

• 入力を受理するならばスタックが空の状況で受理できる，つまりL(A) ={w∈Σ^∗|q0w=^∗⇒

δ qaccept} という条件をみたすとしてよい．文脈自由文法G= (V,Σ, P, S)を

V :={Ap,q|p, q∈Q},

P :={Ap,p→ε|p∈Q} ∪ {Ap,q →Ap,rAr,q|p, q, r∈Q}

∪{A_p,q→ε|p, q∈Q,(p, q)∈δ}

∪{A_p,q→A_r,s |p, q, r, s∈Q, z ∈Z,(p, zr),(zs, q)∈δ}

∪{Ap,q→aAr,q |p, q, r∈Q, a∈Σ,(pa, r)∈δ}, S :=A_q0,qaccept

と定義する．Pは明らかに有限集合であることに注意する．この文法は次の条件をみたすように定義されている．

主張 2.42. 各変数A_p,q ∈V と文字列w∈Σ^∗に対し，

[

Ap,q =∗⇒

P w

] ⇐⇒

[ pw=^∗⇒

δ q ]

.

証明. (=⇒) 導出Ap,q =∗⇒

P w の長さに関する帰納法で示す．Ap,q =⇒

P w のとき，P の定め方から p = q かつw = ε，または(p, q) ∈ δ かつw = εしかありえないので，前者ならば pw = p =⁰⇒

δ p = q， 後者ならばpw = p =¹⇒

δ q である．Ap,q =⇒

P Ap,rAr,q =∗⇒

P w のとき，Ap,r =∗⇒

P w1, Ar,q =∗⇒

P w2

となるような分割 w = w1w2 がある．よって帰納法の仮定よりpw1 =∗⇒

δ r, rw2 =∗⇒

δ q となるので pw=pw1w2=∗⇒

δ rw2=∗⇒

δ qを得る．次にAp,q=⇒

P Ar,s =∗⇒

P wのとき，Pの定義から(p, zr),(zs, q)∈δ となるようなz∈Zがとれる．よって帰納法の仮定からrw=^∗⇒

δ sであるのでpw=⇒

δ zrw=^∗⇒

δ zs=⇒

δ q を得る．最後にAp,q=⇒

P aAr,q =∗⇒

P w(a∈Σ,(pa, r)∈δ)のとき，w=aw^′とすると帰納法の仮定より rw^′=^∗⇒

δ qであるのでpw=paw^′ =⇒

δ rw^′ =^∗⇒

δ qを得る．

(⇐=) 導出pw=^∗⇒

δ qの長さに関する帰納法で示す．長さが0のときはpw=qよりp=q, w=εしかありえな いからA_p,q =A_p,p =⇒

P ε=wよりよい．長さが1以上のとき，導出pw=^∗⇒

δ qにおいてpwに最初に適 用されるδの規則によって場合分けする．pwはスタックが空の計算状況であるから，δに関する仮定と合 わせて，以下の3通りのいずれかになる．

((p, r)∈δの形のとき) pw=⇒

δ rw=^∗⇒

δ qであるから，帰納法の仮定よりA_r,q =^∗⇒

P wである．(p, r)∈δ からAp,r→ε∈Pであることと合わせてAp,q =⇒

P Ap,rAr,q=⇒

P Ar,q=∗⇒

P wを得る．

((p, zr)∈δの形のとき) pw =⇒

δ zrw =^∗⇒

δ qとなっているが，ここでq はスタックが空の計算状況で あるから，最初にスタックの底にプッシュされた z が初めてポップされる瞬間がなければなら ない．よってその瞬間に適用される規則を (zs, q^′) ∈ δ とすると，ある分解w = uv について pw =⇒

δ zrw =zruv =^∗⇒

δ zsv =⇒

δ q^′v =^∗⇒

δ qとなる．zsv =⇒

δ q^′v がz が初めてポップされる瞬 間であることより，ru=^∗⇒

δ sが成り立つ(一般にはzruv=^∗⇒

δ zsvであるからといってruv=^∗⇒

δ sv とは限らないことに注意)．よって帰納法の仮定よりAr,s =∗⇒

P uかつ Aq′,q =∗⇒

P v であるので Ap,q=⇒

P Ap,q^′Aq^′,q=⇒

P Ar,sAq^′,q=∗⇒

P uAq^′,q=∗⇒

P uv=wを得る．

((pa, r)∈δの形のとき) w=aw^′ (a∈Σ, w^′ ∈Σ^∗)の形に分解でき，pw =paw^′ =⇒

δ rw^′ =^∗⇒

δ qとなっ

ている．よって帰納法の仮定よりAr,q=∗⇒

P w^′であるのでAp,q =⇒

P aAr,q =∗⇒

P aw^′=wを得る．

よって

L(G) ={w∈Σ^∗|Aq₀,q_accept =∗⇒

P w} (S=Aq₀,q_accept より)

={w∈Σ^∗|q0w=^∗⇒

δ qaccept} (主張2.42より)

ドキュメント内 Muller-Schuppの定理 (ページ 35-41)