有限オートマトン
トランスデューサ(変換機、transducer)は、与えられた入力と動作を伴う状態(両方または一方)に基づいて出力を生成する。このタイプの有限オートマトンは計算言語学の分野や制御などに使われる。また、トランスデューサは二種類に分類される。
有限オートマトン(ゆうげんオートマトン、英: finite automaton)または有限状態機械(ゆうげんじょうたいきかい、英: finite state machine, FSM)とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。
有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械(群)を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。