オートマトン

オートマトン：計算モデルの基礎

オートマトンは、計算理論において中心的な役割を果たす概念です。自動機械、あるいは自動人形という意味を持つこの言葉は、計算モデルを指し、有限オートマトンやチューリングマシンなど、様々な種類が存在します。それぞれのオートマトンは、計算能力に違いがあり、複雑な計算を行う能力を持つものから、比較的単純な計算しか行えないものまで多岐に渡ります。

オートマトンの種類

オートマトンは、その計算能力や構造によって、いくつかの種類に分類されます。代表的なものとして、以下のものがあります。

有限オートマトン

[有限オートマトン]]は、最も基本的なオートマトンの一つです。有限個の状態を持ち、入力文字列を読み込みながら状態を遷移していきます。状態遷移の過程で、入力文字列が受理されるかどうかを判定します。有限オートマトンには、決定的[[有限オートマトン]と非決定的[有限オートマトン]があり、DFAは各状態において次の状態が常に一つに定まっているのに対し、NFAは複数の状態へ遷移できる可能性があります。さらに、ε動作を含む非決定的[有限オートマトン]も存在し、入力文字列を読まずに状態遷移を行うことができます。

プッシュダウン・オートマトン

プッシュダウン・オートマトン(PDA)は、有限オートマトンにスタックというデータ構造を追加したものです。スタックは、後入れ先出し(LIFO)のデータ構造で、入力文字列の処理中に情報を一時的に保存することができます。このスタック機能により、PDAは有限オートマトンよりも強力な計算能力を持ちます。

線形拘束オートマトン

線形拘束オートマトン(LBA)は、利用できるメモリが、入力文字列の長さに比例して線形に増加するオートマトンです。有限オートマトンやプッシュダウン・オートマトンよりも強力な計算能力を持ちます。

生け垣オートマトン

生け垣オートマトン(Hedge Automata)は、木構造のデータを処理するのに適したオートマトンです。

チューリングマシン

[チューリングマシン]]は、計算理論において最も強力な計算モデルの一つです。無限長のテープと、そのテープを読み書きするヘッドを持ち、プログラムに従って動作します。チューリングマシンは、任意の計算可能な問題を解くことができます。チューリングマシンも、決定的[[チューリングマシン]と非決定的[チューリングマシン]に分類されます。

形式言語との関係

オートマトンは、形式言語と密接な関係があります。ある形式言語を生成する文法（形式文法）と、その言語を受理するオートマトンは、一対一の対応関係にあります。つまり、特定のオートマトンは特定の形式言語のみを受理し、逆に特定の形式言語を受理できるオートマトンは一種類しか存在しません。さらに、これらの形式言語は、包含関係によって階層構造を形成しており、この関係はチョムスキー階層として知られています。

関連分野

オートマトンは、計算理論の基礎となる概念であり、様々な分野で応用されています。例えば、コンパイラ設計、自然言語処理、ソフトウェア検証など、多くの分野でオートマトンが活用されています。また、抽象機械、セル・オートマトン、状態機械、正規表現、形式文法など、多くの関連概念があります。

参考文献

米田政明 他 『オートマトン・言語理論の基礎』、 近代科学社、2003年
岩間 一雄：「オートマトン・言語と計算理論」、コロナ社、2003年
藤原暁宏：「はじめて学ぶ　オートマトンと言語理論」、森北出版、2015年
Zvi Kohavi; Niraj K. Jha (2009), Switching and Finite Automata Theory (3rd ed.), Cambridge University Press

もう一度検索