ミーリ・マシン

ミーリ・マシン（Mealy Machine）は出力が現在状態と入力によって決定される有限オートマトンである。つまり、状態遷移図で描くと遷移エッジには出力信号が付記される。例えば、入力 '0' を受けて状態1から状態2に遷移する際に、'1' が出力される（エッジには 0/1 と表示される）。一方ムーア・マシンの出力は現在状態にのみ左右され、入力には依存しない。ただし、ミーリ・マシンはムーア・マシンと等価と見なすことが出来る。ムーア・マシンの状態は、ミーリ・マシンの現在状態と一つ前の状態の直積で表される。

ミーリ・マシンという名前は提唱者であり状態機械の先駆者である G.H. ミーリ の名からきている。彼はミーリ・マシンを A Method for Synthesizing Sequential Circuitsという論文に記している（Bell System Tech. J. vol 34, pp. 1045–1079, September 1955）。

形式的定義
ミーリ・マシンは (S, Σ, Λ, T, G, s) の6要素から成り、以下の性質を持つ。
 状態の有限集合 (S)
 入力文字列の有限集合 (Σ) 
 出力文字列の有限集合 (Λ) 
 遷移関数 (T : S × Σ → S). 
 出力関数 (G : S × Σ → Λ). 
 開始状態 (s ∈ S)

例
このマシンは 1クロック遅延マシンであり、入力 x0x1...xn に対して、0x0x1...xn-1 という出力を生成する。開始状態は S0 である。

注

関連項目 
 同期回路

計算モデル
数学に関する記事