设计一个用于处理二进制输入序列的 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+ 浏览量

启动你的职业生涯

通过完成课程获得认证

开始学习