《计算机组成与体系结构（原书第4版）》 —3.6.4　有限状态机

3.6.4　有限状态机

特性表和时序图可用来描述触发器和时序电路的动作。有限状态机（FSM）提供了等效的图形描述。有限状态机通常使用圆圈表示机器状态，用有向弧表示从一个状态转变到另一个。每个圆圈都标有它代表的状态，每个圆弧都标记有用于该状态转换的输入或输出。FSM一次只能处于一个状态。这里只对同步FSM进行研究（只有当时钟到来时才允许转换状态）。

可以用状态机建模的真实示例是公共交通灯。它有3种状态：绿色、黄色和红色。当硬件中的计时器到达时状态发生转换。下面是交通灯的FSM。

有许多种不同类型的有限状态机，每种都有不同的作用。图3-24显示了一个JK触发器的摩尔机表示。圆圈代表触发器的两种状态，标记为A和B。输出Q用括号表示，圆弧表示状态之间的转换。可以在这个图中看到，当J=1和K=0或J=K=1时，JK触发器从状态0变到状态1;当J=K=1或J=0和K=1时，它从状态1变为状态0。这种有限状态机是摩尔型机器，因为每个状态与机器的输出相关。事实上，图中所示的反射电弧是不需要的，因为机器的输出仅在状态改变时改变，并且状态不通过反射电弧改变。据此，可以绘制一个简化的摩尔机（如图3-25所示）。摩尔机以爱德华·F.摩尔命名，他于1956年发明了这种类型的FSM。

图3-24　用JK触发器表示摩尔机　　图3-25　用JK触发器表示简化的摩尔机

与爱德华·摩尔同时代的乔治H.米莉独立发明了另一种类型的FSM，它也是以发明者命名的。像摩尔机一样，米莉机也是用圆圈表示状态，用连接弧表示每个状态过渡。与摩尔机不同的是，米莉机的输出不但与每个状态相关（在摩尔机示例中将0或1放在方括号中），还与每个转换相关。这意味着米莉机的输出函数与当前状态　图3-26　用JK触发器表示一个米莉机及其输入有关，而摩尔机的输出函数仅与当前状态有关。每个过渡弧上用其输入和输出分开标记并用斜杠隔开。反射弧不能从米莉机中删除，因为它们描绘机器的输出。

图3-26显示了一个用于JK触发器的米莉机。

在实际执行摩尔机或米莉机时，有两件事情是必须要做的：用于存储当前状态的存储器（寄存器），以及控制输出和从一个状态到另一个状态转换的组合逻辑组件。图3-27说明了这两个机器的逻辑。

图　3-27

这里提供的摩尔机或米莉机的图形模型和框图对于电路行为的高级概念建模是很有用的。然而，一旦电路变得很复杂时，摩尔机和米莉机会变得很麻烦，并且很难捕获到实现所需的细节。例如，考虑一个微波炉。微波炉将仅在门关闭时才处于“开”状态，控制转盘设置为“烹饪”或“除霜”，定时器开始显示时间。“开”状态意味着磁控管正在产生微波，炉室中的灯被点亮，并且转盘正在旋转。如果时间到了，打开门，或控制从“烹饪”变为“关闭”时，微波炉变为“关”状态。由定时器提供的范围连同定义一个状态的大量信号，很难在摩尔机和米莉机中捕获。因此，克里斯托弗·R.克莱尔发明了算法状态机（ASM）。正如其名称所示，算法状态机表示将FSM从一个状态提前到另一个状态的算法。

算法状态机由包含状态框、标签、可选条件和输出框的块组成（见图3-28）。每个ASM块恰好具有一个入口点和至少一个出口点。摩尔型输出（电路信号）在状态块内指示，米莉型输出在椭圆输出“盒”中指示。如果信号在“高”时置位，则前缀为H；否则，它将以L为前缀。如果信号立即置位，则它也以I为前缀。否则，在下一个时钟周期信号有效。导致状态变化的输入条件（这是算法部分）由名为条件框的细长的六边形来表示。任何数量的条件框都可以放在ASM块内，并且它们的显示顺序并不重要。在示例中微波炉的ASM块如图3-29所示。

