読み方：ゆうげんオートマトン

有限オートマトン【finite automaton】有限状態機械

別名：FSM/Finite State Machine

概要

有限オートマトンとは、計算モデルの一種で、限られた数の「状態」を持ち、入力に応じてそれらの状態間を遷移するもの。計算理論や形式言語理論の基礎的な概念で、文字列の認識やパターン判定を形式的に扱うための理論的枠組みとして用いられる。

有限オートマトンは、入力記号を一つずつ読み取りながら、現在の状態と入力に応じて次の状態へと移行する抽象機械である。現在どの段階にあるかを示す「状態」と、外部からの信号を受け取って別の状態へ移る「遷移」、そして一連の処理が正しく終了したかを判定する「受理状態」から成る。

状態の総数は有限であり、開始状態と受理状態があらかじめ定められている。入力として与えられた文字列や記号の列を一つずつ読み進め、すべての入力を終えたときに特定の「受理状態」に到達していれば、その入力は正当なものとして受け入れられる。

例えば、自動販売機の動作を有限オートマトンによってモデル化すると、硬貨が投入されておらず利用者による操作を待機している開始状態から始まる。百円玉が投入されるという「入力」によって、「百円蓄積」という状態へ遷移する。さらにボタンが押されることで「商品搬出」という受理状態へ移り、最終的に元の待機状態に戻る。

有限オートマトンには、「決定性有限オートマトン」と「非決定性有限オートマトン」の二種類がある。前者は各状態と入力記号の組に対して遷移先が一意に定まるモデルであり、後者は複数の遷移先を持つことが許されるモデルである。理論的には両者は同じ表現能力を持ち、いずれも正規言語と呼ばれる言語の集合を認識できる。

メモリの容量が無限である必要はなく、あらかじめ決められた固定数の状態だけで処理が完結するため、非常に軽量で予測可能性の高いシステムを構築するのに適している。コンパイラによるソースコードの字句解析、テキスト検索、通信プロトコルの状態管理など、実用的な情報処理の基礎にも広く応用されている。