交代有限オートマトン

オートマトン理論において、交代有限オートマトン（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}}$

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

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

よく使われる代替モデルは、ブール結合が選言正規形で表されるモデルです。例えば、は を表します。この場合、状態tt (真) は で表され、 ff (偽) は で表されます。この表現は通常、より効率的です。 ${\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}。

参考文献

1. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). 「交代」. Journal of the ACM . 28 (1): 114– 133. doi : 10.1145/322234.322243 . ISSN  0004-5411.
2. Fellah, A.; Jürgensen, H.; Yu, S. (1990). 「交代有限オートマトン∗の構築」. International Journal of Computer Mathematics . 35 ( 1–4 ): 117– 132. doi :10.1080/00207169008803893. ISSN  0020-7160.
3. の定理19 、クトリブ（マーティン）（2011年3月1日）「有限オートマトンにおける記述的および計算的複雑さ—概観」『情報と計算』209 (3): 456– 470. doi :10.1016/j.ic.2010.11.013. ISSN  0890-5401.

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Alternating_finite_automaton&oldid=1285525356"