米利型有限狀態機

一個簡單Mealy機的狀態圖

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

名源

Mealy machine的名字來自這個概念的提出者，在1951年寫了A Method for Synthesizing Sequential Circuits的狀態機的先驅G. H. Mealy。

運作機制

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

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

形式定義

Mealy機是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.