- オートマトン（automaton）とは、入力に対して内部の状況に応じた処理を行った結果を出力する仮想的な自動機械の概念です。オートマトンのうち、状態の個数と入力の個数が有限個の場合を有限オートマトンといいます。
- 処理に伴い、内部の状態が変化する（遷移といいます）ので、同じ入力でも異なる処理、異なる出力になります。それで、どの状況のときに、どの入力があると、どの状態に遷移するかを示す規則が必要になります。それを表形式にしたものを状態遷移表、図の形式にしたものを状態遷移図といいます。
- 有限オートマトンでは、開始をするときの状態と終了するときの状態が決められており、開始状態で最初の入力が行われ、入力の最後で決められた状態（受理状態という）になる（受理されたという）ことが求められます。
- 有限オートマトンを、テープの先頭から読み込み、処理と遷移を繰り返していく仮想的な機械であると考えたものがチューリングマシンです。チューリングマシンは、コンピュータの基本原理になっています。
オートマトンの概念およびそれを記述する状態遷移図は、論理回路の設計やソフトウェアの設計に重要なものになっています。
例えば右図は、ＯＳのタスク管理において、タスクの状態の遷移を図示したものです。
新しくタスクが生成されると、まず「実行可能状態」になります（①）。その状態にある複数のタスクからディスパッチャにより選択されたタスクは「実行状態」に遷移（②）して実行され（ＣＰＵが割り当てられ）、実行が終了すればタスクは消滅します（⑥）。実行している間に、なんらかの割込みが発生して、他のタスクにＣＰＵが割り当てられると、このタスクは「待機状態」に遷移します（④）。以下省略（詳細は「タスク管理」（hs-task-kanri）参照）
状態遷移の動きを例題で解説します。
○問題
下の状態遷移図あるいは状態遷移表と入力が与えられたとき、遷移の過程を示せ。
 |
遷移先 |
○解答
アの場合：①１→②０→③１→④１→⑤１のように入力番号をつけます。
- 初期状態Ａでは、入力が０なら遷移せずにＡの状態が継続し、１ならばＢへ遷移することを示しています、①の入力が１なので、Ｂへ遷移します。
- ②では、Ｂにおいて０が入力されたので、Ａへ戻ります。
- ③では、Ａにおいて１が入力されたので、Ｂへ遷移します。
- ④では、Ｂにおいて１が入力されたので、Ｄへ遷移します。
- ⑤では、Ｄにおいて１が入力されたので、Ｃへ遷移します。この結果、受理状態に達しました。
イの場合：次の遷移になるので、受理状態にならず拒否されます。
Ａ（１）→Ｂ（１）→Ｄ（１）→Ｃ（１）→Ｅ（０）→Ｅ
ペトリネット
ペトリネット(Petri Net)とは、数学的なモデルの一種で、並行的、非同期的、分散的なシステムの表現など、状態遷移図に似た目的に使われます。
ペトリネットはシステムを条件(condition)と事象(event)を基本としてモデル化し、次の４つの図形で表現します（図ａ）。
- プレース（○印）条件
- トランジション（｜印なたは四角）事象
- アーク（→印）プレースとトランジションの接続
- トークン（●印）状態遷移の状態
状態偏移はトークンの移動によるプレース配置組み合わせの変化で表されれます。
- トークンはペトリネットのトランジションを発火(firing)させることによりネット内を移動します。
- トランジションを発火させるためにはトランジションが発火可能(enable)でなければなりません。トランジションのすべての入力プレースにトークンがあるとき, そのトランジションは発火可能です(図ｂ)。
- トランジションが発火すると, その入力プレースからトークンを取り除き, 新しいトークンを生成してそれを出力プレースに置きます(図ｃ)。