黒田の定理(形式言語)

1 から 2：文脈依存文法は非収縮文法である（def-kuroda-grammars の後の注意）。3 から 2：黒田標準形の文法は非収縮文法である（rem-kuroda-conventions）。2 から 4：prop-kuroda-grammar-to-lba。4 から 3 と 4 から 1：prop-kuroda-lba-to-grammar。以上で 1, 2, 3, 4 はすべて同値である。

（考え方）機械は導出を一歩ずつ推測してテープの下段で書き換える。導出の途中の文字列は入力より長くならないので、テープに収まる。
（構成）新しい記号 $\square$ をとり $\Delta:=V\cup\Sigma\cup\{\square\}$ とおく。$\Delta$ 上の文字列 $z$ から $\square$ をすべて除いた文字列を $\mathrm{del}(z)$ と書く。同じ長さの空でない文字列の対の有限集合 $P$ を、各 $\sigma\in V\cup\Sigma$ についての対 $(\sigma\square,\ \square\sigma)$（空きを左へ一つ移す）と、$S\to\varepsilon$ 以外の各規則 $\alpha\to\beta$ についての対 $(\alpha\square^{d},\ \beta)$（$d:=|\beta|-|\alpha|\ge0$）の全体とする。テープ記号を $\Gamma:=\Sigma\cup(\Sigma\times\Delta)$ とし、$(a,\zeta)\in\Sigma\times\Delta$ を上段に入力の記号 $a$、下段に作業用の記号 $\zeta$ を置いた二段のマスと考える。状態は $s_0,s_1,s_2,b,m,c,f$ と、各 $(u,v)\in P$ と $2\le j\le|u|$ についての $t_{u,v,j}$ とし、初期状態を $s_0$、$F:=\{f\}$ とする。遷移は次のとおり（$a\in\Sigma$、$Z\in\Sigma\times\Delta$ は任意。$u=u_1\cdots u_k$、$v=v_1\cdots v_k$ とし、$t_{u,v,k+1}$ は $b$ と読む）。

1. 準備：$(s_0,\triangleright,s_1,\triangleright,+1)$、$(s_1,a,s_2,(a,S),+1)$、$(s_2,a,s_2,(a,\square),+1)$、$(s_2,\triangleleft,b,\triangleleft,-1)$。さらに $S\to\varepsilon\in R$ のときに限り $(s_1,\triangleleft,f,\triangleleft,-1)$。
2. 左端へ戻る：$(b,Z,b,Z,-1)$、$(b,\triangleleft,b,\triangleleft,-1)$、$(b,\triangleright,m,\triangleright,+1)$、$(b,\triangleright,c,\triangleright,+1)$。
3. 書き換え：$(m,Z,m,Z,+1)$。各 $(u,v)\in P$ について $(m,(a,u_1),t_{u,v,2},(a,v_1),+1)$ と、$2\le j\le k$ について $(t_{u,v,j},(a,u_j),t_{u,v,j+1},(a,v_j),+1)$。
4. 照合：$(c,(a,a),c,(a,a),+1)$、$(c,\triangleleft,f,\triangleleft,-1)$。
   段階 3 では、状態 $m$ で右へ進んで位置を一つ選び、そこから $k$ マスの下段が $u$ であることを確かめながら $v$ に書き換え、状態 $b$ で左端へ戻る。下段が $u$ と食い違うか右端の印に当たれば、その計算は止まる。
   （空語）$\varepsilon\in L(M)$ と $\varepsilon\in L(G)$ は、どちらも $S\to\varepsilon\in R$ と同値である。
   詳細

   $n=0$ のときテープは $\triangleright\triangleleft$ で、$f$ に至る計算は $s_1$ で $\triangleleft$ を読む遷移を使うものに限るので、$\varepsilon\in L(M)$ は $S\to\varepsilon\in R$ と同値である。$G$ の側でも、$S\to\varepsilon$ 以外の規則は長さを減らさず、$S\to\varepsilon$ があれば $S$ は右辺に現れないので、$\varepsilon$ の導出は $S$ に直接 $S\to\varepsilon$ を適用するものに限る。よって $\varepsilon\in L(G)$ も $S\to\varepsilon\in R$ と同値である。

   
   以下、入力を $x=a_1\cdots a_n$（$n\ge1$）とする。準備を終えて初めて状態 $b$ になったときのテープは $\triangleright(a_1,S)(a_2,\square)\cdots(a_n,\square)\triangleleft$ で、以後どのマスも $(a_i,z_i)$ の形を保つ。下段の文字列を $z:=z_1\cdots z_n$ と書く。
   （$L(M)\subset L(G)$）状態 $b$ から状態 $m$ を経て状態 $b$ に戻る一巡は、ある $(u,v)\in P$ について $z=z'uz''$ を $z'vz''$ に替える。対 $(\sigma\square,\square\sigma)$ では $\mathrm{del}(z)$ は変わらない。対 $(\alpha\square^{d},\beta)$ では、$\alpha,\beta$ が $\square$ を含まないので、$\mathrm{del}(z)=\mathrm{del}(z')\,\alpha\,\mathrm{del}(z'')$ が $\mathrm{del}(z')\,\beta\,\mathrm{del}(z'')$ に替わり、これは $G$ の一歩である。最初は $\mathrm{del}(z)=S$ なので、一巡の回数に関する帰納法により、状態 $b$ ではつねに $S\Rightarrow_G^{*}\mathrm{del}(z)$ である。$n\ge1$ では状態 $f$ に入る遷移は状態 $c$ からのものだけで、状態 $c$ はすべてのマスが $(a,a)$ の形であることを確かめるので、受理されるのは $z=x$、すなわち $S\Rightarrow_G^{*}x$ のときに限る。
   （$L(G)\subset L(M)$）$x\in L(G)$ とし、導出 $S=\eta_0\Rightarrow\eta_1\Rightarrow\cdots\Rightarrow\eta_r=x$ をとる。$x\ne\varepsilon$ なので、上と同じ理由でこの導出は $S\to\varepsilon$ を使わず、$|\eta_0|\le\cdots\le|\eta_r|=n$ である。各 $l$ について、下段が $\eta_l\square^{\,n-|\eta_l|}$ で状態 $b$ の様相に到達できることを $l$ に関する帰納法で示す。$l=0$ は準備による。$\eta_l=\gamma\alpha\theta$、$\eta_{l+1}=\gamma\beta\theta$（規則 $\alpha\to\beta$）とし、$d:=|\beta|-|\alpha|$、$e:=n-|\eta_l|$ とおくと、$|\eta_{l+1}|\le n$ より $d\le e$ である。下段 $\gamma\alpha\theta\square^{e}$ の $\theta$ の直後の空きを、対 $(\sigma\square,\square\sigma)$ の一巡を $|\theta|$ 回行って $\alpha$ の直後まで移す。これを $d$ 回繰り返すと下段は $\gamma\alpha\square^{d}\theta\square^{e-d}$ になり、対 $(\alpha\square^{d},\beta)$ の一巡で $\eta_{l+1}\square^{\,n-|\eta_{l+1}|}$ になる。$l=r$ のとき下段は $x$ であり、状態 $b$ から状態 $c$ に入って照合を通り、$f$ に至る。

