摩爾型有限狀態機

在計算理論中，摩爾機器有限狀態機，其輸出值僅由其當前狀態確定。 這與Mealy機器形成對比，Mealy機器的輸出值由其當前狀態和輸入值決定。 摩爾機器以愛德華·摩爾（Edward F. Moore）的名字命名，他在1956年的論文“Gedanken-在順序機器上進行實驗”中提出了這一概念。

基本介紹

• 中文名：摩爾型有限狀態機
• 外文名：Moore type finite state machine
• 提出者：Edward F. Moore
• 提出時間：1956

定義

摩爾機器可以定義為6元組 由下列：

一組有限的狀態；

起始狀態（也稱為初始狀態） ，它是 的元素；

有限集稱為輸入字母；

有限集稱為輸出字母；

轉換函式 將狀態和輸入字母映射到下一個狀態；

輸出函式 將每個狀態映射到輸出字母表。

摩爾機器可以被視為限制類型的有限狀態換能器。

可視化表示

表

圖一

狀態轉換表是顯示輸入和狀態之間關係的表。

圖

Moore機器或Moore圖的狀態圖是將輸出值與每個狀態相關聯的圖。 摩爾機器是一個輸出生產者。

與Mealy機器的關係

由於Moore和Mealy機器都是有限狀態機的類型，它們同樣具有表現力：任何一種類型都可以用來解析常規語言。

Moore機器和Mealy機器之間的區別在於，在後者中，轉換的輸出由當前狀態和當前輸入的組合決定（ 作為 的輸入），而不僅僅是當前狀態（ 作為 的輸入）。當表示為狀態圖時，

對於Moore機器，每個節點（狀態）都標有輸出值;

對於Mealy機器，每個弧（過渡）都標有輸出值。

每個摩爾機器 等同於具有相同狀態和轉換的Mealy機器和輸出函式 ，它接受每個狀態輸入對 並產生 ，其中 是 的輸出函式。

但是，並非每台Mealy機器都可以轉換為等效的摩爾機器。有些只能轉換為幾乎等效的摩爾機器，輸出時間會發生變化。這是由於狀態標籤與轉換標籤配對以形成輸入/輸出對的方式。考慮從州 到州 的轉換 。導致轉換的輸入 標記邊 。與該輸入對應的輸出是狀態標籤 。請注意，這是轉換的源狀態。因此，對於每個輸入，輸出在接收輸入之前已經固定，並且僅取決於當前狀態。這是E. Moore的原始定義。使用狀態 的標籤作為轉換 的輸出是一個常見的錯誤。

樣例

根據輸入/輸出的數量類型。

簡單摩爾機器

簡單的摩爾機器有一個輸入和一個輸出：

• 邊緣檢測器使用XOR
  
• 二進制添加機器
  
• 時鐘序列系統（限制形式的摩爾機器，其中狀態僅在全局時鐘信號改變時改變）
  

大多數數字電子系統設計為時鐘順序系統。時鐘順序系統是Moore機器的受限形式，其中狀態僅在全局時鐘信號改變時改變。通常，當前狀態存儲在觸發器中，並且全局時鐘信號連線到觸發器的“時鐘”輸入。時鐘順序系統是解決亞穩態問題的一種方法。典型的電子摩爾機器包括組合邏輯鏈，用於將當前狀態解碼為輸出（λ）。當前狀態發生變化的瞬間，這些變化會波及該鏈，並且幾乎瞬間輸出會更新。有一些設計技術可確保在短暫的時間內輸出上不會出現毛刺，而這些變化正在通過鏈條波動，但大多數系統的設計使得在短暫的轉換時間內的毛刺被忽略或無關緊要。然後輸出無限期保持不變（LED保持亮，電源保持與電機連線，電磁閥保持通電等），直到Moore機器再次改變狀態。

運行實例

順序網路有一個輸入和一個輸出。 當至少有兩個0和兩個1作為輸入時，輸出變為1並且此後保持為1。

圖二顯示了具有上述描述的九種狀態的摩爾機器。 初始狀態為狀態A，最終狀態為狀態I.此示例的狀態如圖三：

圖二

圖三

複雜摩爾機器

複雜的摩爾機器可以有多個輸入和多個輸出。