オートマトンとは？

詳細解説

オートマトン（自動機械）は、入力を受け取るたびに内部の状態が決まった規則で切り替わる（状態遷移）仕組みを数学的に抽象化した計算モデルです。代表的なものが有限オートマトンで、有限個の状態、入力の記号、状態がどう変わるかを示す遷移規則、初期状態、受理状態（最終状態）から成ります。入力を最後まで読んだとき受理状態にいれば、その入力列を受理します。これは、ある規則に合う文字列（形式言語）かどうかを判定する仕組みと見なせ、正規表現による文字列の照合や、コンパイラの字句解析に応用されます。状態遷移図や状態遷移表で、動作を表現します。シラバスでは、述語論理、形式言語、オートマトンなど、情報に関する理論のあらましを理解することが示されています。

FE試験での出題ポイント

• 1状態・遷移・初期状態・受理状態という構成要素を説明できるようにする
• 2状態遷移図から、ある入力が受理されるかを追えるようにする
• 3形式言語や字句解析との関係を理解する

関連用語