图3-28　算法状态机的组件

图3-29　微波炉的算法状态机

可见，ASM可以表示摩尔机和米莉机的行为。摩尔机和米莉机可能是等效的，因此可以互换使用。但是，具体使用哪一种取决于实际应用。在大多数情况下，摩尔机相比米莉机需要更多的状态（内存），但可以得到更简单的实现，因为摩尔机的转换更少。无硬件的机器摩尔机和米莉机只是你在计算机科学文章中遇到的许多不同类型有限状态机中的两种。理解FSM对于研究编程语言、编译器、计算理论和自动机理论至关重要。我们将这些抽象称为机器，因为机器是一组响应刺激（事件）的设备，这些刺激是基于先前事件的历史（当前状态）生成的可预测响应（动作）。其中最重要的是有限自动机（DFA）计算模型。一般来说，在DFA中，M完全由五元组描述，即M=（Q，S，Σ，δ，F），其中：

●Q是表示机器能承担的每一种配置的有限状态集合；

●S是Q的元素，表示起始状态，它是机器接收任何输入之前的初始状态；

●Σ是机器能识别的输入字母表或事件集；

●δ是映射Q中的一个状态和输入字母表中的一个字母到Q中另一个（可能相同）状态的转换函数；

●F是最终（或接受）状态的一组状态（Q的元素）。

DFA在编程语言的研究中特别重要，它们用于识别语法或语言。要想使用DFA，请从初始状态开始并处理输入字符串，一次一个字符，随着输入而改变状态。在处理整个字符串时，如果你处于最终接受状态，则DFA“接受”该合法字符串。否则，字符串被拒绝。

可以　接收一个变量名的有限状态机使用这个DFA的定义来描述一个机器，就像在编译器中从源代码文件中提取变量名（字符串）一样。假设计算机语言必须接受以字母开头的变量名，在初始字母之后可以包含无限字母或数字流，并由空格字符（制表符、空格、换行符等）终止。变量名的初始状态是空字符串，因为没有输入被读取。在右图中用夸张的箭头（还有几个其他符号）指示这个初始状态。

当机器识别字母字符时，它转换到状态I，在那里只要输入了字母或数字，它就会保留。在接收到空格字符时，机器转换到状态A，即它的最终接受状态，用双圈指示。如果输入了除数字、字母或空格之外的字符，则机器进入错误状态，这是拒绝字符串的最终状态。

我们更感兴趣（因为正在讨论硬件）的是具有输出状态的摩尔和米莉FSM。这些FSM和DFA之间的基本区别是，除了从一个状态转移到另一个状态的转换函数以外，摩尔机和米莉机也能生成一个输出符号。此外，由于电路没有停止或接受字符串的概念，所以它们没有最终状态集的定义，而是直接输出。摩尔机和米莉机的M都可以由五元组来完全描述，即M=（Q，S，Σ，Γ，δ），其中：

●Q是表示机器每个配置的有限状态集合；

●S是Q的元素，表示开始状态，即机器在接收任何输入之前的状态；

●Σ是机器可以识别的输入字母表或事件集；

●Γ是有限输出字母表；

●δ是将状态从Q和输入字母表的字母映射到Q状态的转移函数。

注意，输入和输出字母通常是相同的，但不是必须这样。产生输出的方式是区分摩尔机和米莉机之间的元素。因此，摩尔机的输出函数嵌入了S的定义，米莉机的输出函数嵌入了转移函数δ。

如果这看起来太抽象，那么只要记住一台计算机可以被认为是通用有限状态机。它描述为一台机器加上输入以及产生（通常）的预期输出。有限状态机只是关于计算机和计算的另一种思考方式。