双方向有限オートマトン

コンピュータサイエンス、特にオートマトン理論において、双方向有限オートマトンとは、入力を再読み込みできる 有限オートマトンを指します。

双方向決定性有限オートマトン( 2DFA ) は抽象マシンであり、すでに処理された文字を再訪できる決定性有限オートマトン(DFA)の一般化バージョンです。DFA と同様に、現在の文字に基づいて状態間の遷移を伴う有限数の状態がありますが、各遷移には、マシンが入力内の位置を左、右、または同じ位置に留まるかどうかを示す値もラベル付けされます。同様に、2DFA は、作業テープがなく、読み取り専用の入力テープのみを持つ 読み取り専用チューリングマシンと見なすことができます。

2DFAは1959年の画期的な論文でラビンとスコットによって導入され、^[1]一方向DFAと同等の能力を持つことが証明されました。つまり、 2DFAで認識できる形式言語はどれも、各文字を順番に調べて消費するだけのDFAで認識できます。DFAは明らかに2DFAの特殊なケースなので、これは両方の種類のマシンが正確に正規言語のクラスを認識することを意味します。しかし、2DFAと同等のDFAは指数関数的に多くの状態を必要とする可能性があるため、2DFAはいくつかの一般的な問題のアルゴリズムのより実用的な表現になります。

2DFA は、積構造 (作業テープ状態と制御状態の各組み合わせの状態) を介して有限制御状態に任意の一定量の情報を組み込むことができるため、作業テープ上で一定量のスペースのみを使用する読み取り専用チューリング マシンと同等です。

形式的には、双方向決定性有限オートマトンは次の8組で記述できる。ここで ${\displaystyle M=(Q,\Sigma,L,R,\delta,s,t,r)}$

• ${\displaystyle Q}$有限で空でない状態の集合である
• ${\displaystyle \Sigma }$入力シンボルの有限かつ空でない集合である
• ${\displaystyle L}$左のエンドマーカーです
• ${\displaystyle R}$正しいエンドマーカーです
• ${\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{\mathrm {left,right} \}}$
• ${\displaystyle s}$開始状態です
• ${\displaystyle t}$最終状態です
• ${\displaystyle r}$拒否状態です

さらに、次の 2 つの条件も満たす必要があります。

• 全ての${\displaystyle q\in Q}$

${\displaystyle \delta (q,L)=(q^{\prime },\mathrm {right} )}$一部の人にとって${\displaystyle q^{\prime }\in Q}$

${\displaystyle \delta (q,R)=(q^{\prime },\mathrm {left} )}$一部の人にとって${\displaystyle q^{\prime }\in Q}$

ポインタが入力ワードのいずれかの端に到達したときに、何らかの遷移が可能になるはずだと書かれています。

• すべてのシンボルについて^{[説明が必要]}${\displaystyle \sigma \in \Sigma \cup \{L\}}$

${\displaystyle \delta (t,\sigma )=(t,R)}$

${\displaystyle \delta (r,\sigma )=(r,R)}$

${\displaystyle \delta (t,R)=(t,L)}$

${\displaystyle \delta (r,R)=(r,L)}$

オートマトンは一度受け入れまたは拒否の状態に達すると、永遠にそこに留まり、ポインタは右端のシンボルに移動し、そこで無限に循環すると言われています。^[2]

双方向非決定性有限オートマトン（2NFA）は、同じ構成で複数の遷移が定義される場合があります。その遷移関数は

• ${\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow 2^{Q\times \{\mathrm {left,right} \}}}$。

標準的な一方向NFAと同様に、2NFA は、可能な計算の少なくとも 1 つが受け入れ可能な場合に文字列を受け入れます。2DFA と同様に、2NFA も通常の言語のみを受け入れます。

双方向交代有限オートマトン（2AFA）は、交代有限オートマトン（AFA）の双方向拡張である。その状態集合は

• ${\displaystyle Q=Q_{\exists }\cup Q_{\forall }}$どこ。${\displaystyle Q_{\exists }\cap Q_{\forall }=\emptyset }$

および の状態はそれぞれ存在的および普遍的と呼ばれます。存在的状態では、2AFA は NFA のように非決定的に次の状態を選択し、結果として得られる計算の少なくとも 1 つが受け入れる場合に受け入れます。普遍的状態では、2AFA はすべての状態に移動し、結果として得られる計算がすべて受け入れる場合に受け入れます。 ${\displaystyle Q_{\exists}}$${\displaystyle Q_{\forall}}$

双方向および一方向の有限オートマトン、決定性および非決定性および交互のオートマトンは同じクラスの正規言語を受け入れます。ただし、あるタイプのオートマトンを別のタイプの同等のオートマトンに変換すると、状態数が爆発的に増加します。Christos Kapoutsis ^{[3] は}、状態 2DFA を同等の DFA に変換するには、最悪の場合でも状態が必要であることを明らかにしました。状態 2DFA または 2NFA を NFA に変換する場合、必要な状態の最悪数は です。Ladner 、Lipton、およびStockmeyer ^{[4] は}、状態 2AFA を状態を持つ DFA に変換できることを証明しました。2AFA から NFA への変換には、最悪の場合でも状態が必要になります。Geffertおよび Okhotin ^[5]を参照してください。${\displaystyle n}$${\displaystyle n(n^{n}-(n-1)^{n})}$${\displaystyle n}$${\displaystyle {\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)}$${\displaystyle n}$${\displaystyle 2^{n2^{n}}}$${\displaystyle 2^{\Theta (n\log n)}}$

コンピュータサイエンスにおける未解決の問題:

すべての- 状態 2NFA には同等の- 状態 2DFA がありますか?${\displaystyle n}$${\displaystyle \operatorname {poly} (n)}$

(コンピュータサイエンスにおける未解決の問題)

あらゆる2NFAが状態数の多項式増加のみで2DFAに変換できるかどうかは未解決の問題である。この問題はSakodaとSipser ^[6]によって提起され、 彼らはこれを計算複雑性理論におけるP対NP問題と比較した。BermanとLingas ^{[7]はこの問題と}L対NL未解決問題の間に正式な関係を発見した。正確な関係については Kapoutsis ^{[8]を参照のこと。}

スイープオートマトンとは、特殊な種類の2DFAで、左から右、右から左へのスイープを交互に実行して入力文字列を処理し、エンドマーカーでのみ方向転換する。Sipser ^[9]は、それぞれn状態のNFAによって受け入れられるが、状態数が少ないスイープオートマトンでは受け入れられない言語のシーケンスを構築した。 ${\displaystyle 2^{n}}$

2DFAの概念は、1997年にジョン・ワトラスの「2方向量子有限状態オートマトンの効果について」によって量子コンピューティングに一般化され、これらのマシンが非正規言語を認識できるため、DFAよりも強力であることが実証されました。 ^[10]

入力テープ上でどちらの方向にも移動できるプッシュダウンオートマトンを双方向プッシュダウンオートマトン（2PDA）と呼びます。[ 11 ]これはハートマニス、ルイス、スターンズ（1965）によって研究されました。[12] アホ、ホップクロフト、ウルマン（1968）[13] クック（1971）[14] は決定性（2DPDA）^および 非^決定 性^（ 2NPDA ^）双方向プッシュダウンオートマトンによって認識可能な言語のクラスを特徴付けました。グレイ、ハリソン、イバラ（1967）はこれらの言語の閉包特性を調査しました。^[15]