線形有界オートマトン

同義語：linear bounded automaton線形拘束オートマトンLBA

概要

前提知識: Turing機械, 文脈依存言語, 句構造言語, 数学的帰納法

Turing機械は無制限に長いテープを使える。線形有界オートマトン（linear bounded automaton; LBA）は、テープのうち入力が書かれた範囲だけしか使えないように制限した非決定性の Turing 機械である。入力の両端には印が置かれ、ヘッドはその外に出られないが、範囲の中では何度でも往復して読み書きできる。記憶の量は入力の長さで抑えられるが、使い方には制限がない。この点で、記憶量に上限がないが使い方が後入れ先出しに限られるプッシュダウンオートマトンと対照的である。
この記事の中心の結果は、線形有界オートマトンで受理できる言語がちょうど文脈依存言語であり、さらに規則が文字列を縮めない文法（非収縮文法）で生成できる言語とも一致するという定理（thm-lba-csl）である。証明は黒田の定理(形式言語) にある。文法から機械を作る向きでは導出を一歩ずつ推測してテープの上で書き換え、機械から文法を作る向きではテープの各マスを一つの変数記号で表して機械の一歩を規則でなぞる。あわせて、線形有界オートマトンの受理する言語では所属が判定できることを示す。

定義

以下、$\Sigma$ はアルファベット（形式言語）、$\Sigma^{*}$ はその上の文字列全体、$\varepsilon$ は空語、$|x|$ は文字列 $x$ の長さを表す。$\triangleright,\triangleleft$ は左端と右端の印を表す記号で、以下に現れるどのアルファベットにも属さないとする。

線形有界オートマトン

線形有界オートマトンとは、$6$ つ組 $M=(Q,\Sigma,\Gamma,\delta,q_0,F)$ であって次を満たすものをいう。

$Q$ は空でない有限集合（状態の集合）、$q_0\in Q$（初期状態）、$F\subset Q$（受理状態の集合）
$\Gamma$ は $\Sigma$ を含む有限集合（テープ記号の集合）。$\hat\Gamma:=\Gamma\cup\{\triangleright,\triangleleft\}$ とおく。
$\delta$ は $Q\times\hat\Gamma\times Q\times\hat\Gamma\times\{-1,+1\}$ の有限部分集合（遷移の集合）で、各 $(q,X,p,Y,d)\in\delta$ は次を満たす：$X=\triangleright$ なら $Y=\triangleright$ かつ $d=+1$、$X=\triangleleft$ なら $Y=\triangleleft$ かつ $d=-1$、$X\in\Gamma$ なら $Y\in\Gamma$。
遷移 $(q,X,p,Y,d)$ は「状態 $q$ でヘッドの下の記号が $X$ なら、そこに $Y$ を書き、ヘッドを $d$ の向き（$-1$ は左、$+1$ は右）に一マス動かし、状態 $p$ に移る」ことを表す。条件により、端の印は書き換えられず、ヘッドは印の外に出ない。

様相・計算・受理

$M=(Q,\Sigma,\Gamma,\delta,q_0,F)$ を線形有界オートマトン、$x=a_1\cdots a_n\in\Sigma^{*}$ を入力とする。テープは $0$ 番目から $n+1$ 番目までのマスからなり、$0$ 番目に $\triangleright$、$n+1$ 番目に $\triangleleft$ があり、間の $n$ マスの内容は $\Gamma^{n}$ の元である。

