米利型有限狀態機

在計算理論中，米利型有限狀態機（英語：Mealy machine）是基於它的當前狀態和輸入生成輸出的有限狀態自動機（更精確的叫有限狀態變換器）。這意味着它的狀態圖將為每個轉移邊包括輸入和輸出二者。與輸出只依賴於機器當前狀態的摩爾有限狀態機不同，它的輸出與當前狀態和輸入都有關。但是對於每個米利機都有一個等價的摩爾機，該等價的摩爾機的狀態數量上限是所對應米利機狀態數量和輸出數量的乘積加1（|S'|=|S|*|Λ|+1）。

一個簡單Mealy機的狀態圖

名源

米利機的名字來自這個概念的提出者，在1951年寫了《A Method for Synthesizing Sequential Circuits》的狀態機的先驅喬治·H·米利。^[1]

運作機制

米利機提供了密碼機的一個根本的數學模型。例如考慮拉丁字母表的輸入和輸出，一個米利機可以被設計用來把給定字母的字符串（一序列輸入）處理成密碼字符串（一序列輸出）。但是，儘管你可能使用米利模型來描述恩尼格瑪密碼機，狀態圖對於提供設計複雜密碼機的靈活方式而言太複雜了。

米利狀態機與摩爾有限狀態機不同，米利有限狀態機的輸出不單與當前狀態有關，而且與輸入訊號的當前值有關。米利有限狀態機的輸出直接受輸入訊號的當前值影響，而輸入訊號可能在一個時鐘周期內任意時刻變化，這使得米利有限狀態機對輸入的響應發生在當前時鐘周期，比Moore有限狀態機對輸入訊號的響應要早一個周期。因此，輸入訊號的雜訊可能影響在輸出的訊號。

形式定義

米利機是6-元組（S, S₀, Σ, Λ, T, G），構成自：

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

在某些表述中，轉移函數和輸出函數被合併為一個單一函數 ${\displaystyle T:S\times \Sigma \rightarrow S\times \Lambda }$.

「隨時間演化」的概念在此抽象中通過狀態機在離散的「計時器滴答」時刻查詢隨時間變化的輸入符號得以實現，這些時刻記為 ${\displaystyle t_{0},t_{1},t_{2},...}$ ，狀態機根據這些理想化瞬間的內部配置作出響應，或者等待下一個輸入符號（如先進先出隊列）並在其到達時作出反應。

與摩爾有限狀態機的比較

1. 米利機通常具有更少的狀態數：
   • 其輸出變化體現在轉移弧上（n²種可能），而非狀態節點上（僅需n種狀態）。
2. 當作為電子電路實現時（而非數學抽象或代碼形式）：
   • 摩爾機比米利機使用更安全：
     • 輸出變化始終發生在時鐘邊沿（總是延遲一個周期）。
     • 米利機中，輸入變化會立即通過邏輯電路影響輸出——當多台機器互聯時可能引發嚴重問題，若不謹慎設計會導致異步反饋。
   • 米利機對輸入響應更快：
     • 同一時鐘周期內即可響應——無需等待時鐘觸發。
     • 摩爾機可能需要更多邏輯電路將狀態解碼為輸出——時鐘邊沿後需經歷更多門延遲。

參見

• 有限狀態機
• 摩爾型有限狀態機

引用