オートマトン理論

オートマトンの種類

オートマトン理論は、抽象機械とオートマトン、およびそれらを使用して解決できる計算上の問題を研究する分野です。これは、数学的論理と密接な関係のある理論計算機科学の理論です。オートマトンという言葉は、ギリシャ語のαὐτόματοςに由来し、「自動動作、自己意志、自動移動」を意味します。オートマトン(複数形は automata) は、事前に決定された一連の操作に自動的に従う抽象的な自己推進型計算装置です。有限の数の状態を持つオートマトンを有限オートマトン (FA) または有限状態マシン(FSM) と呼びます。右の図は、よく知られているタイプのオートマトンである有限状態マシンを示しています。このオートマトンには、状態(図では円で表されます) と遷移(矢印で表されます) が含まれます。オートマトンは入力シンボルを見ると、遷移関数に従って別の状態に遷移（またはジャンプ）します。遷移関数は、前の状態と現在の入力シンボルを引数として受け取ります。

オートマトン理論は形式言語理論と密接に関連しています。この文脈では、オートマトンが、無限である可能性のある形式言語の有限表現として使用されます。オートマトンは通常、オートマトンの主要なクラス間の入れ子関係を説明するチョムスキー階層のように、認識できる形式言語のクラスによって分類されます。オートマトンが、計算、コンパイラ構築、人工知能、構文解析、形式検証の理論で重要な役割を果たします。

抽象オートマトン理論は、有限オートマトンとの関連で20世紀半ばに開発されました。^{[1]オートマトン理論は当初、}離散パラメータシステムの挙動を研究する数学システム理論の一分野と考えられていました。オートマトン理論の初期の取り組みは、微分積分を使って物質システムを記述するのではなく、抽象代数を使って情報システムを記述するという点で、それ以前のシステム研究とは異なっていました。^[2]有限状態トランスデューサの理論は、さまざまな研究コミュニティによってさまざまな名前で開発されました。^[3]チューリングマシンの初期の概念も、プッシュダウンオートマトンなどの新しい形式の無限状態オートマトンとともにこの分野に含まれていました。

1956年には、クロード・シャノン、W・ロス・アシュビー、ジョン・フォン・ノイマン、マービン・ミンスキー、エドワード・F・ムーア、スティーブン・コール・クリーネなどの科学者による研究を収集した『オートマトン研究』が出版された。^[4]この書籍の出版により、「オートマトン理論は比較的自律的な分野として浮上した」。^[5]この本には、クリーネによる正規イベントの集合、つまり正規言語の説明と、シャノンによるチューリングマシンプログラムの複雑さの比較的安定した尺度が含まれていた。^[6] 同年、ノーム・チョムスキーはオートマトンと形式文法の対応であるチョムスキー階層を説明し、^[7]ロス・アシュビーは基本的な集合論を使用してオートマトンと情報を説明したわかりやすい教科書である『サイバネティクス入門』を出版した。

線形有界オートマトンの研究は、マイヒル・ネローデ定理^[8]につながり、これは形式言語が正規であるための必要十分条件と、その言語の最小マシンの状態数の正確な数を与える。正規言語のポンピング補題も正則性の証明に役立ち、この時期にマイケル・O・ラビンとダナ・スコットによって、決定性有限オートマトンと非決定性有限オートマトンが計算上同等であることが証明された^{[9] 。}

1960年代には、「構造理論」または「代数分解理論」として知られる一連の代数的結果が生まれ、これは相互接続によってより小さな機械から順次機械を実現することを扱った。^{[10]有限オートマトンはすべて}ユニバーサルゲートセットを使用してシミュレートできるが、これにはシミュレート回路に任意の複雑さのループが含まれている必要がある。構造理論は、機械の「ループフリー」実現可能性を扱う。^[5]計算複雑性 の理論も1960年代に形を成した。^{[11] [12]} 10年の終わりまでに、オートマトン理論は「コンピュータサイエンスの純粋数学」と見なされるようになった。^[5]

以下はオートマトンに関する一般的な定義であり、システムのより広い定義を、離散的な時間ステップで動作するシステムに限定し、その状態と入力のみの不変の関数によって各ステップで定義される状態動作と出力を持つ。^[5]