$q\in Q$、$y=X_1\cdots X_n\in\Gamma^{n}$、$0\le i\le n+1$ の組 $(q,y,i)$ を（入力の長さ $n$ の）様相という。ヘッドの下の記号を、$i=0$ なら $\triangleright$、$i=n+1$ なら $\triangleleft$、それ以外なら $X_i$ とし、$\mathrm{sym}(y,i)$ と書く。
$(q,\mathrm{sym}(y,i),p,Y,d)\in\delta$ のとき $(q,y,i)\vdash(p,y',i+d)$ と書く（一歩）。ここで $y'$ は、$1\le i\le n$ なら $y$ の $i$ 番目を $Y$ に替えたもの、$i\in\{0,n+1\}$ なら $y$ そのものである。遷移の条件から $0\le i+d\le n+1$ である。$\vdash$ を有限回（$0$ 回を含む）続けた関係を $\vdash^{*}$ と書く。
$c_0(x):=(q_0,x,0)$ を $x$ の初期様相という。ある様相 $(f,y,i)$（$f\in F$）について $c_0(x)\vdash^{*}(f,y,i)$ となるとき、$M$ は $x$ を受理するという。$M$ が受理する文字列全体を $L(M)$ と書く。
一つの様相から適用できる遷移が複数あってもよく、受理は「受理状態に至る計算が少なくとも一つある」という意味である。どの $(q,X)$ についても $(q,X,p,Y,d)\in\delta$ となる $(p,Y,d)$ が高々一つのとき、$M$ は決定性であるという。

非収縮文法

句構造言語の記事の定義「句構造文法」の意味の文法 $G=(V,\Sigma,R,S)$ で、各規則 $\alpha\to\beta$ が $|\alpha|\le|\beta|$ を満たすもの（例外として、$S$ がどの規則の右辺にも現れないときに限り $S\to\varepsilon$ を許す）を非収縮文法という。これは文脈依存言語の記事の定義「非収縮文法」と同じものである。

定義の流儀

テープの長さを入力の長さの定数倍まで許す流儀もあり、「線形有界」という名称はこちらに由来する。長さ $kn$ のテープは、$k$ 個の記号の組を一つのテープ記号とし、組の中のどの位置にヘッドがあるかを状態に記録すれば、長さ $n$ のテープで模倣できる。したがって受理できる言語のクラスは変わらない。端の印を置かず、端から外に出ようとする動きではヘッドがその場に留まるとする流儀もある。

直感

線形有界オートマトンは「入力の書かれた紙の上でだけ計算してよい」機械である。紙を何度も読み返し、印を付けたり消したりはできるが、新しい紙は使えない。それでも、記号に印を付けながら往復すれば、$a,b,c$ の個数を一つずつ照合したり（ex-lba-anbncn）、文字列を半分ずつに減らしたり（ex-lba-powers-of-two）できる。
文脈依存文法との対応の鍵は、文脈依存文法（より一般に非収縮文法）の規則が文字列を縮めないことである（文脈依存言語の記事の命題「規則の非減少性」）。長さ $n$ の文字列の導出の途中に現れる文字列はどれも長さ $n$ 以下なので、導出をテープの上で一歩ずつなぞっても入力の範囲からはみ出さない。逆に、機械の様相はテープの内容・ヘッドの位置・状態からなり、その長さは入力の長さで決まっている。そこで様相を同じ長さの文字列として表し、機械の一歩を、隣り合う記号だけを見て一記号を書き換える文脈依存文法の規則でなぞることができる。

例

三つの部分の個数が等しい文字列

$\{a^{n}b^{n}c^{n}\mid n\ge1\}$ は次の線形有界オートマトンで受理できる。まず左端から右端まで一度走査し、入力が $a^{+}b^{+}c^{+}$ の形でなければ止まる。次に、左端から右へ進んで印の付いていない最初の $a$ に印を付け、続けて印の付いていない最初の $b$、最初の $c$ に印を付けて左端に戻る、という一巡を繰り返す（テープ記号に印付きの $\dot a,\dot b,\dot c$ を加える）。一巡の途中で探す記号が見つからなければ止まる。印の付いていない $a$ がなくなった時点で、印の付いていない $b,c$ も残っていなければ受理する。一巡ごとに $a,b,c$ の印のない個数がそれぞれ一つずつ減るので、受理されるのは三つの個数が等しいときに限る。この言語は文脈自由言語ではない（文脈自由言語の記事の命題「三つの部分の個数が等しい文字列は文脈自由でない」。引用先は $n\in\mathbb{N}$ の言語を扱うが、空語を除いても、文脈自由言語のクラスが和について閉じていることから同じことが従う）。

2 の冪乗の長さの文字列

$\Sigma=\{a\}$ 上の言語 $\{a^{2^{k}}\mid k\in\mathbb{N}\}$ は次の線形有界オートマトンで受理できる。テープ記号に $\bar a$（消した $a$）を加える。左端から右端まで一回走査するあいだに、消されていない $a$ を左から数えて偶数番目のものをすべて $\bar a$ に替える。数えるのは偶奇だけでよいので状態で覚えられ、同時に「消されていない $a$ が $1$ 個だけだったか」も状態で覚えられる。右端に着いたとき、走査の前に消されていない $a$ が $1$ 個だけなら受理し、奇数個（$3$ 個以上）または $0$ 個なら止まり、$2$ 以上の偶数個なら左端に戻って同じ走査を繰り返す。走査の前の個数が偶数 $m$ なら走査の後は $m/2$ 個になるので、入力の長さ $n\ge1$ について受理されるのは、$n$ を $2$ で割り続けて奇数に出会うまでの最後の値が $1$ のとき、すなわち $n$ が $2$ の冪乗のときに限る。

同じ文字列の繰り返し

$\{ww\mid w\in\{a,b\}^{+}\}$ は、まず中央の位置を推測して印を付け（非決定性を使う。決定性の機械でも、両端から一つずつ印を付けて中央を求められる）、前半の $i$ 番目と後半の $i$ 番目を一つずつ印を付けながら照合する機械で受理できる。この言語は文脈自由言語ではない（文脈自由言語の記事の反例「三つの部分の個数が等しい文字列」の後半。空語を除いても、文脈自由言語のクラスが和について閉じていることから同じことが従う）。

反例：テープの範囲を外に広げる機械

入力の範囲の外のマスも使ってよいとすると、その機械は決定性の Turing機械も特別な場合として含むので、すべての句構造言語が受理できるようになる（句構造言語の記事の定理「Turing 機械との同値性」）。そこには所属が判定できない言語が含まれる（ex-lba-counterexamples）。したがってその機械は「受理する言語の所属が判定できる」という性質（prop-lba-decidable）を満たさない。テープの範囲の制限は、線形有界オートマトンの本質的な仮定である。

性質

所属の判定

所属問題の決定可能性

線形有界オートマトン $M$ と入力 $x$ が与えられたとき、$x\in L(M)$ かどうかは有限の手続きで判定できる。

$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)$ から到達できる頂点の集合を辺をたどって順に拡げていく（既に加えた頂点は再訪しない）ことで、有限回の操作で計算できる。

