米利机是一种有限状态机,其输出由当前状态和接收到的输入共同决定。每个输入符号都会引发一次状态转移,并产生一个输出符号,因此通常将输出标注在转移上,而不是状态上。米利机用于描述数字控制器、通信协议、序列检测器,以及其他利用有限记忆处理输入的系统。该模型以乔治·H. 米利(George H. Mealy)的名字命名;他在1955年发表的论文《时序电路的一种综合方法》中提出了这种时序电路设计方法。
形式化定义
确定性米利机通常定义为一个六元组:
其中:
- 是有限非空状态集。
- 是有限输入字母表。
- 是有限输出字母表。
- 是转移函数。
- 是输出函数。
- 是初始状态。
对于输入序列 ,状态与输出满足:
因此,输出 取决于转移之前的状态,以及引发该次转移的输入符号。
在标准定义中,这两个函数都是全函数:每个状态与输入的组合都有明确指定的下一状态和输出。部分定义的米利机会将某些组合留作未定义,例如用来描述规格尚不完整的控制器,或合法输入受到限制的接口。
标准米利机对每个输入符号恰好产生一个输出符号。因此,其输入—输出行为定义了一个保持长度不变的函数:
其中, 和 分别表示相应字母表上所有有限字符串的集合。空输入产生空输出。与形式语言的识别器不同,米利机本身并不要求设置接受状态或拒绝状态。
表示与运行
状态图与状态表
在状态图中,状态表示为顶点,转移表示为有向边。标注为 的边表示:收到输入 时,产生输出 ,并沿该边转移到目标状态。
转移表通过列出每个状态和输入所对应的“下一状态与输出”二元组,表达同样的信息。这些表示方式区分了机器的两项核心操作:
- **更新记忆:**选择下一状态。
- **产生响应:**选择当前输入所对应的输出。
状态概括了输入历史中的相关信息。当不同历史之间的差异不再影响未来行为时,它们就可以对应同一个状态。
示例:检测序列101
考虑一台读取二进制符号流的机器:每当最新输入使模式 完整出现时,就输出 ;否则输出 ,并允许检测到相互重叠的模式。
只需三个状态:
- :截至目前的输入中,没有任何非空后缀与 的真前缀匹配。
- :满足上述匹配条件的最长后缀为 。
- :满足上述匹配条件的最长后缀为 。
初始状态为 。
| 当前状态 | 输入0:下一状态/输出 | 输入1:下一状态/输出 |
|---|---|---|
对于输入 ,输出为 。检测到 后,机器进入 ,因为末尾的 也可以作为下一次匹配的开头。这样既保留了识别重叠匹配所需的信息,又不必存储完整的输入历史。
与其他计算模型的关系
摩尔机
摩尔机与米利机的区别在于确定输出的方式。摩尔机的输出函数仅取决于当前状态:
米利机的输出函数则同时取决于状态和输入:
因此,米利机即使保持在同一状态,也能针对不同输入产生不同输出。摩尔机则必须使用输出标记不同的状态来表示这种差异。
只要适当对齐输出时序和初始输出,两种模型就能表示相同的有限状态输入—输出行为:
- 如果在每个输入处理完毕后比较输出,就可以将每条转移标注为其目标状态的输出,从而将摩尔机转换为米利机。
- 可以根据各条入边转移上的输出拆分目标状态,从而将米利机转换为摩尔机。得到的状态可表示为二元组 ,同时记录目标状态和刚刚产生的输出。
第二种构造可能增加状态数量。此外,还必须明确约定摩尔机在第一个输入到来之前的输出,因为标准米利机并没有与之对应的初始输出。
声称某一种模型的响应“快一个时钟周期”,取决于实现方式和观察约定,而不是两种模型在计算能力上存在无条件成立的差异。
有限状态转导器与图灵机
米利机是一种受限的有限状态转导器。更一般的转导器可以在一次转移中产生空字符串或多个输出符号,可以包含不消耗输入的转移,也可以允许非确定性选择。
米利机的记忆能力受限于其有限状态集。与图灵机不同,它没有无界的工作带。例如,它无法维护任意大小的精确计数器,也无法在没有固定界限的情况下识别任意深度的嵌套结构。
尽管存在这一限制,米利机仍能处理长度无界的输入流:限制针对的是保留的记忆量,而不是能够处理的输入符号数量。
数字电路实现
在同步硬件中,米利型控制器通常由以下部分实现:
对于 个状态,二进制状态编码至少需要
个状态位。包括独热编码在内的其他编码方式,则通过增加存储元件来换取不同的逻辑和时序特性。
在输出未经过寄存的米利型实现中,输入变化经过输出逻辑传播后,可能在下一个时钟沿到来之前影响输出。这可以使系统直接响应输入,但也会使输出受到输入不稳定和组合逻辑毛刺的影响。异步输入需要适当的同步电路或接口电路;抽象机器本身并不对亚稳态或电气时序建模。
对输出进行寄存会改变输出时序,规格中必须体现这一变化。选择米利型还是摩尔型实现,取决于状态数量、逻辑深度、时序约束和接口要求。没有哪一种模型在所有电路中都天然更优。
等价与最小化
对于确定性米利机,如果从两个状态分别出发,任意有限的后续输入序列都会产生相同的输出序列,那么这两个状态在行为上就是等价的。合并等价状态不会改变可观察行为。
一种标准的最小化过程采用划分细化法:
- 删除从初始状态不可达的状态。
- 将对每个单独输入符号都产生相同输出的状态归为一组。
- 如果某组中的两个状态在相同输入下转移到不同的组,就拆分该组。
- 重复上述过程,直到无法进一步拆分。
最终得到的等价类构成约简后机器的状态。对于所有状态均可达、定义完全的确定性米利机,给定行为的最小实现除状态命名外是唯一的。
还可以通过乘积构造探索状态对,以检查机器是否等价。如果某个可达状态对在某一输入下产生不同输出,那么导致这一差异的输入序列就是一个区分测试。这为形式验证以及实现与规格之间的比较提供了支持。
应用与局限
当响应既取决于有限的交互历史,又取决于下一个输入时,米利机是一种实用的模型。其应用包括:
- **序列检测:**识别串行数据流中的模式。
- **数字控制:**根据控制器的状态和当前输入生成控制信号。
- **协议建模:**描述参与方在不同协议状态下如何响应消息。
- **软件测试:**生成输入序列,并检查预期的输出轨迹。
- **接口建模:**表示有界的请求—响应行为。
米利机也可以用作模型检测的模型,不过实际规格中往往还会加入数据变量、时序约束或环境假设。
其主要局限在于记忆有限。直接将大量相互独立的变量编码为状态,可能产生极其庞大的状态空间。此外,基本米利机无法表达实时截止期限、概率、连续物理量或不受限制的并发。这些特性需要通过扩展模型或采用其他建模框架来描述。
如何解释输入或输出符号,也是建模时的一项重要选择。一个符号可以表示单个电气比特、一组信号构成的向量,也可以表示接收到消息之类的抽象事件。抽象层面的正确性本身,并不能证明电气时序、消息传输或环境假设等方面的要求已经得到满足。