オートマトンとは、離散的な（個々の）時間ステップ（または単にステップ）で一連の入力を与えられると実行されるものです。オートマトンでは、入力アルファベットと呼ばれる一連の記号または文字から選択された 1 つの入力が処理されます。オートマトンが任意のステップで入力として受け取る記号は、単語と呼ばれる一連の記号です。オートマトンには一連の状態があります。オートマトンの実行中、各瞬間に、オートマトンはそのいずれかの状態にあります。オートマトンが新しい入力を受け取ると、前の状態と現在の入力記号をパラメータとする遷移関数に基づいて、別の状態（または遷移）に移動します。同時に、出力関数と呼ばれる別の関数が、これも前の状態と現在の入力記号に従って、出力アルファベットから記号を生成します。オートマトンでは、入力単語の記号を読み取り、単語が完全に読み取られるまで状態を遷移します。単語の長さが有限であれば、単語が完全に読み取られた時点でオートマトンが停止します。オートマトンが停止する状態を最終状態と呼びます。

形式言語理論を使用してオートマトンにおける可能な状態/入力/出力シーケンスを調査するために、マシンに開始状態と一連の受け入れ状態を割り当てることができます。次に、開始状態から開始する実行が受け入れ状態で終了するかどうかに応じて、オートマトンが入力シーケンスを受け入れるか拒否するかを判断することができます。オートマトンによって受け入れられるすべての単語の集合は、オートマトンによって認識される言語と呼ばれます。言語を認識するマシンのよく知られた例は、正しいコードの入力を受け入れたり拒否したりする電子ロックです。

オートマトン

オートマトンは次の5 要素 で形式的に表現できます。 ${\displaystyle M=\langle \Sigma ,\Gamma ,Q,\delta ,\lambda \rangle }$

• ${\displaystyle \Sigma }$は、オートマトンの入力アルファベットと呼ばれる有限の記号集合である。
• ${\displaystyle \ガンマ}$オートマトンの出力アルファベットと呼ばれる別の有限の記号集合である。
• ${\displaystyle Q}$は状態の集合であり、
• ${\displaystyle \delta}$状態入力ペアを後続状態にマッピングする次の状態関数または遷移関数 である。${\displaystyle \delta :Q\times \Sigma \to Q}$
• ${\displaystyle \lambda}$状態と入力のペアを出力にマッピングする次の出力関数 です。${\displaystyle \lambda :Q\times \Sigma \to \Gamma }$

が有限であれば、は有限オートマトンである。^[5]${\displaystyle Q}$${\displaystyle M}$

入力した単語

オートマトンが有限の記号列（入力単語と呼ばれる）を読み取ります。すべての単語の集合は で表されます。${\displaystyle a_{1}a_{2}...a_{n}}$${\displaystyle a_{i}\in \Sigma }$${\displaystyle \Sigma^{*}}$

走る