この判定は、機械が止まらない計算（同じ様相を繰り返すもの）を持っていても通用する。様相の個数が有限なので、ある様相を二度通る計算は受理の判定に不要だからである。一方、作業領域に制限のない Turing 機械では様相が無限にあり、この議論は成り立たない。

文法と機械の対応

非収縮文法 $G$ からは $L(M)=L(G)$ となる線形有界オートマトン $M$ が作れ、線形有界オートマトン $M$ からは $L(G)=L(M)$ となる文脈依存文法 $G$ が作れる（黒田の定理(形式言語) の命題「非収縮文法から機械へ」「機械から黒田標準形と文脈依存文法へ」）。前者では、各マスを上段に入力の記号、下段に作業用の記号を置いた二段のマスとし、下段で導出を一歩ずつ推測して書き換える。非収縮文法の導出の途中の文字列は最後の文字列より長くならないので、空き記号で埋めて入力の範囲に収まる。後者では、テープの各マスを一つの変数記号で表し、機械の一歩を隣り合う記号の書き換えでなぞる。

文脈依存文法との同値

文脈依存言語との同値性

$\Sigma$ 上の言語 $L$ について、次は同値である。

$L$ は文脈依存言語である。
$L$ はある非収縮文法で生成される。
ある線形有界オートマトン $M$ について $L=L(M)$ である。

1 から 2：文脈依存文法は非収縮文法である（文脈依存言語の記事の命題「規則の非減少性」）。
2 から 3：黒田の定理(形式言語) の命題「非収縮文法から機械へ」。
3 から 1：黒田の定理(形式言語) の命題「機械から黒田標準形と文脈依存文法へ」。

この定理は文脈依存言語の記事の定理「線形有界オートマトンとの同値性」と同じ主張であり、1 と 2 の同値と、規則を黒田標準形に限っても同じクラスになることは黒田の定理(形式言語) にまとめてある。非収縮文法から作った機械を経由して文脈依存文法に戻ることで、非収縮文法の規則（たとえば二つの変数記号を入れ替える $CB\to BC$）を文脈依存文法の規則に直す一般的な方法が得られる（黒田の定理(形式言語)）。prop-lba-decidable と合わせると、文脈依存言語の所属が判定できることも再び得られる。

仮定を外したときの反例

外す条件	反例	成り立たなくなること
ヘッドが入力の範囲（両端の印の間）に留まる	入力の外のテープも使う Turing 機械で、所属が判定できない言語を受理するもの	所属の判定（prop-lba-decidable）
状態の集合と遷移の集合が有限	状態を $\Sigma^{*}$ で添字づけた「機械」	受理する言語が文脈依存言語であること（thm-lba-csl）：任意の言語が受理できる
テープ記号の集合と遷移の集合が有限	テープ記号に $[v]$（$v\in\Sigma^{*}$）を加えた「機械」	受理する言語が文脈依存言語であること（thm-lba-csl）：任意の言語が受理できる

