線形有界オートマトン

$n:=|x|$ とおく。入力の長さ $n$ の様相 $(q,y,i)$ は $q\in Q$、$y\in\Gamma^{n}$、$0\le i\le n+1$ で定まるので、その全体は有限集合であり、個数は $|Q|\cdot|\Gamma|^{n}\cdot(n+2)$ である。二つの様相 $c,c'$ について $c\vdash c'$ かどうかは $\delta$ の有限個の元を調べれば決まる。よって様相を頂点、$\vdash$ を辺とする有限の有向グラフが構成でき、$x\in L(M)$ は「このグラフで $c_0(x)$ から、状態が $F$ に属する様相のどれかに到達できる」ことと同値である。有限グラフの到達可能性は、$c_0(x)$ から到達できる頂点の集合を辺をたどって順に拡げていく（既に加えた頂点は再訪しない）ことで、有限回の操作で計算できる。

新しい記号 $\square$（空き）をとり、$\Delta:=V\cup\Sigma\cup\{\square\}$ とおく。$\Delta$ の上の文字列 $z$ から $\square$ をすべて取り除いた文字列を $\mathrm{del}(z)$ と書く。同じ長さの空でない文字列の対 $(u,v)$ からなる有限集合 $P$ を、次の二種類の対の全体とする。

• 各 $\sigma\in V\cup\Sigma$ について $(\sigma\square,\ \square\sigma)$（空きを左へ一つ移す）。
• $S\to\varepsilon$ 以外の各規則 $\alpha\to\beta\in R$ について、$d:=|\beta|-|\alpha|\ge0$ として $(\alpha\square^{d},\ \beta)$。
  機械のテープ記号の集合を $\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$、$\zeta\in\Delta$、$Z\in\Sigma\times\Delta$ は任意。$u=u_1\cdots u_k$、$v=v_1\cdots v_k$。$k=|u|$ のときは $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$ と食い違うか右端の印に当たれば、その計算は止まる。
   $x=a_1\cdots a_n$ とする。$n=0$ のとき、テープは $\triangleright\triangleleft$ であり、$f$ に至る計算は $s_1$ で $\triangleleft$ を読む遷移によるものに限るので、$\varepsilon\in L(M)$ は $S\to\varepsilon\in R$ と同値である。一方 $S\to\varepsilon$ 以外の規則は長さを減らさず、$S$ は（$S\to\varepsilon$ がある場合）右辺に現れないので、$\varepsilon$ の導出は $S$ に直接 $S\to\varepsilon$ を適用するものに限り、$\varepsilon\in L(G)$ も $S\to\varepsilon\in R$ と同値である。
   以下 $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\in\Delta^{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^{*}\mathrm{del}(z)=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)$ の一巡で $\gamma\beta\theta\square^{e-d}=\eta_{l+1}\square^{\,n-|\eta_{l+1}|}$ になる。$l=r$ のとき下段は $x$ であり、状態 $b$ から状態 $c$ に入って照合を通り、$f$ に至る。

