有限オートマトン
タイプによって、いくつかの定義が存在する。 アクセプタ有限オートマトンは ⟨Σ, S, s0, δ, F⟩ の5要素から構成される。
Σ は入力文字セット(有限だが空ではないシンボルの集合)
S は有限であって空でない状態の集合
s0 は S の要素でもある初期状態
δ は状態遷移関数: δ: S × Σ → S (非決定性有限オートマトンの場合、 δ は状態の集合を返すので δ : S × Σ → P ( S ) {\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)} となる)
F は終了状態の集合であり、 S の部分集合(空もありうる)
決定性FSMでも非決定性FSMでも δ {\displaystyle \delta } は部分関数でもよく、 δ ( q , x ) {\displaystyle \delta (q,x)} としたとき、 q ∈ S {\displaystyle q\in S} と x ∈ Σ {\displaystyle x\in \Sigma } のあらゆる組合せについて定義する必要はない。有限オートマトン M {\displaystyle M} が q {\displaystyle q} という状態で次の入力記号が x {\displaystyle x} のとき、 δ ( q , x ) {\displaystyle \delta (q,x)} が未定義なら M {\displaystyle M} はエラーを返す(すなわち、入力は拒絶・却下される)。これは汎用の状態機械の定義では便利だが、状態機械を変換するのにはあまり便利ではない。
この有限オートマトンは入力動作のみを使用する。すなわち、出力は入力と状態に依存する。ミーリ・モデルは状態の数を減らす作用がある。図7の例はムーア・マシンの例と同じものをミーリ・マシンで実装したものを示している(実装された有限オートマトンのふるまいは実行モデルに依存する。例えば仮想有限状態機械(英語版)では動作するが、イベント駆動有限状態機械(英語版)では動作しない)。これは二つの入力動作を持つ。「閉鎖命令が来たら扉を閉めるためにモーターを起動する」という入力動作と「開放命令が来たら扉を開けるためにモーターを起動する」という入力動作である。
実際には、これらを混合したモデルがよく使用される。
ムーア・モデルとミーリ・モデルの違いの詳細は、実施例も含めて外部サイトの"Moore or Mealy model?"にある(ただし英語)。
初期状態は、一般にどこからも矢印で指されていない状態である。