順序機械は記憶のある回路や機械を抽象化したもので、次の性質を持つ記号処理機械である。入力記号によって変化し過去の入力の状況を記憶する内部状態を持つ。入力と内部状態に依存して出力記号が決まる。入力とそのときの内部状態に依存して内部状態を変わることを状態遷移という。状態が有限個しかない順序機械は有限状態機械とという。これは順序機械の中で実用上重要である。例:順序論理回路のもっとも簡単なものとしてはフリップフロップが挙げられる。状態遷移図とは、状態が入力によってどのように遷移するのかを有向グラフによって図示したものである。状態を点に対応させて、状態名をラベルとし、有向辺には入力記号を対応させて、辺ラベルとした表現である。出力はそのときの状態と入力で決まるなら辺ラベルの一部として表現させる。これをミーリー(Mealy)機械という。遷移先の状態で決まるなら点ラベルの一部として表現させる。これをムーア(Moore)機械という。例1:ミーリー機械の例Dフリップフロップ1入力1出力のフリップフロップで、入力dの値が変化すると変化前の値を出力する遅れ(delay)素子の役割をする。例2:ムーア機械の例RSフリップフロップ2入力1出力(見かけは2出力)のフリップフロップで、出力は遷移先の状態と同じである。Σ:入力記号の集合(入力アルファベット)Q:内部状態このとき、状態と入力記号から次の状態が決まる状態遷移を写像δ:Q×Σ→Qとみなしたとき、δを状態遷移関数という。遷移関数を関数表として表したものが状態遷移表である。Γ:出力記号の集合(出力アルファベット)出力はそのときの状態と入力記号に依存する。それを関数とみたものを出力関数といい、γで表す。γはQ×Σ→Γという写像を持つ。Dフリップフロップ(4489d)。