[科普中国]-米利型有限状态机

在计算理论中，米利型有限状态机（英语：Mealy machine）是基于它的当前状态和输入生成输出的有限状态自动机（更精确的叫有限状态变换器）。这意味着它的状态图将为每个转移边包括输入和输出二者。与输出只依赖于机器当前状态的摩尔有限状态机不同，它的输出与当前状态和输入都有关。但是对于每个Mealy机都有一个等价的Moore机，该等价的Moore机的状态数量上限是所对应Mealy机状态数量和输出数量的乘积加1。

简介Mealy machine的名字来自这个概念的提出者，在1951年写了A Method for Synthesizing Sequential Circuits的状态机的先驱G. H. Mealy。1

运作机制Mealy机提供了密码机的一个根本的数学模型。例如考虑拉丁字母表的输入和输出，一个Mealy机可以被设计用来把给定字母的字符串（一序列输入）处理成密码字符串（一序列输出）。但是，尽管你可能使用Mealy模型来描述恩尼格玛密码机，状态图对于提供设计复杂密码机的灵活方式而言太复杂了。

Mealy状态机与Moore有限状态机不同，Mealy有限状态机的输出不单与当前状态有关，而且与输入信号的当前值有关。Mealy有限状态机的输出直接受输入信号的当前值影响，而输入信号可能在一个时钟周期内任意时刻变化，这使得Mealy有限状态机对输入的响应发生在当前时钟周期，比Moore有限状态机对输入信号的响应要早一个周期。因此，输入信号的噪声可能影响在输出的信号。

形式定义 Mealy机是6-元组，构成自：

状态的有限集合

开始状态（也叫做初始状态） ，它是 的元素

叫做输入字母表的有限集合

叫做输出字母表的有限集合

转移函数

输出函数

在某些公式中，转换和输出函数合并为单个函数 。

Mealy机和摩尔机的比较1.Mealy机器的规定往往较少：

弧（n2）而不是状态（n）的不同输出。

2.摩尔机器使用更安全：

输出在时钟边沿变化（总是在一个周期后）。

在Mealy机器中，输入更改可能会在逻辑完成后立即导致输出更改 - 当两台机器互连时出现大问题 - 如果不小心，可能会发生异步反馈。

3.Mealy机器对输入的反应更快：

在相同的周期内反应 - 不需要等待时钟。

在Moore机器中，可能需要更多逻辑来将状态解码为输出 - 在时钟边沿之后更多的门延迟。

并非所有时序电路都可以使用Mealy模型实现。 一些时序电路只能作为摩尔机器实现。

图Mealy机器的状态图将输出值与每个转换边缘相关联（与Moore机器的状态图相反，Moore机器将输出值与每个状态相关联）。

当输入和输出字母表都是Σ时，还可以将Mealy Automata与Helix有向图相关联。该图具有状态和字母对的顶点，每个节点都是一度的，而 的后继是自动机的下一个状态和自动机输出时的字母x和 它读取字母i。 如果自动机是双向的，则该图是不相交周期的并集。2

样例简单的一台简单的Mealy机器有一个输入和一个输出。每个过渡边缘都标有输入值（以红色显示）和输出值（以蓝色显示）。机器以Si状态启动。（在此示例中，输出是两个最新输入值的异或;因此，机器实现边缘检测器，每次输入翻转时输出一个，否则输出零。）

复杂的更复杂的Mealy机器可以有多个输入和多个输出。

应用Mealy机器为密码机提供了基本的数学模型。例如，考虑到拉丁字母表的输入和输出字母表，可以设计一个Mealy机器，给定一串字母（一系列输入）可以将其处理成加密的字符串（一系列输出）。然而，尽管可以使用Mealy模型来描述Enigma，但状态图太复杂，无法提供设计复杂加密机器的可行方法。

Moore / Mealy机器，也是时钟任意滴答输出的DFA。现代CPU，计算机，手机，数字时钟和基本电子设备/机器都有某种有限状态机来控制它。

简单的软件系统，特别是可以使用正则表达式表示的系统，可以建模为有限状态机。有许多这样的简单系统，例如自动售货机或基本电子设备。

通过找到两个有限状态机的交集，可以以非常简单的方式设计例如交换消息的并发系统。例如，交通信号灯是由多个子系统组成的系统，例如同时工作的不同交通信号灯。

一些应用示例：

数字分类

看着计时器

售货机

红绿灯

扫码机

气泵

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所