交代有限オートマトン

オートマトン理論において、交代有限オートマトン( AFA ) は、遷移が存在遷移と普遍遷移に分けられる非決定性有限オートマトンです。たとえば、A を交代オートマトンとします。

• 存在遷移の場合、A はを読み取り、非決定的に状態をまたはに切り替えることを選択します。したがって、 は通常の非決定性有限オートマトンのように動作します。${\displaystyle (q,a,q_{1}\vee q_{2})}$${\displaystyle q_{1}}$${\displaystyle q_{2}}$
• 普遍的な遷移 の場合、A はおよびに移動し、を読み取り、並列マシンの動作をシミュレートします。${\displaystyle (q,a,q_{1}\wedge q_{2})}$${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$

全称量化により、実行は実行木によって表されることに注意してください。w上に実行木が存在し、すべてのパスが受け入れ状態で終了する 場合、 A は単語w を受け入れます。

基本的な定理によれば、任意の AFA は決定性有限オートマトン(DFA) と同等であり、したがって AFA は正規言語を正確に受け入れます。

頻繁に使用される代替モデルは、ブール結合が選言正規形であるモデルであり、たとえば はを表します。この場合、状態tt ( true ) は で表され、 ff ( false ) は で表されます。通常、この表現の方が効率的です。 ${\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}$${\displaystyle q_{1}\vee (q_{2}\wedge q_{3})}$${\displaystyle \{\emptyset \}}$${\displaystyle \emptyset }$

交代有限オートマトンを拡張して、木オートマトンと同じ方法で木を受け入れるようにすることができ、交代木オートマトンが生成されます。

交代有限オートマトン（AFA）は、5組、、、 である。 ${\displaystyle (Q,\Sigma ,q_{0},F,\delta )}$

• ${\displaystyle Q}$有限の状態集合である。
• ${\displaystyle \Sigma }$入力シンボルの有限集合である。
• ${\displaystyle q_{0}\in Q}$初期（開始）状態です。
• ${\displaystyle F\subseteq Q}$受け入れ（最終）状態の集合です。
• ${\displaystyle \delta \colon Q\times \Sigma \times \{0,1\}^{Q}\to \{0,1\}}$遷移関数です。

各文字列に対して、長さに関する帰納法によって受容関数を定義します。 ${\displaystyle w\in \Sigma ^{*}}$${\displaystyle A_{w}\colon Q\to \{0,1\}}$${\displaystyle w}$

• ${\displaystyle A_{\epsilon }(q)=1}$の場合、それ以外の場合;${\displaystyle q\in F}$${\displaystyle A_{\epsilon }(q)=0}$
• ${\displaystyle A_{aw}(q)=\delta (q,a,A_{w})}$。

オートマトンは、 の場合にのみ文字列を受け入れます。 ${\displaystyle w\in \Sigma ^{*}}$${\displaystyle A_{w}(q_{0})=1}$

このモデルはチャンドラ、コーゼン、ストックマイヤーによって導入されました。^[1]

AFA は正規言語を正確に受け入れることができますが、状態の数で測定される記述の簡潔さにおいて他のタイプの有限オートマトンとは異なります。

Chandraら^[1]は、状態AFAを同等のDFAに変換するには最悪の場合状態が必要であることを証明したが、逆言語のDFAは状態のみで構築できる。Fellah、Jürgensen、Yuによる別の構築^[2]は、NFAからDFAへの変換に使用されるのと同様の種類のべき集合構築を実行することで、状態を持つAFAを最大状態を持つ非決定性有限オートマトン(NFA)に変換している。 ${\displaystyle n}$${\displaystyle 2^{2^{n}}}$${\displaystyle 2^{n}}$${\displaystyle n}$${\displaystyle 2^{n}}$

メンバーシップ問題とは、AFAと単語が与えられた場合、がを受け入れるかどうかを問う問題である。この問題はP完全である。^{[3]これはシングルトンアルファベット、つまりオートマトンが}単項言語を受け入れる場合でも当てはまる。 ${\displaystyle A}$ ${\displaystyle w}$${\displaystyle A}$${\displaystyle w}$

非空性問題（入力AFAの言語は空でないか？）、普遍性問題（入力AFAの言語の補語は空か？）、同値問題（2つの入力AFAは同じ言語を認識するか）は、AFAに対してPSPACE完全である^{[3] ：定理23、24、25}。

• ピッペンガー、ニコラス（1997）。計算可能性の理論。ケンブリッジ大学出版局。ISBN 978-0-521-55380-3。