（変数記号）ヘッドの印の集合を
$$H:=\{-\}\cup\{\,(q,\kappa)\mid q\in Q,\ \kappa\in\{\mathrm{o},\mathrm{l},\mathrm{r},\mathrm{R},\mathrm{L},\mathrm{R}',\mathrm{L}'\}\,\}$$
とする。$-$ はヘッドがないこと、$(q,\mathrm{o})$ は状態 $q$ のヘッドがそのマスにあること、$(q,\mathrm{l})$・$(q,\mathrm{r})$ はヘッドが左端・右端の印の上にあること（それぞれ最初・最後のマスにだけ付ける）を表す。$\mathrm{R},\mathrm{L},\mathrm{R}',\mathrm{L}'$ はヘッドが隣のマスへ移る途中を表す印で、$\mathrm{R}$・$\mathrm{L}$ は右・左へ出発したこと、$\mathrm{R}'$・$\mathrm{L}'$ は左・右から到着してまだ確定していないことを表す。変数記号は、開始記号 $S$、補助の $T$、および四つ組
$$\langle a,X,h,e\rangle\qquad(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$ は最後のマスであることを表す。
（規則）以下、規則の左辺と右辺に現れる文字は、その位置の条件を満たす範囲で任意にとる。

• 生成：$S\to\langle a,a,(q_0,\mathrm{l}),(1,1)\rangle$、$S\to T\langle a,a,-,(0,1)\rangle$、$T\to T\langle a,a,-,(0,0)\rangle$、$T\to\langle a,a,(q_0,\mathrm{l}),(1,0)\rangle$。
• 右への遷移 $(q,X,p,Y,+1)\in\delta$（$X\in\Gamma$）について：$\langle a,X,(q,\mathrm{o}),(e_1,0)\rangle\to\langle a,Y,(p,\mathrm{R}),(e_1,0)\rangle$ と $\langle a,X,(q,\mathrm{o}),(e_1,1)\rangle\to\langle a,Y,(p,\mathrm{r}),(e_1,1)\rangle$。
• 左への遷移 $(q,X,p,Y,-1)\in\delta$（$X\in\Gamma$）について：$\langle a,X,(q,\mathrm{o}),(0,e_2)\rangle\to\langle a,Y,(p,\mathrm{L}),(0,e_2)\rangle$ と $\langle a,X,(q,\mathrm{o}),(1,e_2)\rangle\to\langle a,Y,(p,\mathrm{l}),(1,e_2)\rangle$。
• 端の印の遷移 $(q,\triangleright,p,\triangleright,+1)$ について $\langle a,X,(q,\mathrm{l}),e\rangle\to\langle a,X,(p,\mathrm{o}),e\rangle$、$(q,\triangleleft,p,\triangleleft,-1)$ について $\langle a,X,(q,\mathrm{r}),e\rangle\to\langle a,X,(p,\mathrm{o}),e\rangle$。
• 右への移動（各 $p\in Q$）：
  $$\begin{aligned}\langle a,X,(p,\mathrm{R}),e\rangle\langle b,Z,-,e'\rangle&\to\langle a,X,(p,\mathrm{R}),e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle,\\ \langle a,X,(p,\mathrm{R}),e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle&\to\langle a,X,-,e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle,\\ \langle a,X,-,e\rangle\langle b,Z,(p,\mathrm{R}'),e'\rangle&\to\langle a,X,-,e\rangle\langle b,Z,(p,\mathrm{o}),e'\rangle.\end{aligned}$$
