摩爾型有限狀態機

在計算理論中，摩爾型有限狀態機（英語：Moore machine）是指輸出只由當前的狀態所確定的有限狀態自動機。摩爾型有限狀態機的狀態圖對每個狀態包含一個輸出信號，相對於米利型有限狀態機，它映射機器中的「轉移」到輸出。

摩爾型有限狀態機的名字來自它的提出者，寫了《Gedanken-experiments on Sequential Machines》的狀態機先驅愛德華·F·摩爾。^[1]

運作機制

多數數字電子系統被設計為時序系統。時序系統是受限制形式的摩爾型有限狀態機，它的狀態只在全局時鐘信號改變的時候改變。當前狀態典型的存儲在觸發器中，而全局時鐘信號連接到觸發器的「時鐘」輸入上。時序系統是解決亞穩定性問題的一種方法。典型的摩爾型有限狀態機包括組合邏輯鏈來把當前狀態解碼為輸出（lambda）。當前狀態一旦改變，這種改變通過這些鏈傳播，幾乎立即導致輸出改變（或不改變）。有確保在這些變化在沿着鏈傳播這段短暫時期在輸出上不出現glitch的技術，但是設計出的大多數系統都忽略在短暫的轉移時間的冒險。輸出接着停留同樣不確定（LED保持點亮，電力保持連接到電機等等），直到摩爾機再次改變狀態。

摩爾型有限狀態機的輸出只與有限狀態自動機的當前狀態有關，與輸入信號的當前值無關。摩爾型有限狀態機在時鐘脈衝的有效邊沿後的有限個門延後，輸出達到穩定值。即使在一個時鐘周期內輸入信號發生變化，輸出也會在一個完整的時鐘周期內保持穩定值而不變。輸入對輸出的影響要到下一個時鐘周期才能反映出來。摩爾型有限狀態機最重要的特點就是將輸入與輸出信號隔離開來。

形式定義

摩爾機形式定義為6-元組{ S, S₀, Σ, Λ, T, G }，構成如下：

狀態的有限集合（S）
開始狀態（也叫做初始狀態）S₀，它是S的元素
叫做輸入字母表的有限集合（Σ）
叫做輸出字母表的有限集合（Λ）
映射狀態和輸入到下一個狀態的轉移函數（T : S × Σ → S）
輸出函數（G : S → Λ）映射每個狀態到輸出字母表

在摩爾機中的狀態的數目大於等於在對應的Mealy機中狀態的數目。

參見

引用

註釋

^ Moore, Edward F. Gedanken-experiments on Sequential Machines. Automata Studies,Annals of Mathematical Studies (Princeton, N.J.: Princeton University Press). 1956, (34): 129–153.

參考文獻

Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, N.J.（1956）。
Karatsuba A. A. Solution of one problem from the theory of finite automata. Usp. Mat. Nauk, 15:3, 157–159（1960）。
Karacuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612（1975）。
Karatsuba A. A. List of research works （頁面存檔備份，存於網際網路檔案館）

[1] Moore, Edward F. Gedanken-experiments on Sequential Machines. Automata Studies,Annals of Mathematical Studies (Princeton, N.J.: Princeton University Press). 1956, (34): 129–153.

[1]