ウィキペディア

有限オートマトン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/01/28 00:21 UTC 版)

(有限状態機械 から転送)

有限オートマトン（ゆうげん-、finite automaton、FA)または有限状態機械（ゆうげんじょうたいきかい、finite state machine、FSM）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限な記憶領域を持ち、一連の記号列を入力として一度に1つずつ読み込み、後戻りはしない。出力は、そのモデルが実装されれば何らかのユーザインタフェースの形でなされることもある。有限オートマトンは「初期状態」として1つの状態をとり、入力の値に従って異なる状態へと遷移していき、いずれかの状態で終了する。特定の状態群のいずれかで終わっていれば、成功（受容状態）となる。