ミーリーマシン

計算理論において、ミーリーマシンは、出力値が現在の状態と現在の入力の両方によって決定される有限状態マシンです。これは、出力値が現在の状態のみによって決定されるムーアマシンとは対照的です。ミーリーマシンは決定論的な有限状態トランスデューサです。つまり、各状態と入力に対して、最大で 1 つの遷移が可能です。

ミーリーマシンは、1955年の論文「順次回路の合成法」で概念を発表したジョージ・H・ミーリーにちなんで名付けられました。 ^[1]

Mealy マシンは、次の 6 要素から構成されるタプルです。 ${\displaystyle (S,S_{0},\Sigma ,\Lambda ,T,G)}$

• 有限の状態集合 ${\displaystyle S}$
• 開始状態（初期状態とも呼ばれる）は、${\displaystyle S_{0}}$${\displaystyle S}$
• 入力アルファベットと呼ばれる有限集合 ${\displaystyle \Sigma }$
• 出力アルファベットと呼ばれる有限集合 ${\displaystyle \Lambda}$
• 状態と入力シンボルのペアを対応する次の状態にマッピングする遷移関数。 ${\displaystyle T:S\times \Sigma \rightarrow S}$
• 状態と入力シンボルのペアを対応する出力シンボルにマッピングする出力関数。${\displaystyle G:S\times \Sigma \rightarrow \Lambda }$

いくつかの定式化では、遷移関数と出力関数が 1 つの関数に結合されます。 ${\displaystyle T:S\times \Sigma \rightarrow S\times \Lambda }$

この抽象化では、状態マシンが離散的な「タイマー ティック」で時間変化する入力シンボルを参照し、それらの理想的な瞬間に内部構成に従って反応するか、状態マシンが次の入力シンボル (FIFO の場合など) を待機し、それが到着するたびに反応することによって、「時間にわたる進化」が実現されます。 ${\displaystyle t_{0},t_{1},t_{2},...}$

1. Mealy マシンは状態数が少ない傾向があります。
   • 状態 ( n )ではなく、弧 ( n ² )上の異なる出力。
2. 電子回路として実装する場合（数学的抽象化やコードとしてではなく）：
   • ムーア マシンはミーリー マシンよりも安全に使用できます。
     • 出力はクロック エッジで変化します (常に 1 サイクル後)。
     • Mealy マシンでは、入力の変更によってロジックが完了するとすぐに出力が変化する可能性があります。これは、2 台のマシンが相互接続されている場合に大きな問題となり、注意しないと非同期フィードバックが発生する可能性があります。
   • Mealy マシンは入力に対してより速く反応します。
     • 同じサイクルで反応します。時計を待つ必要はありません。
     • ムーア マシンでは、状態を出力にデコードするために、より多くのロジック (クロック エッジ後のゲート遅延の増加) が必要になる場合があります。

Mealy マシンの状態図では、各遷移エッジに出力値が関連付けられます。これは、各状態に出力値が関連付けられる Moore マシンの状態図とは対照的です。

入力と出力のアルファベットが両方ともΣの場合、 Mealy オートマトンにらせん有向グラフ[^要説明] ( S × Σ, ( x , i ) → ( T ( x , i ), G ( x , i ) ))を関連付けることもできます。^[2]このグラフは、状態と文字のペアを頂点として持ち、各ノードは出力次数が 1 で、( x , i )の後続ノードは、オートマトンが状態xで文字i を読み取るときに出力する文字と、オートマトンが次の状態になります。このグラフは、オートマトンが双可逆である場合、互いに素なサイクルの和集合です^[要定義]。

シンプルな Mealy マシンには、1 つの入力と 1 つの出力があります。各遷移エッジには、入力値 (赤で表示) と出力値 (青で表示) のラベルが付けられます。マシンは状態S _iから開始します。(この例では、出力は最新の 2 つの入力値の排他的論理和です。したがって、マシンはエッジ検出器を実装し、入力が反転するたびに 1 を出力し、それ以外の場合は 0 を出力します。)

より複雑な Mealy マシンは、複数の入力と複数の出力を持つことができます。^{[引用が必要]}

Mealy マシンは、暗号マシンの基本的な数学モデルを提供します。たとえば、入力と出力のアルファベットをラテン アルファベットとすると、文字列 (入力シーケンス) を暗号化文字列 (出力シーケンス) に処理できる Mealy マシンを設計できます。ただし、Mealy モデルを使用して Enigma を記述することはできますが、状態図が複雑すぎるため、複雑な暗号マシンを設計する現実的な手段を提供することはできません。

ムーア/ミーリー マシンは、クロックの任意のタイミングで出力を行うDFAです。現代の CPU、コンピューター、携帯電話、デジタル時計、基本的な電子機器/マシンには、制御するための何らかの有限状態マシンが搭載されています。

単純なソフトウェア システム、特に正規表現を使用して表現できるシステムは、有限状態マシンとしてモデル化できます。自動販売機や基本的な電子機器など、このような単純なシステムは数多くあります。

2 つの有限状態マシンの交差点を見つけることで、たとえばメッセージを交換する並行システムを非常に簡単な方法で設計できます。たとえば、信号機は、同時に動作するさまざまな信号機などの複数のサブシステムで構成されるシステムです。

アプリケーションの例:

• 番号分類
• タイマー付き時計
• 自販機
• 信号機
• バーコードスキャナー
• ガソリンポンプ

• 同期回路
• ムーアマシン
• アルゴリズムステートマシン
• リチャーズコントローラー

• Mealy, George H. (1955)。「シーケンシャル回路の合成法」、Bell System Technical Journal、pp. 1045–1079。
• ホルコム、WML (1982)。代数オートマトン理論。ケンブリッジ高等数学研究第1巻。ケンブリッジ大学出版局。ISBN 0-521-60492-3.ZBL 0489.68046  .
• Roth, Charles H. Jr. (2004).ロジックデザインの基礎. Thomson-Engineering. pp. 364–367. ISBN 0-534-37804-8。
• Akhavi, Ali; Klimann, Ines; Lombardy, Sylvain; Mairesse, Jean; Picantin, Matthieu (2012). 「オートマトン (半) 群の有限性問題について」. International Journal of Algebra and Computation . 22 (6). arXiv : 1105.4725 . Bibcode :2011arXiv1105.4725A. doi :10.1142/S021819671250052X. S2CID  47518684. Zbl  1280.20038.

• ウィキメディア・コモンズの Mealy マシンに関連するメディア