TOC中的Mealy和Moore机器

摩尔机器： 摩尔机器是具有输出值的有限状态机器，其输出仅取决于当前状态。它可以定义为（Q，q0， ∑, O、 δ，λ）式中：

• Q是有限状态集。
• q0是初始状态。
• ∑ 是输入字母表。
• O是输出字母表。
• δ是映射Q×的转移函数 ∑ →问。
• λ是映射Q的输出函数→O。

在图1所示的摩尔机器中，输出用每个输入状态表示，每个输入状态之间用/。摩尔机器的输出长度大于输入长度1。

• 输入： 11
• 过渡： δ（q0,11）=>δ（q2,1）=>q2
• 输出： 000（q0为0，q2为0，q2为0）

米利机器： Mealy机器也是具有输出值的有限状态机器，其输出取决于当前状态和当前输入符号。它可以定义为（Q，q0， ∑, O、 δ，λ’，其中：

• Q是有限状态集。
• q0是初始状态。
• ∑ 是输入字母表。
• O是输出字母表。
• δ是映射Q×的转移函数 ∑ →问。
• “λ”是映射Q×的输出函数 ∑ →O。

在图1所示的mealy机器中，输出用每个状态的每个输入符号表示，每个输入符号之间用/。粉碎机的输出长度等于输入长度。

• 输入： 11
• 过渡： δ（q0,11）=>δ（q2,1）=>q2
• 输出： 00（q0到q2的转换有输出0，而q2到q2的转换也有输出0）

从Mealy到Moore机器的转换

让我们以图2所示的mealy机器的过渡表为例。

表1

第一步。 首先找出那些有超过1个输出与之关联的状态。q1和q2是同时具有输出0和1的状态。

第二步。 为这些状态创建两个状态。对于q1，两个状态将是q10（输出为0的状态）和q11（输出为1的状态）。类似地，对于q2，两个状态将是q20和q21。

第三步。 用新生成的状态创建一个空的moore机器。对于摩尔机器，输出将与每个状态相关联，而与输入无关。

表2

第四步。 使用表1所示的mealy机器转换表填写下一个状态的条目。对于输入0上的q0，下一个状态是q10（q1带有输出0）。类似地，对于输入1上的q0，下一个状态是q20（输出为0的q2）。对于输入0上的q1（q10和q11），下一个状态是q10。类似地，对于q1（q10和q11），下一个状态是q21。q10的产量为0，q11的产量为1。同样，也可以填写其他条目。

表3

这是摩尔机器的转换表，如图1所示。

从摩尔机器到米利机器的转换

让我们以图1中的摩尔机器为例，其转换表如表3所示。

第一步。 如表4所示，使用摩尔机器的所有状态建造一台空的米利机器。

表4

第二步： 每个状态的下一个状态也可以直接从摩尔机器转换表中找到，如下所示：

表5

第三步： 正如我们在摩尔机器转换表中看到的每个输入对应的输出。使用此选项填充输出条目。例如。；与q10、q11、q20和q21对应的输出分别为0、1、0和1。

表6

第4步： 从表6可以看出，q10和q11彼此相似（下一状态的值和不同输入的输出相同）。同样，q20和q21也很相似。因此，q11和q21可以消除。

表7

这是表1所示的同一台米利机器。所以我们把米利变成了摩尔机器，把摩尔变成了米利。

注： mealy机器中的状态数不能大于moore机器中的状态数。

例子： 以下状态图描述的有限状态机，以A为起始状态，其中弧标签为x/y，x代表1位输入，y代表2位输出？

输出输入的当前位和前一位的总和。

1. 当输入序列包含11时，输出01。
2. 当输入序列包含10时，输出00。
3. 这些都没有。

解决方案： 让我们获取不同的输入及其输出，并检查哪个选项有效：

输入： 01

输出： 00 01（对于0，输出为00，状态为A。对于1，输出为01，状态为B）

输入： 11

输出： 01 10（对于1，输出为01，状态为B。对于1，输出为10，状态为C）

正如我们所见，它给出了当前位和前一位的二进制和。对于第一位，前一位为0。

本文由 奏鸣曲 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论