オートマトン理論：抽象機械、形式言語、計算

特徴と基本定義

オートマトンとは、有限または無限の状態集合、特別に定められた開始状態、受理状態（終状態）の集合、および記号を読み取った際に装置がどのように状態を変えるかを記述する遷移規則からなる抽象的構造である。こうした構造はしばしば抽象機械と呼ばれる。重要な区別として、機械が決定的か、非決定的かがある。決定的な機械では、各記号と現在の状態に対する次状態は一つだけであるのに対し、非決定的な機械では複数の可能な次状態をもつ。また、スタックのような追加の記憶を備えるかどうか、離散的な手順で動作するか、あるいは制限のないテープ状の記憶を用いるかも重要である。

分類と中心的モデル

• 有限オートマトン（決定性・非決定性）：正規言語を認識し、パターン照合や字句解析の基礎となる。
• プッシュダウン・オートマトン：スタックを備え、プログラミング言語の構文記述によく用いられる文脈自由言語を認識する。
• チューリング機械：無限のテープをもつ理想化された装置であり、アルゴリズム的計算可能性という非形式的な概念を捉え、決定可能問題と決定不能問題を定義する。
• その他の変種：線形有界オートマトン、セル・オートマトン、量子オートマトンは、資源を拡張または制約することで中間的なクラスを研究する。

歴史と理論的基盤

オートマトン理論は、研究者たちが計算と言語の概念を形式化した20世紀半ばに成立した。論理学者と計算機科学者の研究により、形式文法、有限状態手法、チューリング機械モデルが生み出され、機械の能力を厳密に比較する方法が与えられた。チョムスキー階層は、文法の型とそれに対応するオートマトンを、表現力と資源制限の関係に基づく段階として配置する。基礎的な成果には、特定の言語クラスにおいて決定的モデルと非決定的モデルが等価であることを示す構成や、機械がある問題を決定できない限界を示す証明が含まれる。

応用と典型的な決定問題

オートマトン理論の考え方は、計算機分野の幅広い領域で実用化されている。正規表現と有限オートマトンはテキスト検索や字句スキャナを支え、プッシュダウン・オートマトンは構文解析器の設計に役立つ。チューリング完全なモデルは計算可能性とアルゴリズムの限界を捉える枠組みを与え、状態に基づくモデルはハードウェア設計やモデル検査を支援する。代表的な決定問題には、所属問題（あるオートマトンは特定の語を受理するか）、空性問題（受理される語は一つでも存在するか）、等価性問題（二つの機械は同じ語の集合を受理するか）、最小化問題（機械をより少ない状態へ縮約できるか）がある。これらの問題の決定可能性と計算量はモデルに依存する。有限オートマトンでは効率的に解けるものが多い一方、モデルの能力が増すと決定不能または扱いにくい問題となりうる。

重要な区別と事実

主要な対比には、決定性と非決定性がある。有限オートマトンでは両者は表現力の点で等価だが、より豊かなすべてのモデルについてそうであるとは限らない。また、記憶と認識能力の間にはトレードオフがあり、スタックは認識能力を正規言語から文脈自由言語へと高める。さらに、どのオートマトンでも解くことのできない計算不可能な問題が存在する。閉包性、すなわち言語クラスが和、積、補集合、連接、クレーネ閉包のもとで閉じているかどうかと、計算量の上界は、何を効率的に認識できるかを論じるための中心的な道具である。これらの概念により、オートマトン理論はシステム設計のための実践的な道具立てであると同時に、計算そのものを理解するための理論的枠組みとなる。詳しい背景については、オートマトンに関する一般的な概説を参照されたい。

この分野で扱われる典型的な例題には、与えられた正規言語に対する最小オートマトンの構成、ポンピング補題またはマイヒル＝ネローデ型の議論による言語の非正規性の証明、言語クラスについての決定可能性または困難性に関する結果の確立がある。こうした問題は形式言語理論を論理学、代数学、計算量理論へと結び付け、現代計算機科学の幅広い知的基盤を形成している。