1 概述

状态机[1]一般指有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机（英语：finite-state automaton，缩写：FSA），是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。有限状态机是在自动机理论和计算理论中研究的一类自动机。如下图所示，有限状态机归属于自动机理论范畴，从下面的自动机理论的领域分层图可以看出，越往外层，概念越复杂。

 

状态机中有几个术语：state(状态) 、transition(转移) 、action(动作) 、transition condition(转移条件) 。

• state(状态) ：将一个系统离散化，可以得到很多种状态，当然这些状态是有限的。例如：门禁闸机可以划分为开启状态、关闭状态；电扇可以划分为关、一档、二档、三档等状态。

• transition(转移) ：一个状态接收一个输入执行了某些动作到达了另外一个状态的过程就是一个transition(转移)。定义transition(转移)就是在定义状态机的转移流程。

• transition condition(转移条件) ：也叫做Event(事件)，在某一状态下，只有达到了transition condition(转移条件)，才会按照状态机的转移流程转移到下一状态，并执行相应的动作。

• action(动作)：在状态机的运转过程中会有很多种动作。如：进入动作(entry action)[在进入状态时进行]、退出动作(exit action)[在退出状态时进行]、转移动作[在进行特定转移时进行]。

如下图，就定义了一个只有opened 和closed两种状态的状态机。当系统处于opened状态，在收到输入“关闭事件”，达到了状态机转移条件，系统就转移到了closed状态，并执行相应的动作，此例有一个进入动作(entry action)，进入closed状态，会执行close door动作。

 

有限状态机在很多不同领域被广泛应用，包括电子工程、语言学、计算机科学、哲学、生物学、数学和逻辑学。在计算机科学中，有限状态机被广泛用于建模、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。

 

2 分类

有限状态机可以被分为不同的类型，主要可以被分为：acceptors(接收器)、transducers(转换器) 两大类。

2.1 acceptors(接收器)

acceptors(接收器) 是指产生一个二值的输出，指示接收的输入是否能被接受。acceptors(接收器)的每一种状态都是接受或不接受的。如果一组所有的输入都被接受并且当前的状态是接受状态，那么这一组输入就是可接受的。有限状态机的acceptors(接收器)这一类在正则引擎的实现中用得非常多。

如下图是一种acceptors(接收器) 类型有限状态机，用来识别所输入的字符串是否为nice，其总共被划分为了七种状态，其中只有第七种状态Success被认为是可接受状态。如果所输入的字串不是nice，则会被转移到第六种状态Error。

 

如下给出acceptors(接收器) 的数学形式化定义，acceptors(接收器) 型有限状态机是一个五元组（，S，,,F）,其中：

• 是输入字符集合(有限的非空符号集合)； 

• S是有限非空状态集合；

• 是初始状态，属于中的元素； 

• 是状态转移函数：：S  S； 

• F是最终状态集合，是S的子集.

2.2 transducers(转换器)

transducers(转换器) 是根据当前的状态和(或)给定的输入产生输出，输出的同时可能也伴随着状态的转移(不是必须)。在一些事件驱动型应用和计算语言学(computational linguistics)领域应用普遍。transducers(转换器) 型有限状态机可以分为两种子类型，moore machine (摩尔型有限状态机)和mealy machine (米利型有限状态机) ，其中：

• 若输出只和状态有关而与输入无关，则称为moore状态机

• 输出不仅和状态有关而且和输入有关系，则称为mealy状态机

2.2.1 moore状态机：

如下所示的状态机为moore状态机，其有q0、q1、q2、q3四个状态，X,Y,Z三个输入，a、b、c三个输出。可以看出其四个状态q0、q1、q2、q3对应的输出分别为b、a、a、c，就是说输出已经和状态绑定好，不管输入为哪一个，均不影响输出。其中q0为初始状态，假设输入为XYZY，可以看出输出为bcac；假设输入为ZXYZ，则输出为baca，可以看出，虽然输出只和状态有关而与输入无关，但改变输入的序列顺序，输出序列也会改变。

 

2.2.2 mealy状态机：

mealy状态机与输出只依赖于机器当前状态的moore状态机不同，它的输出与当前状态和输入都有关。但是对于每个mealy状态机都有一个等价的moore机。如下所示为一个简单的mealy状态机，它有一个输入和一个输出。在每一个有向边上，标注出了输入(红色)和输出(蓝色)。这个状态机的初始状态为Si，当输入为0，输出0，状态变为S0，接着输入0，输出0，状态还是为S0，在此状态下一直输入0，输出会一直是0，当输入为1时，输出才为1，状态变为S1，在此状态再接着输入1，输出一直还是0，直到遇到输入为0，输出才变为1。此状态机其实实现了一个边缘触发检测器，每次输入从1到0或是从1到0发生跳变时，输出为1否则输出为0。如下所示时序图，当输入为0111001110时，输出为0100101001。

 

3 应用

以日常生活中最常见的电风扇为例，来讨论状态机的应用问题。如下图所示，电风扇有4个按钮，分别是关、弱档、中档和强档，关按钮负责关闭电风扇，也就是停止电风扇的转动；而弱档、中档和强档都可以让电风扇开启，其各档所对应的风扇转动的速度不一样。

可以将按下四个按钮所对应的效果定义四种状态，分别为关机、弱风、中风、强风，另外，外加一个故障状态，总共五种状态。如下为电风扇的状态图转移图，其可能的输入事件为 [按下“关”]、[按下“弱]、[按下“中”]、[按下“强”]、[出现异常]。在状态转移的过程中，肯定有动作的执行，如从关机到弱风的过程中，肯定会执行开启电机的动作；从弱风到强风的过程，肯定也会有执行加大电流的动作。整个过程中用不到状态机的输出，所以算是一个转移系统。

 

回到编程领域，GUI应用程序、Web应用程序等事件驱动型的应用程序，采用状态机的思路来完成程序设计，可以简化设计流程，使程序的可读性、可维护性都得到增加。

4 总结

有限状态机可以分为acceptors(接收器)、transducers(转换器) 两大类。acceptors(接收器) 型有限状态机是一个五元组，transducers(转换器) 型有限状态机是一个六元组。transducers(转换器) 型有限状态机可以分为两种子类型，moore machine(摩尔型有限状态机)和mealy machine(米利型有限状态机)。若输出只和状态有关而与输入无关，则称为moore状态机，若输出不仅和状态有关而且和输入有关系，则称为mealy状态机。

参考资料

[1]

维基百科: https://zh.wikipedia.org/zh-hans/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA?wprov=sfla1