Automata Theory 简明教程

Moore and Mealy Machines

有限自动机可以有对应于每个转换的输出。有两种类型的产生输出的有限状态机 -

  1. Mealy Machine

  2. Moore machine

Mealy Machine

Mealy 机是一种 FSM，其输出取决于当前状态以及当前输入。

它可以用 6 元组 (Q，∑，O，δ，X，q0) 来描述，其中 -

  1. Q 是一个有限的状态集。

  2. ∑ 是一个称为输入字母表的有限的符号集。

  3. O 是一个称为输出字母表的有限的符号集。

  4. δ 是输入转换函数，其中 δ：Q × ∑ → Q

  5. X 是输出转换函数，其中 X：Q × ∑ → O

  6. q0 是处理任何输入的初始状态 (q0 ∈ Q)。

Mealy 机的状态表如下所示 -

Present state

Next state

input = 0

input = 1

State

Output

State

Output

→

b

x1

c

x1

b

b

x2

d

x3

c

d

x3

c

x1

d

d

x3

d

x2

上述 Mealy 机的状态图如下 -

state diagram of mealy machine

Moore Machine

Moore 机是一种 FSM，其输出仅取决于当前状态。

摩尔机可以用 6 元组 (Q, ∑, O, δ, X, q0) 来描述，其中 -

  1. Q 是一个有限的状态集。

  2. ∑ 是一个称为输入字母表的有限的符号集。

  3. O 是一个称为输出字母表的有限的符号集。

  4. δ 是输入转换函数，其中 δ：Q × ∑ → Q

  5. X 是输出转换函数，其中 X: Q → O

  6. q0 是处理任何输入的初始状态 (q0 ∈ Q)。

摩尔机的状态表如下所示 -

Present state

Next State

Output

Input = 0

Input = 1

→

b

c

x2

b

b

d

x1

c

c

d

x2

d

d

d

x3

上述 Moore 机的状态图是 −

moore machine state diagram

Mealy Machine vs. Moore Machine

下表重点介绍了 Mealy 机与 Moore 机之间的不同点。

Mealy Machine

Moore Machine

输出既取决于当前状态，又取决于当前输入

输出仅取决于当前状态。

通常，它比 Moore 机状态更少。

通常，它比 Mealy 机状态更多。

输出函数的值是转化的函数，以及当对当前状态进行输入逻辑时变化。

输出函数的值是电流状态与时钟沿变化的函数，每当发生状态变化时。

Mealy 机对输入反应较快。它们通常在同一个时钟周期里做出反应。

在 Moore 机中，需要更多的逻辑来对输出进行解码，这会导致更多的电路延迟。它们通常在下一个时钟周期才做出反应。

Moore Machine to Mealy Machine

Algorithm 4

Input − Moore 机

Output − Mealy 机

Step 1 − 采用一个空白的 Mealy 机转移状态表格式。

Step 2 − 将所有 Moore 机转移状态复制到此表格式中。

Step 3 − 检查 Moore 机状态表中的当前状态及其相应的输出；如果某个状态 Q 的输出为 m，将其复制到 Mealy 机状态表输出栏，Qi 出现于下一个状态的任何地方。

Example

让我们考虑以下 Moore 机 −

Present State

Next State

Output

a = 0

a = 1

→

d

b

1

b

a

d

0

c

c

c

0

d

b

a

1

现在我们将算法 4 应用于将其转换到 Mealy 机。

Step 1 & 2 −

Present State

Next State

a = 0

a = 1

State

Output

State

Output

→

d

b

b

a

d

c

c

c

d

b

a

Step 3 -

Present State

Next State

a = 0

a = 1

State

Output

State

Output

⇒

d

1

b

0

b

a

1

d

1

c

c

0

c

0

d

b

0

a

1

Mealy Machine to Moore Machine

Algorithm 5

Input − Mealy 机

Output − 穆尔机

Step 1 − 计算 Mealy 机状态表中每个状态 (Qi) 可用不同输出数。

Step 2 − 如果 Qi 的所有输出相同，复制状态 Qi。如果它有 n 个不同的输出，将 Qi 分解为 n 个状态，其中 Qin n = 0, 1, 2…​…​。

Step 3 − 如果初始状态的输出为 1，在开头插入一个新的初始状态，其输出为 0。

Example

让我们考虑一下以下 Mealy 机 −

Present State

Next State

a = 0

a = 1

Next State

Output

Next State

Output

→

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 。

Present State

Next State

Output

a = 0

a = 1

→

d

b1

1

b0

a

d

0

b1

a

d

1

c0

c1

C0

0

c1

c1

C0

1

d

b0