摩尔机和米利机

---

---

有限自动机可能具有与每个转换相对应的输出。有两种类型的有限状态机生成输出 -

• 米利机
• 摩尔机

米利机

米利机是一种 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₁。