有限オートマトン
さらなる分類方法として、決定性有限オートマトン (DFA) と非決定性有限オートマトン (NFA, GNFA) がある。決定性有限オートマトンでは、各状態の考えられる全ての入力について一意に次の状態が決定される。非決定性有限オートマトンでは、ある状態にある入力があったとき遷移がどうなるかが決定されない(遷移がないかもしれないし、複数の遷移が対応しているかもしれない)。このような区別は実行時間などの観点では重要だが、ふるまいに関する観点ではそれほど重要ではない。それぞれのオートマトンで表現可能なふるまいは同じであり、任意のNFAを等価な(しかしより大きな)DFAに変換するアルゴリズムが存在する(冪集合構築(英語版))。
ひとつしか状態を持たない有限オートマトンは結合有限オートマトンと呼ばれ、入力動作のみを持つ。これは複数の有限オートマトンが協調動作する場合に便利であり、結合有限オートマトンとして表せる部分を抽出して設計に活用する。
この有限オートマトンは開始動作のみを使用する。すなわち、出力は状態にのみ依存する。ムーア・モデルの利点はふるまいを単純化できることである。図6の例はエレベーターの扉についてのムーア・マシンを示している。この有限オートマトンは「開放命令」と「閉鎖命令」というふたつの命令を理解し、それによって状態が変化する。「開放途中」状態にある開始動作(E:)は扉の開くところを監視し始めることを示し、「閉鎖途中」状態にある開始動作(E:)は扉の閉じるところを監視し始めることを意味する。「開放」と「閉鎖」状態は動作を伴わないが、これらは外界(つまり他のオートマトン)に扉が開いているとか閉まっているといった状況を知らせる意味を持つ。
有限オートマトンについて、その遷移規則(関数)を表にしたものが状態遷移表である。現在の状態(例えばB)と入力(例えばY)の交差するところに次の状態(例えばC)を示す。以下にごく単純な一例を示す。