ムーア・マシン

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ムーアモデル:エレベーター扉の制御

ムーア・マシンMoore Machine)は、出力が(入力によらず)現在の状態によってのみ決定される有限オートマトンである。ムーア・マシンの状態遷移図は各状態の出力信号を含む。一方、ミーリ・マシンはマシンの「遷移」を出力に対応付ける。

ムーア・マシンという名称は提唱者であり状態機械の先駆者エドワード・ムーアの名から来ている。ムーアは Gedanken-experiments on Sequential Machines,(順序機械の思考実験)でムーア・マシンについて記述している(pp 129 – 153, Automata Studies, Annals of Mathematical Studies, no. 34, Princeton University Press, Princeton, N. J., 1956)。

多くの電子機器は順序論理で設計されている。順序論理はムーア・マシンの限定された形態であり、状態はクロック信号が変化したときのみ変化する。一般に、現在状態はフリップフロップに格納され、クロック信号はフリップフロップのクロック入力に接続される。クロック同期システムは準安定性問題を解決する方法のひとつである。

典型的な電子的ムーア・マシンは組合わせ論理の連結によって現在状態から出力にデコードを行う。状態が変化すると、その回路の通じて即座に出力も変化する(変化しない場合もある)。設計上の技法として出力が変化する際に不正な中間的出力が発生しないようにする必要がある。一般には出力を利用する側もクロック同期して中間的な不正な出力は無視される。出力はムーア・マシンの状態が変化しない限りそのままである(LEDは点灯したまま、モーターは回転したまま、など)。

形式的定義[編集]

ムーア・マシンは { S, Σ, Λ, T, G, q_0, F } の7要素から構成され、以下の性質を持つ。

  • 状態の有限集合 ( S )
  • 入力文字の有限集合 ( Σ )
  • 出力文字の有限集合 ( Λ )
  • 遷移関数 (T : S × Σ → S) は状態と入力から次の状態を導く。
  • 出力関数 (G : S → Λ) は状態から出力文字を導く。
  • 開始状態 ( q_0 )
  • 完了状態の集合 F

ムーア・マシンの状態数は、同等機能のミーリ・マシンの状態数より多い(あるいは同数)。

外部リンク[編集]