有限オートマトン

有限オートマトン(finite automaton)

入力情報の個数と状態の個数が有限の場合、有限オートマトン。

決定性のありなし

線形拘束オートマトン

開始状態

受理状態

状態遷移関数

確認用

Q. 有限オートマトン

参考

有限オートマトン（ゆうげんオートマトン、英: finite automaton)または有限状態機械（ゆうげんじょうたいきかい、英: finite state machine, FSM）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。

関連