aiwiki.page
中文
计算机 / 算法与理论 / mealy-machine

米利机

米利机是一种有限状态计算模型,每一步的输出由当前状态和当前输入共同决定。

12 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
有限状态机形式语言图灵机触发器组合逻辑独热编码电子设计自动化逻辑门米利机

米利机是一种有限状态机,其输出由当前状态和接收到的输入共同决定。每个输入符号都会引发一次状态转移,并产生一个输出符号,因此通常将输出标注在转移上,而不是状态上。米利机用于描述数字控制器、通信协议、序列检测器,以及其他利用有限记忆处理输入的系统。该模型以乔治·H. 米利(George H. Mealy)的名字命名;他在1955年发表的论文《时序电路的一种综合方法》中提出了这种时序电路设计方法。

形式化定义

确定性米利机通常定义为一个六元组:

M=(Q,Σ,Γ,δ,λ,q0),M=(Q,\Sigma,\Gamma,\delta,\lambda,q_0),

其中:

  • QQ 是有限非空状态集。
  • Σ\Sigma 是有限输入字母表。
  • Γ\Gamma 是有限输出字母表。
  • δ:Q×Σ→Q\delta:Q\times\Sigma\to Q 是转移函数。
  • λ:Q×Σ→Γ\lambda:Q\times\Sigma\to\Gamma 是输出函数。
  • q0∈Qq_0\in Q 是初始状态。

对于输入序列 a1a2⋯ana_1a_2\cdots a_n,状态与输出满足:

qi=δ(qi−1,ai),bi=λ(qi−1,ai),1≤i≤n.q_i=\delta(q_{i-1},a_i), \qquad b_i=\lambda(q_{i-1},a_i), \quad 1\leq i\leq n.

因此,输出 bib_i 取决于转移之前的状态,以及引发该次转移的输入符号。

在标准定义中,这两个函数都是全函数:每个状态与输入的组合都有明确指定的下一状态和输出。部分定义的米利机会将某些组合留作未定义,例如用来描述规格尚不完整的控制器,或合法输入受到限制的接口。

标准米利机对每个输入符号恰好产生一个输出符号。因此,其输入—输出行为定义了一个保持长度不变的函数:

fM:Σ∗→Γ∗,f_M:\Sigma^*\to\Gamma^*,

其中,Σ∗\Sigma^* 和 Γ∗\Gamma^* 分别表示相应字母表上所有有限字符串的集合。空输入产生空输出。与形式语言的识别器不同,米利机本身并不要求设置接受状态或拒绝状态。

表示与运行

状态图与状态表

在状态图中,状态表示为顶点,转移表示为有向边。标注为 a/ba/b 的边表示:收到输入 aa 时,产生输出 bb,并沿该边转移到目标状态。

转移表通过列出每个状态和输入所对应的“下一状态与输出”二元组,表达同样的信息。这些表示方式区分了机器的两项核心操作:

  • **更新记忆:**选择下一状态。
  • **产生响应:**选择当前输入所对应的输出。

状态概括了输入历史中的相关信息。当不同历史之间的差异不再影响未来行为时,它们就可以对应同一个状态。

示例:检测序列101

考虑一台读取二进制符号流的机器:每当最新输入使模式 101101 完整出现时,就输出 11;否则输出 00,并允许检测到相互重叠的模式。

只需三个状态:

  • AA:截至目前的输入中,没有任何非空后缀与 101101 的真前缀匹配。
  • BB:满足上述匹配条件的最长后缀为 11。
  • CC:满足上述匹配条件的最长后缀为 1010。

初始状态为 AA。

当前状态 输入0:下一状态/输出 输入1:下一状态/输出
AA A/0A/0 B/0B/0
BB C/0C/0 B/0B/0
CC A/0A/0 B/1B/1

对于输入 1010110101,输出为 0010100101。检测到 101101 后,机器进入 BB,因为末尾的 11 也可以作为下一次匹配的开头。这样既保留了识别重叠匹配所需的信息,又不必存储完整的输入历史。

与其他计算模型的关系

摩尔机

摩尔机与米利机的区别在于确定输出的方式。摩尔机的输出函数仅取决于当前状态:

g:Q→Γ.g:Q\to\Gamma.

米利机的输出函数则同时取决于状态和输入:

λ:Q×Σ→Γ.\lambda:Q\times\Sigma\to\Gamma.

因此,米利机即使保持在同一状态,也能针对不同输入产生不同输出。摩尔机则必须使用输出标记不同的状态来表示这种差异。

