2-way 決定性有限オートマトン[2DFA]

直感的な説明をすると, 入力文字列を2方向に走査できるオートマトン。通常のオートマトンでは, キャラクタを受け取るとそのキャラクタと, 現在の状態から次の状態を決定する。その流れは2DFAでも同様に行われるが, 2DFAでは入力として与えられるキャラクタに, アルファベットの他, 方向付きの終端記号が含まれる。あたえられた文字列ををテープ, 今ちょうど読んでいるキャラクタが, テープ中のヘッドが指している部分に記されている図をイメージする。初めヘッドはテープの左端からスタートし1文字づつ右側へと進んでいく。終端器号 $\dashv$ に到達すると, ヘッドは進む向きを反転させ, テープ左端へと向かい始める。左側にも同様の終端器号 $\vdash$ が存在し, ここに到達すればヘッドは再び右側へと進み始める。形式的な定義は次のように与えられる。

定義

2DFA Mは次の8つ組で与えられる.

$(Q, \Sigma , \vdash , \dashv , \delta , s , t , r)$

where

$Q$ は状態の有限集合
$\Sigma$ は入力文字の有限集合(アルファベット)
$\vdash,\dashv$ はそれぞれ左終端器号,右終端器号( $\vdash,\dashv\not\in\Sigma$ )
$\delta : Q\times\{\Sigma\cup\{\vdash,\dashv \}\}\rightarrow Q\times\{L,R\}$ は遷移関数(L,Rはそれぞれヘッドが次に左に進むか右に進むかを表す)
$s, t, r \in Q$ はそれぞれ初期状態, 受理状態, リジェクト状態を表す

また遷移関数は次の条件を満たす

任意の $q\in Q$ について
$\delta(q,\vdash) = (u, R) for some u\in Q$
$\delta(q,\dashv) = (v, L) for some v\in Q$
任意の $b\in\Sigma\cup\{\vdash\}$ について
$\delta(t, b) = (t, R),\ \delta(r, b) = (r, R)$
$\delta(t, \dashv) = (t, L)\ \delta(r, \dashv) = (r, L)$