反例の確かめ

1 行目：Turing 機械の符号 $\langle M\rangle$ と入力 $w$ の組で「$M$ が $w$ を受理する」ものの全体 $A_{\mathrm{TM}}$ は、Turing 機械で受理できる（MSm24 Theorem 5.4.4、p. 177）が、すべての入力で停止する Turing 機械で判定することはできない（MSm24 Theorem 5.1.6、p. 162）。この記事では証明しない。$A_{\mathrm{TM}}$ を受理する線形有界オートマトンがあれば prop-lba-decidable により所属が判定できてしまうので、$A_{\mathrm{TM}}$ を受理する機械は入力の範囲の外を使う必要がある。そのような機械では様相が無限にありうるので、prop-lba-decidable の議論は成り立たない。
2 行目：任意の言語 $L\subset\Sigma^{*}$ に対し、状態の集合を $\Sigma^{*}\cup\{q_{\mathrm{acc}}\}$、初期状態を $\varepsilon$ とし、遷移を「状態 $v$ で $a\in\Sigma$ を読めば状態 $va$ に移って右へ進む」「状態 $v\in L$ で右端の印を読めば $q_{\mathrm{acc}}$ に移る」（左端の印からは右へ進むだけ）、受理状態を $q_{\mathrm{acc}}$ とすると、受理されるのはちょうど $L$ の元である。言語は非可算個あり（形式言語の記事の命題「言語の個数」）、文脈依存言語は可算個しかない（句構造言語の記事の命題「句構造言語の個数」）ので、文脈依存でない言語も受理される。
3 行目：状態は有限個のまま、テープ記号の集合を $\Sigma\cup\bar\Sigma\cup\{[v]\mid v\in\Sigma^{*}\}$ に広げる（$\bar\Sigma$ は印を付けた記号、$[v]$ は文字列 $v$ を表す一つの記号）。最初のマスの $a_1$ を $[a_1]$ に替え、以後、印のない最も左の記号 $a$ を $\bar a$ に替え、$a$ を状態に覚えて最初のマスまで戻り、そこの $[v]$ を $[va]$ に替える、という操作を繰り返す。印のない記号がなくなったら最初のマスに戻り、その記号 $[v]$ について $v\in L$ なら受理状態に移る（空語は、左端の印の直後が右端の印かどうかで別に扱う）。$\Sigma$ は有限なので状態は有限個で済み、遷移は無限個になる。最初のマスには最後に $[x]$ が書かれるので、受理されるのはちょうど $L$ の元である。

2 行目と 3 行目の「機械」は遷移が無限個あり、有限個のデータでは書けない。遷移の集合を有限に保ったまま状態やテープ記号の集合だけを無限にしても、遷移に現れる状態と記号は有限個なので、受理する言語は変わらない。線形有界オートマトンの限界は、有限の制御と、作業領域が入力の長さで抑えられることの両方から来ている。

補足

決定性と LBA 問題

決定性の線形有界オートマトンで受理できる言語のクラスが、非決定性の線形有界オートマトンで受理できる言語のクラス（文脈依存言語のクラス）と一致するかどうかは LBA 問題と呼ばれ、未解決である（文脈依存言語の記事の注意「線形有界オートマトンとの同値性の証明の所在」）。これに対し、文脈依存言語のクラスが補集合について閉じていることは示されている（文脈依存言語の記事の定理「閉包性」とその注意）。prop-lba-decidable の判定は様相のグラフ全体をたどるので、記憶量は入力の長さについて指数的に増え、それ自身は線形有界オートマトンによる判定ではない。

階層における位置

線形有界オートマトンは Chomsky階層のタイプ 1、すなわち文脈依存言語に対応する計算モデルである。入力を左から一度読むだけの機械、記憶を一本のスタックに限った機械、作業領域に制限のない機械が、それぞれ有限オートマトン（正規言語）、プッシュダウンオートマトン（文脈自由言語）、Turing機械（句構造言語）である。文脈依存言語のクラスは、所属の判定できる言語のクラスに真に含まれる（Chomsky階層の記事の定理「階層定理」）。