摩爾型有限狀態機

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

x, y, z作為輸入和a, b, c作為輸出的摩爾機狀態圖

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

運作機制

編輯

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

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

形式定義

編輯

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

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

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

參見

編輯

引用

編輯

註釋

編輯
  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. 

參考文獻

編輯
  • 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頁面存檔備份,存於網際網路檔案館