米利型有限狀態機

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

一個簡單Mealy機的狀態圖

名源

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

運作機制

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

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

形式定義

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

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

參見

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

引用

參考文獻

• Mealy, GH. A Method to Synthesizing Sequential Circuits. Bell System Technical J. 1955: 1045–1079. 

• Roth, Charles H., Jr. Fundamentals of Logic Design. Thomson-Engineering. 2004: 364-367. ISBN 0534378048.