TL;DR
システムやプログラムが内部に持つ状態とその変化を表し、状態に応じて特定の動作を実行するためのモデルである。
仕組み
ステートマシンは、状態（State）と遷移（Transition）の 2 つの要素で構成される。状態はシステムのある時点の状態を表し、遷移は状態の間の変化を表す。ステートマシンは、現在の状態と次の入力に基づいて遷移し、次の状態に移る。
Wikipedia によると、状態の数が有限のものを有限オートマトン（有限状態機械）と呼ぶ。入力記号の集合、状態の集合、初期状態、状態遷移関数、受理状態の集合の 5 つで定義される。状態をノード、遷移を矢印で描く状態遷移図や、今の状態と入力から次の状態を引く状態遷移表で表す。各状態と入力に対して次の状態が 1 つに決まるものを決定性、決まらない場合があるものを非決定性と呼ぶが、両者が認識できる言語は同じである。
例
情報工学では、アプリケーションの動作のモデル化、ハードウェア設計、コンパイラ、通信プロトコルの設計などに使われる。
注意点
有限オートマトンは、チューリングマシンと違って計算の状態を記憶するテープを持たないので、チューリング完全ではない。