• 左への移動（各 $p\in Q$）：上の三つの規則の左右を入れ替えたもの。すなわち $\langle b,Z,-,e'\rangle\langle a,X,(p,\mathrm{L}),e\rangle\to\langle b,Z,(p,\mathrm{L}'),e'\rangle\langle a,X,(p,\mathrm{L}),e\rangle$、$\langle b,Z,(p,\mathrm{L}'),e'\rangle\langle a,X,(p,\mathrm{L}),e\rangle\to\langle b,Z,(p,\mathrm{L}'),e'\rangle\langle a,X,-,e\rangle$、$\langle b,Z,(p,\mathrm{L}'),e'\rangle\langle a,X,-,e\rangle\to\langle b,Z,(p,\mathrm{o}),e'\rangle\langle a,X,-,e\rangle$。
• 受理（各 $f\in F$、$\kappa\in\{\mathrm{o},\mathrm{l},\mathrm{r}\}$）：$\langle a,X,(f,\kappa),e\rangle\to a$、$a\langle b,Z,-,e\rangle\to ab$、$\langle b,Z,-,e\rangle a\to ba$（$a,b\in\Sigma$）。
• $\varepsilon\in L(M)$ のときに限り $S\to\varepsilon$。
  どの規則も、左右の文脈（隣の高々一記号）を変えずに一つの変数記号を空でない文字列に書き換えるもので、$S$ はどの規則の右辺にも現れないので、$G=(V,\Sigma,R,S)$ は文脈依存文法である。
  （記号列による様相の表示）$x=a_1\cdots a_n$（$n\ge1$）と様相 $c=(q,X_1\cdots X_n,i)$ に対し、$\mathrm{enc}(x,c)$ を、$j$ 番目が $\langle a_j,X_j,h_j,([j=1],[j=n])\rangle$ である長さ $n$ の文字列とする。ここで $[\,\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})$、それ以外は $-$ とする。
  （終端記号を含まない文字列の形）$S$ から導出され終端記号を含まない文字列は、次のいずれかであることを導出の長さに関する帰納法で示す：(i) $S$、(ii) $T$ の後にヘッドの印 $-$ の四つ組が並んだ生成途中の文字列、(iii) ある $x$ と $c_0(x)\vdash^{*}c$ となる様相 $c$ についての $\mathrm{enc}(x,c)$、(iv) そのような $c$ から一歩 $c\vdash c'$ でヘッドが隣のマスへ移る途中の文字列（$\mathrm{enc}(x,c)$ のヘッドのマスを $\mathrm{R}$ または $\mathrm{L}$ の印で書き換えたもの、さらに隣のマスに $\mathrm{R}'$ または $\mathrm{L}'$ の印を付けたもの、さらに元のマスの印を $-$ にしたもの、の三段階）。
  (i)、(ii) に適用できるのは生成の規則だけで、結果は (ii) か、規則 $T\to\langle a,a,(q_0,\mathrm{l}),(1,0)\rangle$ または $S\to\langle a,a,(q_0,\mathrm{l}),(1,1)\rangle$ により $\mathrm{enc}(x,c_0(x))$ になる。(iii) の文字列には、ヘッドの印が $-$ でない四つ組がちょうど一つあり、その種類は $\mathrm{o},\mathrm{l},\mathrm{r}$ のどれかである。生成の規則と、終端記号を左辺に含む規則は適用できない。移動の規則は $\mathrm{R},\mathrm{L},\mathrm{R}',\mathrm{L}'$ の印を要するので適用できない。遷移の規則は、ヘッドの下の記号を読む $M$ の遷移に対応するものだけが適用でき、端の印の上への移動や端の印からの移動の場合は結果が $\mathrm{enc}(x,c')$（$c\vdash c'$）であり、隣のマスへの移動の場合は結果が (iv) の第一段階である。四つ組の $e$ により、最後のマスからの右への遷移は右端の印への移動に、それ以外は隣のマスへの移動になる（左も同様）。受理の規則 $\langle a,X,(f,\kappa),e\rangle\to a$ は $c$ の状態が $F$ に属するときにだけ適用でき、終端記号を生じる。(iv) では、各段階で適用できる規則は次の段階へ進む一つだけである。たとえば右への移動の第一段階 $\ldots\langle a,Y,(p,\mathrm{R}),e\rangle\langle b,Z,-,e'\rangle\ldots$ では、ヘッドの印が $-$ でない四つ組は $(p,\mathrm{R})$ の一つだけであり、適用できるのは右への移動の最初の規則だけである（二番目の規則は右隣に $\mathrm{R}'$ の印を、三番目の規則は $\mathrm{R}'$ の印そのものを要する）。第二段階では $(p,\mathrm{R})$ の右隣が $-$ でないので最初の規則は適用できず、三番目の規則も左隣が $-$ でないので適用できない。第三段階では三番目の規則だけが適用でき、結果は $\mathrm{enc}(x,c')$ である。左も同様である。
  （$L(G)\subset L(M)$）$x\ne\varepsilon$ で $S\Rightarrow^{*}x$ とする。この導出で終端記号を含まない最後の文字列を $\zeta$ とする。$\zeta$ の次の一歩で初めて終端記号が現れるので、上により $\zeta=\mathrm{enc}(x',c)$（$c_0(x')\vdash^{*}c$、$c$ の状態は $F$ に属する）であり、その一歩は受理の規則 $\langle a,X,(f,\kappa),e\rangle\to a$ による。以後の文字列には $S,T$ は現れず、どの規則も、四つ組をその第一成分と同じ終端記号に替えるか、四つ組の第一成分を変えずに書き換えるかなので、各四つ組を第一成分に、終端記号をそれ自身に写す写像を文字ごとに施した文字列は変わらない。$\zeta$ ではそれが $x'$、最後の $x$ ではそれが $x$ なので $x=x'$ であり、$x\in L(M)$ である。$\varepsilon$ については、$S\to\varepsilon$ 以外の規則は長さを減らさないので、$\varepsilon\in L(G)$ は $S\to\varepsilon\in R$、すなわち $\varepsilon\in L(M)$ と同値である。
  （$L(M)\subset L(G)$）$x=a_1\cdots a_n\in L(M)$、$n\ge1$ とし、受理に至る計算 $c_0(x)=c_0\vdash c_1\vdash\cdots\vdash c_s$（$c_s$ の状態は $F$ に属する）をとる。生成の規則で $S\Rightarrow^{*}\mathrm{enc}(x,c_0)$ とし、各一歩 $c_{l}\vdash c_{l+1}$ を遷移の規則（と、必要なら移動の三つの規則）でなぞって $\mathrm{enc}(x,c_s)$ を得る。ヘッドのあるマスを受理の規則で $a_i$ に替えると、ほかのマスの印はすべて $-$ なので、規則 $a\langle b,Z,-,e\rangle\to ab$ と $\langle b,Z,-,e\rangle a\to ba$ で右へ左へと順に終端記号に替えられ、$x$ に至る。

1 から 2：文脈依存文法は非収縮文法である（文脈依存言語 の記事の命題「規則の非減少性」）。2 から 3：prop-lba-from-grammar。3 から 1：prop-lba-to-grammar。