摩尔机和米利机
有限自动机可能有与每次转换相对应的输出。有两种类型的有限状态机可生成输出 −
- Mealy 米利机
- Moore 摩尔机
Mealy 米利机
Mealy 机是一种 FSM，其输出取决于当前状态以及当前输入。
它可以用 6 元组 (Q, ∑, O, δ, X, q0) 来描述，其中 −
Q 是一组有限的状态。
∑ 是一组有限的符号，称为输入字母表。
O 是一组有限的符号，称为输出字母表。
δ 是输入转换函数，其中 δ: Q × ∑ → Q
X 是输出转换函数，其中 X: Q × ∑ → O
q0 是处理任何输入的初始状态 (q0 ∈ Q)。
Mealy 机的状态表如下所示 −
| 当前状态 | 下一个状态 | |||
|---|---|---|---|---|
| 输入 = 0 | 输入 = 1 | |||
| 状态 | 输出 | 状态 | 输出 | |
| → a | b | x1 | c | x1 |
| b | b | x2 | d | x3 |
| c | d | x3 | c | x1 |
| d | d | x3 | d | x2 |
上述 Mealy 机的状态图为 −
Moore 机
Moore 机是一种 FSM，其输出仅取决于当前状态。
Moore 机可以用 6 元组 (Q, ∑, O, δ, X, q0) 来描述，其中 −
Q 是一组有限的状态。
∑ 是一组有限的符号，称为输入字母表。
O 是一组有限的符号，称为输出字母表。
δ 是输入转换函数，其中 δ: Q × ∑ → Q
X 是输出转换函数，其中 X: Q → O
q0 是处理任何输入的初始状态 (q0 ∈ Q)。
摩尔机的状态表如下所示 −
| 当前状态 | 下一个状态 | 输出 | |
|---|---|---|---|
| 输入 = 0 | 输入 = 1 | ||
| → a | b | c | x2 |
| b | b | d | x1 |
| c | c | d | x2 |
| d | d | d | x3 |
上述 Moore 机的状态图为 −
Mealy 机与 Moore 机
下表重点介绍了 Mealy 机与 Moore 机的区别。
| Mealy 机 | Moore 机 |
|---|---|
| 输出取决于当前状态和当前输入 | 输出仅取决于当前状态。 |
| 通常，它的状态比 Moore 机少。 | 通常，它具有比 Mealy 机具有更多的状态。 |
| 当对当前状态进行输入逻辑时，输出函数的值是转换和变化的函数。 | 当状态发生变化时，输出函数的值是当前状态和时钟边缘变化的函数。 |
| Mealy 机对输入的反应更快。它们通常在同一个时钟周期内做出反应。 | 在 Moore 机中，需要更多逻辑来解码输出，从而导致更多的电路延迟。它们通常会在一个时钟周期后做出反应。 |
Moore 机到 Mealy 机
算法 4
输入 − Moore 机
输出 − Mealy 机
步骤 1 − 取一个空白的 Mealy 机转换表格式。
步骤 2 − 将所有 Moore 机转换状态复制到此表格式中。
步骤 3 − 检查 Moore 机状态表中的当前状态及其对应的输出；如果对于状态 Qi 输出为 m，则将其复制到 Mealy 机状态表的输出列中，无论 Qi 出现在下一个状态中的位置如何。
示例
让我们考虑以下 Moore 机 −
| 当前状态 | 下一个状态 | 输出 | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | d | b | 1 |
| b | a | d | 0 |
| c | c | c | 0 |
| d | b | a | 1 |
现在我们应用算法 4 将其转换为 Mealy 机。
步骤 1 和 2 −
| 当前状态 | 下一个状态 | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| 状态 | 输出 | 状态 | 输出 | |
| → a | d | b | ||
| b | a | |||
| c | c | c | ||
| d | b | a | ||
步骤 3 −
| 当前状态 | 下一个状态 | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| 状态 | 输出 | 状态 | 输出 | |
| => a | d | 1 | b | 0 |
| b | a | 1 | d | 1 |
| c | c | 0 | c | 0 |
| d | b | 0 | a | 1 |
Mealy 机到 Moore 机
算法 5
输入 − Mealy 机
输出 − Moore 机
步骤 1 − 计算 Mealy 机状态表中每个状态 (Qi) 的不同输出数量。
步骤 2 − 如果 Qi 的所有输出都相同，则复制状态 Qi。如果它有 n 个不同的输出，则将 Qi 拆分为 n 个状态，即 Qin，其中 n = 0, 1, 2.......
步骤 3 −如果初始状态的输出为 1，则在开头插入一个新的初始状态，该状态输出为 0。
示例
让我们考虑以下 Mealy 机 −
| 当前状态 | 下一个状态 | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| 下一个状态 | 输出 | 下一个状态 | 输出 | |
| → a | d | 0 | b | 1 |
| b | a | 1 | d | 0 |
| c | c | 1 | c | 0 |
| d | b | 0 | a | 1 |
这里，状态"a"和"d"分别只给出 1 和 0 的输出，因此我们保留状态"a"和"d"。但状态"b"和"c"产生不同的输出（1 和 0）。因此，我们将 b 分为 b0、b1，将 c 分为 c0、c1。
| 当前状态 | 下一个状态 | 输出 | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | d | b1 | 1 |
| b0 | a | d | 0 |
| b1 | a | d | 1 |
| c0 | c1 | C0 | 0 |
| c1 | c1 | C0 | 1 |
| d | b0 | a | 0 |
