ミーリ・マシン

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

ミーリ・マシン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 × Σ → Λ).
  • 開始状態 (sS)

[編集]

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

状態遷移図

関連項目[編集]