ミーリ・マシン

ウィキペディア

ミーリ・マシン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2010/08/09 21:14 UTC 版)

ミーリ・マシン（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クロック遅延マシンであり、入力 x₀x₁...x_n に対して、0x₀x₁...x_n-1 という出力を生成する。開始状態は S₀ である。

関連項目

• 同期回路

ウィキペディア小見出し辞書

ミーリ・マシン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/14 04:59 UTC 版)

「有限オートマトン」の記事における「ミーリ・マシン」の解説

この有限オートマトンは入力動作のみを使用する。すなわち、出力は入力と状態に依存する。ミーリ・モデルは状態の数を減らす作用がある。図7の例はムーア・マシンの例と同じものをミーリ・マシンで実装したものを示している（実装された有限オートマトンのふるまいは実行モデルに依存する。例えば仮想有限状態機械（英語版）では動作するが、イベント駆動有限状態機械（英語版）では動作しない）。これは二つの入力動作を持つ。「閉鎖命令が来たら扉を閉めるためにモーターを起動する」という入力動作と「開放命令が来たら扉を開けるためにモーターを起動する」という入力動作である。