（考え方）様相を、各マスを一つの変数記号で表した長さ $n$ の記号列で表し、機械の一歩を規則 $AB\to CD$ でなぞる。受理したら、全部のマスに印を広げてから終端記号に替える。
（変数記号）ヘッドの印の集合を $H:=\{-,\star\}\cup\{(q,\kappa)\mid q\in Q,\ \kappa\in\{\mathrm{o},\mathrm{l},\mathrm{r}\}\}$ とする。$-$ はヘッドがないこと、$(q,\mathrm{o})$ は状態 $q$ のヘッドがそのマスにあること、$(q,\mathrm{l})$・$(q,\mathrm{r})$ はヘッドが左端・右端の印の上にあること（最初・最後のマスに付ける）、$\star$ は受理が済んだことを表す。$G_{\mathrm{K}}$ の変数記号は、開始記号 $S$、補助の $T$、および四つ組 $\langle a,X,h,e\rangle$（$a\in\Sigma$、$X\in\Gamma$、$h\in H$、$e=(e_1,e_2)\in\{0,1\}^{2}$）とする。四つ組は入力の一マスを表し、$a$ はそのマスの入力の記号、$X$ は今のテープの記号、$h$ はヘッドの印で、$e_1=1$・$e_2=1$ はそれぞれ最初・最後のマスであることを表す。
（様相の表示）$x=a_1\cdots a_n$（$n\ge2$）と様相 $c=(q,X_1\cdots X_n,i)$ に対し、$j$ 番目が $\langle a_j,X_j,h_j,([j=1],[j=n])\rangle$ である長さ $n$ の記号列を $\mathrm{enc}(x,c)$ とする。$[\,\cdot\,]$ は条件が成り立てば $1$、そうでなければ $0$ を表し、$h_j$ は $i=j$ なら $(q,\mathrm{o})$、$i=0$ かつ $j=1$ なら $(q,\mathrm{l})$、$i=n+1$ かつ $j=n$ なら $(q,\mathrm{r})$、それ以外は $-$ とする。
（$G_{\mathrm{K}}$ の規則）次の表のとおりとする。表に現れる $a,b\in\Sigma$、$X,Y,Z\in\Gamma$、$e,e'\in\{0,1\}^{2}$、$e_1,e_2\in\{0,1\}$ は、条件の欄の制約のもとで任意である。

