オートマトン(オートマトン)とは | 意味や読み方など丁寧でわかりやすい用語解説

オートマトンとは、外部からの入力に応じて内部の状態を変化させ、特定の規則に従って動作する「抽象的な機械モデル」を指す。その名前は「自動で動く機械」を意味するギリシャ語に由来し、コンピュータが情報を処理するメカニズムを理論的に理解するための基礎概念の一つである。計算機科学や情報科学の分野において、アルゴリズムの動作原理、プログラミング言語の構造、論理回路の設計など、多岐にわたる領域でその概念が応用される。

オートマトンの基本的な構成要素は、「入力」「内部状態」「状態遷移規則」「出力」の四つである。まず、「入力」とは、オートマトンが外部から受け取る情報やデータであり、これによってオートマトンの動作が駆動される。次に、「内部状態」は、オートマトンが現在どのような状況にあるかを示すもので、過去の入力処理の履歴が集約された情報と考えることができる。例えば、自動販売機であれば「コインが投入されていない状態」「100円投入された状態」「商品選択待ちの状態」などがこれにあたる。そして、「状態遷移規則」は、現在の内部状態と受け取った入力に基づいて、次にどの内部状態へと変化するかを定める一連のルールである。この規則に従い、オートマトンは状態を変化させていく。最後に、「出力」は、オートマトンが処理を終えた結果として外部へ提供する情報や動作を指す。自動販売機の例では、商品が排出されることや、お釣りが返却されることが出力にあたる。信号機もオートマトンの好例であり、時間経過（入力）に応じて「青」「黄」「赤」と内部状態が遷移し、対応する色の光（出力）を放つ。このように、オートマトンは特定のルールに従い自律的に動作するシステムをモデル化する際に非常に有効なツールであり、コンピュータが特定の「言語」を認識する能力を考察する上でも重要な役割を果たす。ここでいう「言語」とは、人間が話す自然言語ではなく、特定の記号列や文字列の集合、例えばプログラミング言語の正しい構文などを指す。この概念を学ぶことは、コンピュータがどのように計算し、情報を処理するのかという根源的な部分を理解するための第一歩となる。

オートマトンは、その記憶能力や処理能力に応じていくつかの主要な種類に分類される。最も基本的なモデルが「有限オートマトン（Finite Automaton, FA）」である。これは内部状態の数が有限であり、記憶できる情報量が限定されているという特徴を持つ。FAは、ある文字列が特定のパターン（正規表現など）に合致するかどうかを判定するのに非常に適しており、検索エンジンのキーワードマッチング、プログラミング言語の字句解析（変数名やキーワードの識別）、ネットワークプロトコルの状態管理などに広く用いられる。決定性有限オートマトン（DFA）と非決定性有限オートマトン（NFA）が存在するが、認識できる能力という点では両者に違いはないことが証明されている。

次に、FAに「スタック」という特別な記憶装置が追加されたものが「プッシュダウンオートマトン（Pushdown Automaton, PDA）」である。スタックは、後から入れたデータが先に取り出される（LIFO: Last In First Out）という特性を持つ記憶装置で、これによりPDAはFAでは認識できなかった「ネストした構造」、例えば括弧の対応関係（((()))）やプログラミング言語のブロック構造などを認識できる能力を持つ。PDAは、プログラミング言語の構文解析、すなわちコードが文法的に正しいかをチェックするコンパイラの主要な部分をモデル化する際に非常に有効である。PDAが認識できる言語は「文脈自由言語」と呼ばれ、多くのプログラミング言語の文法はこのクラスに属する。

そして、オートマトンの究極のモデルとされ、現代のコンピュータの理論的な基礎となっているのが「チューリングマシン（Turing Machine, TM）」である。TMは、FAやPDAが持つ記憶装置に加えて、「無限の長さを持つテープ」と「テープヘッド」を持つ。このテープは記憶装置として機能し、ヘッドはテープ上を移動して記号を読み書きできる。この無限の記憶能力と柔軟な操作性により、TMはあらゆる種類の計算、つまりコンピュータで実行可能なすべてのアルゴリズムをシミュレートできる能力を持つ。チューリングマシンが計算できる問題の範囲は「計算可能性」と呼ばれ、計算の限界や本質を探る上で極めて重要な概念である。あらゆるプログラミング言語で記述できるアルゴリズムは、理論上すべてチューリングマシンで実行可能であるという「チャーチ・チューリングの提唱」は、計算機科学の根幹をなす考え方である。

これらのオートマトンは、それぞれ異なる種類の「形式言語」を認識する能力を持ち、その階層構造は「チョムスキー階層」と呼ばれ、コンピュータが処理できる問題の複雑さを分類する枠組みを提供している。システムエンジニアを目指す上でオートマトンを学ぶ意義は、単にこれらの理論的なモデルを知るだけでなく、コンピュータがどのように情報を処理し、アルゴリズムがどのように機能するかという根本的な原理を深く理解することにある。この理解は、より堅牢で効率的なシステム設計、複雑な問題解決能力の向上、そして将来の技術革新に対応できる応用力を養うための不可欠な基礎知識となる。