摩爾機和米利機

---

---

有限自動機可能具有與每個轉換相對應的輸出。有兩種型別的有限狀態機生成輸出 -

• 米利機
• 摩爾機

米利機

米利機是一種 FSM，其輸出取決於當前狀態以及當前輸入。

它可以用一個 6 元組 (Q, ∑, O, δ, X, q₀) 來描述，其中 -

• Q 是一個有限的狀態集。

• ∑ 是一個有限的符號集，稱為輸入字母表。

• O 是一個有限的符號集，稱為輸出字母表。

• δ 是輸入轉換函式，其中 δ: Q × ∑ → Q

• X 是輸出轉換函式，其中 X: Q × ∑ → O

• q₀ 是任何輸入都從其開始處理的初始狀態 (q₀ ∈ Q)。

米利機的狀態表如下所示 -

上述米利機的狀態圖如下所示 -

摩爾機

摩爾機是一種 FSM，其輸出僅取決於當前狀態。

摩爾機可以用一個 6 元組 (Q, ∑, O, δ, X, q₀) 來描述，其中 -

• Q 是一個有限的狀態集。

• ∑ 是一個有限的符號集，稱為輸入字母表。

• O 是一個有限的符號集，稱為輸出字母表。

• δ 是輸入轉換函式，其中 δ: Q × ∑ → Q

• X 是輸出轉換函式，其中 X: Q → O

• q₀ 是任何輸入都從其開始處理的初始狀態 (q₀ ∈ Q)。

摩爾機的狀態表如下所示 -

上述摩爾機的狀態圖如下所示 -

米利機與摩爾機

下表突出顯示了區分米利機和摩爾機的要點。

摩爾機到米利機

演算法 4

輸入 - 摩爾機

輸出 - 米利機

步驟 1 - 獲取一個空白的米利機轉換表格式。

步驟 2 - 將所有摩爾機轉換狀態複製到此表格式中。

步驟 3 - 檢查摩爾機狀態表中當前狀態及其對應的輸出；如果對於狀態 Q_i 輸出為 m，則將其複製到米利機狀態表中 Q_i 出現在下一狀態的輸出列中。

示例

讓我們考慮以下摩爾機 -

現在我們應用演算法 4 將其轉換為米利機。

步驟 1 & 2 -

步驟 3 -

米利機到摩爾機

演算法 5

輸入 - 米利機

輸出 - 摩爾機

步驟 1 - 計算米利機狀態表中每個狀態 (Q_i) 的不同輸出數量。

步驟 2 - 如果 Qi 的所有輸出都相同，則複製狀態 Q_i。如果它有 n 個不同的輸出，則將 Q_i 分成 n 個狀態，如 Q_in，其中n = 0, 1, 2.......

步驟 3 - 如果初始狀態的輸出為 1，則在開頭插入一個新的初始狀態，該狀態輸出 0。

示例

讓我們考慮以下米利機 -

這裡，狀態“a”和“d”分別只給出 1 和 0 輸出，因此我們保留狀態“a”和“d”。但是狀態“b”和“c”產生不同的輸出（1 和 0）。因此，我們將b分成b₀, b₁，並將c分成c₀, c₁。