Mealy 机

Mealy 机在输入事件发生的同一步作出响应。状态概括过去，当前字符提供最新信息，两者合在一起决定现在写什么。因而同一个状态可以对不同输入立即给出不同输出，不必先为每种输出复制一个状态。

这种响应时机适合描述协议控制器与流式编码器：收到事件时既改变内部阶段，又发出确认、告警或编码字符。输出是运行轨迹的一部分，而不是读完整个字后检查的标签；空输入的输出按定义是 $\epsilon$。

因为一条输入边恰产生一个字符，任意输入前缀的输出也恰是完整输出的同长前缀。这个同步因果性比一般 sequential 转导器更强：后者允许某一步输出空字或一整个常量块，Mealy 机则没有可变输出延迟。

“总函数”很关键。工程图中缺失的边若被解释为报错或停机，得到的是偏 Mealy 机；若补上错误汇状态，则仍是总机但输出中会包含错误码。两种语义都合理，却不能靠图上没画边来含混决定。

考虑在线输出“到目前为止读到的 1 数量奇偶性”。取状态 $E,O$ 表示偶数与奇数，输入、输出字母表均为 $\{0,1\}$。在任一状态读 0 保持状态并输出当前奇偶位；读 1 切换状态，并输出切换后的奇偶位。

输入 10110 的轨迹为

所以输出是 11011。第一个输出必须在读第一个 1 的那条边上产生；这里没有“进入终态后再补一个字符”的步骤。逐前缀复算也可验证：五个前缀中的 1 数分别为 $1,1,2,3,3$。

当字母表至少含两个符号时，这个模型不能把任意长输入反转；它也不能在最后才追加一个依赖终态的非空后缀，因为输出长度和时机已被每步一个字符锁定。单字母表上的反转只是恒等映射，不构成反例。若把边输出放宽为字符串，可以做 URL 转义等变长映射；若加入终态输出，则进入 subsequential 模型。把这些能力暗中塞进 $\lambda$ 会破坏 Mealy 与其他模型的边界。

两个 Mealy 机串联时，只要第一台的输出字母表等于第二台的输入字母表，就能以状态对 $(p,q)$ 同步执行：第一台读 $a$ 产生 $b$，第二台立刻读 $b$ 产生 $c$。所得机器最多有 $|Q_1||Q_2|$ 个状态，并仍逐输入字输出一个字符。

等价检查也可在状态对图上完成。若从两个初态出发存在一条输入路径，使某一步的输出不同，就得到最短反例；若所有可达状态对的对应边输出相同，则两个总 Mealy 机定义同一函数。这个局部判据依赖同步逐字输出，不能直接搬到允许延迟输出的一般转导器。

Mealy 控制器常用于硬件握手、串行协议和在线监测。它响应少一个状态延迟，但输出可能随输入边沿立即变化；实际电路若要求输出只在寄存器边界改变，设计者往往改用 Moore 表示或显式寄存输出。这是时序接口选择，不是抽象表达能力的简单高低。

测试时可把每条用例写成输入/输出等长的轨迹表，并逐步核对“旧状态、输入、输出、新状态”四元组。只检查最终状态会漏掉中途输出错误，因为 Mealy 语义没有接受集合替这些轨迹作最终汇总。