只要适当对齐输出时序和初始输出,两种模型就能表示相同的有限状态输入—输出行为:

  • 如果在每个输入处理完毕后比较输出,就可以将每条转移标注为其目标状态的输出,从而将摩尔机转换为米利机。
  • 可以根据各条入边转移上的输出拆分目标状态,从而将米利机转换为摩尔机。得到的状态可表示为二元组 (q,b)(q,b),同时记录目标状态和刚刚产生的输出。

第二种构造可能增加状态数量。此外,还必须明确约定摩尔机在第一个输入到来之前的输出,因为标准米利机并没有与之对应的初始输出。

声称某一种模型的响应“快一个时钟周期”,取决于实现方式和观察约定,而不是两种模型在计算能力上存在无条件成立的差异。

有限状态转导器与图灵机

米利机是一种受限的有限状态转导器。更一般的转导器可以在一次转移中产生空字符串或多个输出符号,可以包含不消耗输入的转移,也可以允许非确定性选择。

米利机的记忆能力受限于其有限状态集。与图灵机不同,它没有无界的工作带。例如,它无法维护任意大小的精确计数器,也无法在没有固定界限的情况下识别任意深度的嵌套结构。

尽管存在这一限制,米利机仍能处理长度无界的输入流:限制针对的是保留的记忆量,而不是能够处理的输入符号数量。

数字电路实现

在同步硬件中,米利型控制器通常由以下部分实现:

  • 状态寄存器,通常由触发器构成。
  • 根据当前状态和输入计算下一状态的组合逻辑。
  • 根据当前状态和输入计算输出的组合逻辑。

对于 NN 个状态,二进制状态编码至少需要

⌈log⁡2N⌉\left\lceil\log_2 N\right\rceil

个状态位。包括独热编码在内的其他编码方式,则通过增加存储元件来换取不同的逻辑和时序特性。

在输出未经过寄存的米利型实现中,输入变化经过输出逻辑传播后,可能在下一个时钟沿到来之前影响输出。这可以使系统直接响应输入,但也会使输出受到输入不稳定和组合逻辑毛刺的影响。异步输入需要适当的同步电路或接口电路;抽象机器本身并不对亚稳态或电气时序建模。

对输出进行寄存会改变输出时序,规格中必须体现这一变化。选择米利型还是摩尔型实现,取决于状态数量、逻辑深度、时序约束和接口要求。没有哪一种模型在所有电路中都天然更优。

电子设计自动化工具可以将这些控制器的硬件描述综合为寄存器和逻辑门。

等价与最小化

对于确定性米利机,如果从两个状态分别出发,任意有限的后续输入序列都会产生相同的输出序列,那么这两个状态在行为上就是等价的。合并等价状态不会改变可观察行为。

一种标准的最小化过程采用划分细化法:

  1. 删除从初始状态不可达的状态。
  2. 将对每个单独输入符号都产生相同输出的状态归为一组。
  3. 如果某组中的两个状态在相同输入下转移到不同的组,就拆分该组。
  4. 重复上述过程,直到无法进一步拆分。

最终得到的等价类构成约简后机器的状态。对于所有状态均可达、定义完全的确定性米利机,给定行为的最小实现除状态命名外是唯一的。

还可以通过乘积构造探索状态对,以检查机器是否等价。如果某个可达状态对在某一输入下产生不同输出,那么导致这一差异的输入序列就是一个区分测试。这为形式验证以及实现与规格之间的比较提供了支持。

应用与局限

当响应既取决于有限的交互历史,又取决于下一个输入时,米利机是一种实用的模型。其应用包括:

  • **序列检测:**识别串行数据流中的模式。
  • **数字控制:**根据控制器的状态和当前输入生成控制信号。
  • **协议建模:**描述参与方在不同协议状态下如何响应消息。
  • **软件测试:**生成输入序列,并检查预期的输出轨迹。
  • **接口建模:**表示有界的请求—响应行为。

米利机也可以用作模型检测的模型,不过实际规格中往往还会加入数据变量、时序约束或环境假设。

其主要局限在于记忆有限。直接将大量相互独立的变量编码为状态,可能产生极其庞大的状态空间。此外,基本米利机无法表达实时截止期限、概率、连续物理量或不受限制的并发。这些特性需要通过扩展模型或采用其他建模框架来描述。

如何解释输入或输出符号,也是建模时的一项重要选择。一个符号可以表示单个电气比特、一组信号构成的向量,也可以表示接收到消息之类的抽象事件。抽象层面的正确性本身,并不能证明电气时序、消息传输或环境假设等方面的要求已经得到满足。