状態のシーケンス（ただし、についてとなる）は、状態 から始まる入力に対するオートマトンの実行です。言い換えると、最初、オートマトンの開始状態 にあり、入力 を受け取ります。および入力文字列の に続く ごとに、オートマトンでは遷移関数 に従って次の状態を選択し、最後の記号が読み取られてマシンが実行の最終状態になるまで続けます。同様に、各ステップで、オートマトンでは出力関数 に従って出力記号を出力します。${\displaystyle q_{0},q_{1},...,q_{n}}$${\displaystyle q_{i}\in Q}$${\displaystyle q_{i}=\delta (q_{i-1},a_{i})}$${\displaystyle 0<i\leq n}$${\displaystyle a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$${\displaystyle q_{0}}$${\displaystyle q_{0}}$${\displaystyle a_{1}}$${\displaystyle a_{1}}$${\displaystyle a_{i}}$${\displaystyle q_{i}}$${\displaystyle \delta (q_{i-1},a_{i})}$${\displaystyle a_{n}}$${\displaystyle q_{n}}$${\displaystyle \lambda (q_{i-1},a_{i})}$

遷移関数は、入力ワード全体を入力したときのマシンの挙動を記述するために、帰納的に に拡張されます。 空の文字列、すべての状態、および が最後の記号でが文字列の残りの部分（空の場合もある）である文字列 の場合、 となります。^[10]出力関数も同様に に拡張でき、これは状態 からワード に対して実行されたときのマシンの完全な出力を提供します。${\displaystyle \delta}$${\displaystyle {\overline {\delta }}:Q\times \Sigma ^{*}\to Q}$${\displaystyle \epsilon }$${\displaystyle {\overline {\delta }}(q,\varepsilon )=q}$${\displaystyle q}$${\displaystyle wa}$${\displaystyle a}$${\displaystyle w}$${\displaystyle {\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)}$${\displaystyle \lambda}$${\displaystyle {\overline {\lambda }}(q,w)}$${\displaystyle w}$${\displaystyle q}$

アクセプター

形式言語理論を用いてオートマトンを研究するためには、オートマトンをアクセプタとして考え、出力アルファベットと関数を 置き換え、${\displaystyle \ガンマ}$${\displaystyle \lambda}$

• ${\displaystyle q_{0}\in Q}$、指定された開始状態、および
• ${\displaystyle F}$（すなわち）の状態の集合を受容状態と呼ぶ。${\displaystyle Q}$${\displaystyle F\subseteq Q}$

これにより、次のことを定義できます。

受け入れの言葉

つまり、文字列全体を消費した後、マシンが受け入れ状態にある場合、単語はオートマトンにとって受け入れ単語となります。${\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$${\displaystyle {\overline {\delta }}(q_{0},w)\in F}$${\displaystyle w}$

認識言語

オートマトンが認識する言語とは、オートマトンが受け入れる全ての単語の集合である。[ ^13]${\displaystyle L\subseteq \Sigma ^{*}}$ ${\displaystyle L=\{w\in \Sigma ^{*}\ |\ {\overline {\delta }}(q_{0},w)\in F\}}$

認識可能な言語

認識可能な言語とは、あるオートマトンによって認識される言語の集合です。有限オートマトンの場合、認識可能な言語は通常の言語です。オートマトンの種類によって、認識可能な言語は異なります。

オートマトンとは、数学的形式主義に基づいて有用な機械を研究するために定義されます。したがって、オートマトンの定義は、オートマトンを使用してモデル化したい「現実世界の機械」に応じて変化します。オートマトンにはさまざまなバリエーションが研究されてきました。以下は、オートマトンの各コンポーネントの定義における一般的なバリエーションです。

入力

• 有限入力: 有限のシンボルシーケンスのみを受け入れるオートマトン。上記の導入定義は有限の単語のみを対象としています。
• 無限入力: 無限の単語 ( ω-単語)を受け入れるオートマトン。このようなオートマトンをω-オートマトンと呼びます。
• ツリー入力: 入力は、シンボルのシーケンスではなく、シンボルのツリーである場合があります。この場合、各シンボルを読み取った後、オートマトンが入力ツリー内のすべての後続シンボルを読み取ります。オートマトンが後続シンボルごとに1 つのコピーを作成し、各コピーがオートマトン遷移関係に従って状態から後続シンボルの 1 つで実行を開始すると言われています。このようなオートマトンをツリー オートマトンと呼びます。
• 無限木入力 : 上記の 2 つの拡張を組み合わせると、オートマトンが (無限の) 分岐を持つ木構造を読み取ります。このようなオートマトンを無限木オートマトンと呼びます。

州

• 単一状態：組み合わせ回路とも呼ばれる単一状態のオートマトンが、組み合わせ論理を実装する変換を実行します。^[10]
• 有限状態: 有限の数の状態のみを含むオートマトン。
• 無限状態: 有限の数の状態、または数えられる数の状態さえ持たないオートマトン。さまざまな種類の抽象メモリを使用して、このようなマシンに有限の説明を与えることができます。
• スタック メモリ: オートマトンは、シンボルをプッシュおよびポップできるスタックの形で追加のメモリを含むこともあります。この種のオートマトンは、プッシュダウン オートマトンと呼ばれます。
• キューメモリ: オートマトンはキューの形でメモリを持つことがあります。このようなマシンはキューマシンと呼ばれ、チューリング完全です。
• テープ メモリ: オートマトンの入力と出力は、入力テープと出力テープと呼ばれることがよくあります。チューリング マシン、線形境界オートマトン、対数空間トランスデューサなど、一部のマシンには追加の作業テープがあります。

遷移関数

• 決定論的: 与えられた現在の状態と入力シンボルに対して、オートマトンが 1 つの状態にのみジャンプできる場合、それは決定論的オートマトンです。
• 非決定性: 入力シンボルを読み取った後、遷移関係に従って、複数の状態のいずれかにジャンプするオートマトン。遷移関数という用語は、遷移関係に置き換えられます。オートマトンが非決定性で、許可された選択肢の 1 つにジャンプすることを決定します。このようなオートマトンを非決定性オートマトンと呼びます。
• 交替: このアイデアはツリーオートマトンに非常に似ていますが、直交しています。オートマトンは同じ次の読み取りシンボルで複数のコピーを実行する場合があります。このようなオートマトンを交替オートマトンと呼びます。入力を受け入れるには、このようなコピーのすべての実行で受け入れ条件が満たされている必要があります。
• 双方向性: オートマトンでは入力を左から右に読み取ることも、チューリング マシンと同様に入力を前後に移動することもできます。入力を前後に移動できるオートマトンを双方向有限オートマトンと呼びます。

受諾条件

• 有限語の受け入れ: 上記の非公式な定義で説明したものと同じです。
• 無限の単語の受け入れ:無限の単語は決して終了しないので、 ω オートマトンには最終状態がありません。むしろ、単語の受け入れは、実行中に訪問された状態の無限のシーケンスを調べることによって決定されます。
• 確率的受容: オートマトンが入力を厳密に受け入れたり拒否したりする必要はありません。0から 1 の間の確率で入力を受け入れる場合があります。たとえば、量子有限オートマトン、幾何学オートマトン、およびメトリックオートマトンには確率的受容があります。

上記のバリエーションのさまざまな組み合わせにより、多くのクラスのオートマトンが生成されます。

オートマトン理論は、さまざまな種類のオートマトンの特性を研究する主題です。たとえば、特定の種類のオートマトンについて、次の質問が研究されます。

• ある種のオートマトンによって認識可能な形式言語のクラスはどれですか? (認識可能な言語)
• 特定のオートマトンが形式言語の和集合、積集合、または相補集合に対して閉じているか? (閉包特性)
• 形式言語のクラスを認識するという点において、ある種のオートマトンがどの程度表現力があるか? また、それらの相対的な表現力は? (言語階層)

オートマトン理論では、次のリストに類似した問題を解決するための 効果的なアルゴリズムの存在または非存在についても研究します。

• オートマトンが少なくとも 1 つの入力単語を受け入れますか? (空チェック)
• 認識される言語を変更せずに、与えられた非決定性オートマトンを決定性オートマトンに変換することは可能ですか? (決定化)
• 与えられた形式言語について、それを認識する最小のオートマトンは何ですか? (最小化)

以下は、オートマトンの種類の一覧です（不完全です）。

通常、オートマトン理論は抽象マシンの状態を記述しますが、離散オートマトン、アナログオートマトンまたは連続オートマトン、あるいはハイブリッド離散連続オートマトンがあり、それぞれデジタルデータ、アナログデータまたは連続時間、またはデジタルデータとアナログデータを使用します。

以下は、さまざまな種類の仮想マシンの能力に関する不完全な階層です。この階層は、マシンが受け入れることができる言語のネストされたカテゴリを反映しています。^[14]

オートマトン理論の各モデルは、いくつかの応用分野で重要な役割を果たしています。有限オートマトン は、テキスト処理、コンパイラ、ハードウェア設計で使用されます。文脈自由文法(CFG) は、プログラミング言語と人工知能で使用されます。元々、 CFG は人間の言語の研究で使用されていました。セルオートマトンは人工生命の分野で使用されており、最も有名な例はジョン・コンウェイのライフゲームです。生物学でオートマトン理論を使用して説明できる他の例としては、軟体動物や松ぼっくりの成長や色素沈着パターンなどがあります。さらに、宇宙全体が何らかの離散オートマトンによって計算されているという理論を一部の科学者が提唱しています。このアイデアはコンラート・ツーゼの研究に端を発し、エドワード・フレドキンによってアメリカで普及しました。オートマトン は有限体の理論にも登場します。2次多項式の合成として記述できる既約多項式の集合は、実際には正規言語です。 ^[15] オートマトンが使用できるもう一つの問題は正規言語の誘導である。

オートマトンシミュレーターは、オートマトン理論を教え、学び、研究するために使われる教育ツールです。オートマトンシミュレーターは、オートマトンの説明を入力として受け取り、任意の入力文字列に対する動作をシミュレートします。オートマトンの説明は、いくつかの方法で入力できます。オートマトンを記号言語で定義すること も、その仕様をあらかじめ設計された形式で入力することも、マウスをクリックしてドラッグすることで遷移図を描くこともできます。よく知られているオートマトンシミュレーターには、Turing's World、JFLAP、VAS、TAGS、SimStudio などがあります。^[16]

前のセクションで説明したさまざまなタイプへのオートマトン分類に従って、いくつかの異なるオートマトンカテゴリ^{[17]を定義できます。決定性オートマトン、シーケンシャルマシンまたは}シーケンシャルオートマトン、およびオートマトン間の矢印を定義するオートマトン準同型を持つチューリングマシンの数学的カテゴリは、直交閉カテゴリであり、^[18]カテゴリ極限と余極限の両方を持ちます。オートマトン準同型は、オートマトンA _iの 5 組を別のオートマトンA _jの 5 組に マップします。オートマトン準同型は、オートマトンの状態空間Sが半群S _gとして定義されている場合、オートマトン変換または半群準同型と見なすこともできます。モノイドは、モノイドカテゴリのオートマトンに適した設定と見なされます。^{[19] [20] [21]}

変数オートマトンの種類

また、自己準同型を介して、ノーバート・ウィーナーの著書『人間の利用』の意味で、変数オートマトンを定義することもできます。すると、そのような変数オートマトン準同型が数学的な群を形成することが示されます。ただし、非決定性またはその他の複雑な種類のオートマトンの場合、後者の自己準同型のセットは、変数オートマトン群類になることがあります。したがって、最も一般的なケースでは、あらゆる種類の変数オートマトンカテゴリは、群類のカテゴリまたは群類カテゴリです。さらに、可逆オートマトンカテゴリは 2カテゴリであり、群類の2カテゴリ、または群類カテゴリのサブカテゴリでもあります。 ${\displaystyle A_{i}\to A_{i}}$

• ブール微分積分
• ペトリネット

• John E. Hopcroft、Rajeev Motwani、Jeffrey D. Ullman (2000)。オートマトン理論、言語、計算入門（第2版）。Pearson Education。ISBN 978-0-201-44124-6。
• マイケル・シプサー（1997年）。計算理論入門。PWS出版。ISBN 978-0-534-94728-6。パート 1: オートマトンと言語、第 1 章から第 2 章、29 ～ 122 ページ。セクション 4.1: 決定可能な言語、152 ～ 159 ページ。セクション 5.1: 言語理論からの決定不可能な問題、172 ～ 183 ページ。
• エレイン・リッチ（2008年）。オートマトン、計算可能性、複雑性：理論と応用。ピアソン。ISBN 978-0-13-228806-4。
• Salomaa, Arto (1985)。計算とオートマトン。数学とその応用百科事典。第25巻。ケンブリッジ大学出版局。ISBN 978-0-521-30245-6.ZBL 0565.68046  .
• アンダーソン、ジェームズ A. (2006)。オートマトン理論と現代的応用。トム・ヘッドの寄稿付き。ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-61324-8.ZBL1127.68049  。​
• Conway, JH (1971)。「正規代数と有限マシン」。Chapman and Hall 数学シリーズ。ロンドン: Chapman & Hall。Zbl 0231.94041  。
• ジョン・M・ハウィー（1991）オートマタと言語、クラレンドン・プレス ISBN 0-19-853424-8 MR 1254435 
• サカロヴィッチ、ジャック（2009）。オートマトン理論の要素。フランス語からルーベン・トーマスによる翻訳。ケンブリッジ大学出版局。ISBN 978-0-521-84425-3.ZBL1188.68177  。​
• James P. Schmeiser、David T. Barnard (1995)。ボトムアップ解析によるトップダウン解析順序の生成。Elsevier North-Holland。
• イゴール・アレクサンダー、F. キース・ハンナ (1975)。オートマトン理論: 工学的アプローチ。ニューヨーク: クレイン・ラサック。ISBN 978-0-8448-0657-0。
• マービン・ミンスキー(1967)。『計算：有限マシンと無限マシン』プリンストン、ニュージャージー：プレンティス・ホール。
• ジョン・C・マーティン（2011年）。言語と計算理論入門。ニューヨーク：マグロウヒル。ISBN 978-0-07-319146-1。

• dk.brics.オートマトン
• リブファ