設計一個用於處理二進位制輸入序列的 Moore 機。

問題

設計一個 Moore 機，用於處理二進位制輸入序列。如果序列包含子串 "101"，則輸出 A；如果包含子串 "110"，則輸出 B；否則輸出 C。

解答

為了設計這樣的機器，我們將檢查兩個條件："101" 和 "110"。如果檢測到 "101"，則輸出 A；如果檢測到 "110"，則輸出 B；對於其他字串，輸出 C。

Moore 機有 6 個元組

(Q, q0, Σ, O, δ, λ)

其中：

• Q：有限狀態集
• q0：初始狀態
• Σ：有限輸入符號集
• O：輸出字母表
• δ：狀態轉移函式，Q × Σ → Q
• λ：輸出函式，Q → O

部分狀態圖如下所示：

示例 1

現在，我們將為每個狀態插入 0 和 1 的可能性。

因此，Moore 機如下所示：

解釋

• **步驟 1** - q0 是起始狀態，輸入 '0' 轉到 q0，輸入 '1' 轉到 q1，輸出 C。
• **步驟 2** - q1，輸入 '0' 轉到 q2，輸入 '1' 轉到 q4，輸出 C。
• **步驟 3** - q2，輸入 '0' 轉到 q0，輸入 '1' 轉到 q3，輸出 C。
• **步驟 4** - q3，輸入 '0' 轉到 q0，輸入 '1' 轉到 q4，輸出 A。
• **步驟 5** - q4，輸入 '0' 轉到 q5，輸入 '1' 轉到 q4，輸出 C。
• **步驟 6** - q5，輸入 '1' 轉到 q3，輸出 B。

示例 2

構建一個 Moore 機，對於輸入字串 "bababbb"，輸出為 "01100100"。

輸入字母表 - Σ = {a, b}

輸出字母表 - Γ = {0, 1}

狀態 - q0, q1, q2, q3

狀態轉移表

狀態轉移表如下所示：

狀態轉移圖

狀態轉移圖如下所示：

Bhanu Priya

更新於：2021年6月12日

13K+ 瀏覽量

啟動你的職業生涯

透過完成課程獲得認證

開始學習