どの規則も $AB\to CD$、$A\to BC$、$A\to a$、$S\to\varepsilon$ のいずれかの形で、$S$ はどの規則の右辺にも現れないので、$G_{\mathrm{K}}$ は黒田標準形である。長さ $2$ 以上の入力では、ヘッドのあるマスに隣のマスがあるので、一つのマスしか変えない一歩（端の印へ移る一歩と端の印から戻る一歩）も、隣のマスを文脈として変えずに残す二記号の規則でなぞれる。そのため $A\to B$ の形の規則は要らない。長さ $0,1$ の入力は短い入力の規則で直接扱う。
（導出される記号列）$S$ から $G_{\mathrm{K}}$ で導出される記号列は、次のどれかであることを導出の長さに関する帰納法で示す。

• (i) $S$。(ii) $T$ の後に、ヘッドの印が $-$ で第一成分と第二成分が等しい四つ組が一つ以上並び、最後の一つだけ $e=(0,1)$、ほかは $e=(0,0)$ のもの。
• (iii) $|x|\ge2$ と $c_0(x)\vdash^{*}c$ を満たす様相 $c$ についての $\mathrm{enc}(x,c)$。
• (iv) ある $x=a_1\cdots a_n\in L(M)$（$n\ge2$）について、長さ $n$ で、$j$ 番目が $a_j$ か、第一成分が $a_j$ でヘッドの印が $-$ か $\star$ の四つ組であるもの。
• (v) $L(M)$ に属する長さ $0$ または $1$ の文字列。
  (i) からは生成の規則で (ii) か $\mathrm{enc}(ab,c_0(ab))$ に、短い入力の規則で (v) になる。(ii) に適用できるのは $T$ の規則だけで、結果は (ii) か $\mathrm{enc}(x,c_0(x))$（$|x|\ge3$）である。(iii) の記号列では、印が $(q,\kappa)$ の四つ組がちょうど一つあり、ほかの印は $-$ なので、適用できるのはその四つ組を左辺に含む規則（表の「右へ」から「受理」まで）だけである。「受理」以外の規則は、その四つ組の $X$ と位置（$e$）に合う $M$ の遷移をなぞり、結果は $c\vdash c'$ となる $c'$ についての $\mathrm{enc}(x,c')$ である。逆に $c\vdash c'$ ならば、それをなぞる規則が適用できる。「受理」は $c$ の状態が $F$ に属するときだけ適用でき、そのとき $x\in L(M)$ なので結果は (iv) である。(iv) には $S,T$ も $(q,\kappa)$ の印もないので、適用できるのは伝播と終端の規則だけで、結果は (iv) のままである。(v) は終端記号だけからなる。
  詳細

  (iii) で印 $(q,\mathrm{o})$ が $j$ 番目にあるとする。「右へ」は $e_2=0$、すなわち $j\le n-1$ のときに適用でき、遷移 $(q,X_j,p,Y,+1)$ により $c\vdash(p,y',j+1)$（$y'$ は $j$ 番目を $Y$ に替えたもの）となり、結果は $j$ 番目が $\langle a_j,Y,-,\cdot\rangle$、$j+1$ 番目が $\langle a_{j+1},X_{j+1},(p,\mathrm{o}),\cdot\rangle$ で、これは $\mathrm{enc}(x,(p,y',j+1))$ である。「右端の印へ」は $j=n$ のときで、ヘッドは $n+1$ 番目に移り、結果は $n$ 番目の印が $(p,\mathrm{r})$ の $\mathrm{enc}$ である。「左へ」「左端の印へ」も同様である。印 $(q,\mathrm{l})$ は $i=0$ を表し、ヘッドの下の記号は $\triangleright$ なので、遷移は $(q,\triangleright,p,\triangleright,+1)$ の形に限り、ヘッドは $1$ 番目に移る。これが「左端の印から」で、結果の $1$ 番目の印は $(p,\mathrm{o})$ である。$(q,\mathrm{r})$ も同様である。どの規則も、相手のマスの印が $-$ であることを要求するが、(iii) ではヘッドのないマスの印はすべて $-$ であり、$n\ge2$ なのでヘッドのあるマスには必要な側の隣がある（最初のマスには右隣、最後のマスには左隣）。

  
  （$L(G_{\mathrm{K}})\subset L(M)$）終端記号だけからなる (i)〜(v) の記号列は、(iv) の場合は $x\in L(M)$ そのもの、(v) の場合は $L(M)$ の元である。
  （$L(M)\subset L(G_{\mathrm{K}})$）長さ $0,1$ の元は短い入力の規則で得られる。$x\in L(M)$、$n=|x|\ge2$ とし、受理に至る計算 $c_0(x)=c_0\vdash\cdots\vdash c_s$ をとる。生成の規則で $S\Rightarrow^{*}\mathrm{enc}(x,c_0)$ とし、各一歩をそれをなぞる規則で進めて $\mathrm{enc}(x,c_s)$ を得る。受理の規則でヘッドのあるマスと隣のマスに $\star$ を付け、伝播の規則で $\star$ を全部のマスに広げてから、終端の規則で各マスを $a_j$ に替えると $x$ になる。
  （$G_{\mathrm{C}}$）$G_{\mathrm{K}}$ の規則のうち、「生成」「短い入力」「終端」は文脈依存文法の形（文脈なしに一つの変数記号を書き換えるもの）であり、「右端の印へ」「左端の印へ」「左端の印から」「右端の印から」「伝播」は、二つの記号の一方を文脈として残し、もう一方だけを書き換えるので、これも文脈依存文法の形である。残る「右へ」「左へ」「受理」を、次の規則で置き換えた文法を $G_{\mathrm{C}}$ とする。ヘッドの印に $(p,\kappa)$（$p\in Q$、$\kappa\in\{\mathrm{R},\mathrm{L},\mathrm{R}',\mathrm{L}'\}$）を加える。$\mathrm{R},\mathrm{L}$ はヘッドが右・左へ出発したこと、$\mathrm{R}',\mathrm{L}'$ は隣に着いてまだ確定していないことを表す。

  置き換える規則	文脈依存文法の規則
  右へ	$\langle a,X,(q,\mathrm{o}),(e_1,0)\rangle\to\langle a,Y,(p,\mathrm{R}),(e_1,0)\rangle$（$(q,X,p,Y,+1)\in\delta$）と、各 $p\in Q$ についての $\langle a,Y,(p,\mathrm{R}),e\rangle\langle b,Z,-,e'\rangle\to\langle a,Y,(p,\mathrm{R}),e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle$、$\langle a,Y,(p,\mathrm{R}),e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle\to\langle a,Y,-,e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle$、$\langle a,Y,-,e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle\to\langle a,Y,-,e\rangle\langle b,Z,(p,\mathrm{o}),e'\rangle$
  左へ	上の四つの規則の左右を入れ替え、$\mathrm{R},\mathrm{R}'$ を $\mathrm{L},\mathrm{L}'$ に、$(e_1,0)$ を $(0,e_2)$ に、$+1$ を $-1$ に替えたもの
  受理	$\langle a,X,(f,\kappa),e\rangle\to\langle a,X,\star,e\rangle$（$f\in F$、$\kappa\in\{\mathrm{o},\mathrm{l},\mathrm{r}\}$）

  新しい規則は、どれも一つの変数記号を、隣の高々一記号を文脈として一つの変数記号に書き換えるので、$G_{\mathrm{C}}$ は文脈依存文法である。$G_{\mathrm{K}}$ の (i)〜(v) に、(iii) の $\mathrm{enc}(x,c)$ から「右へ」をなぞる途中の三段階（ヘッドのマスの印を $(p,\mathrm{R})$ にしたもの、さらに右隣の印を $(p,\mathrm{R}')$ にしたもの、さらに元のマスの印を $-$ にしたもの）と、左への同様の三段階を加えた形について、同じ帰納法が成り立つ。途中の各段階で適用できる規則は次の段階へ進む一つだけで、三段階目からは $\mathrm{enc}(x,c')$（$c\vdash c'$）に至るからである。
  詳細

  一段階目では、印が $-$ でない四つ組は $(p,\mathrm{R})$ の一つだけで、適用できるのは右隣の $-$ を $(p,\mathrm{R}')$ にする規則だけである（三番目の規則は右隣に $(p,\mathrm{R}')$ を、四番目の規則は $(p,\mathrm{R}')$ そのものを要する。一段階目の規則は $e_2=0$ を要求するので、出発したのは最後のマスでなく、右隣がある）。二段階目では、$(p,\mathrm{R})$ の右隣が $-$ でないので二番目の規則は適用できず、$(p,\mathrm{R}')$ の左隣が $-$ でないので四番目の規則も適用できない。適用できるのは三番目の規則だけである。三段階目では、印が $-$ でないのは $(p,\mathrm{R}')$ だけで、その左隣は $-$ なので四番目の規則だけが適用でき、結果は $c\vdash(p,y',j+1)$ の $\mathrm{enc}$ である。受理の規則は一つの $\star$ を作るだけで、結果は (iv) に入る。

  
  したがって $L(G_{\mathrm{C}})\subset L(M)$ であり、$L(M)\subset L(G_{\mathrm{C}})$ は $G_{\mathrm{K}}$ と同じように、各一歩を三段階でなぞって示せる。