「オートマトン（automaton）」という言葉は、「自ら動くもの」を意味するギリシャ語を語源としており、「自動機械」と訳されることもあります。

注意すべきは、オートマトンは架空の機械であり、形式言語で記述された文を受理する機械を作れることを、学術的に証明する理論に過ぎない点です。

オートマトンは、入出力用の「テープ」、テープを読み書きする「ヘッド」、内部状態を遷移（変化）させる「有限状態制御装置」の3つの要素から成ります。
テープはマス目状に区切られていて、形式言語の記号が記憶されており、ヘッドで読み出した記号の内容と、現在の内部状態をもとにして、次の状態が決定されるのです。

例として図に10進数の数値データの構文をBNF記法で定義した。「：：＝」は「とは」というように代用すると理解できます。
0～9の数字と＋と－の符号を組み合わせることで、123や-456、3.14といった数値を表現しています。

オートマトンには、大きく「初期状態」、「中間状態」、「最終状態」の3つの状態があります。初期状態は1つだけですが、中間状態と最終状態は複数あっても良いです。
オートマトンが文を先頭から末尾まで解釈した結果として最終状態になったなら「文を受理した」と言え、逆に最終状態にならない場合には「文を拒否した」と言えます。

以下は、ＯＳのタスク管理において、タスクの状態の遷移を図示したものです。

新しくタスクが生成されると、まず「実行可能状態」になります（①）。

その状態にある複数のタスクからディスパッチャにより選択されたタスクは「実行状態」に遷移（②）して実行され（ＣＰＵが割り当てられ）、実行が終了すればタスクは消滅します（⑥）。

実行している間に、なんらかの割込みが発生して、他のタスクにＣＰＵが割り当てられると、このタスクは「待機状態」に遷移します（④）。

例）状態遷移図あるいは状態遷移表と入力が与えられたとき、遷移の過程を示せ。

入力    ア：10111  イ：11110

◆ アの場合：
   Ａ(1)→Ｂ(0)→Ａ(1)→Ｄ(1)→Ｃ(1)→Ｃ
   Ｃの受理状態が最後なので、アの入力は受理されます。

◆ イの場合：
   Ａ(1)→Ｂ(1)→Ｄ(1)→Ｃ(1)→Ｅ(0)→Ｅ
   Ｅが最後になっていて、Ｃの受理状態へ遷移していない拒否されます。