有限状态机

在数字电路系统中，有限状态机是一种十分重要的时序逻辑电路模块，它对数字系统的设计具有十分重要的作用。

有限状态机是指输出取决于过去输入部分和当前输入部分的时序逻辑电路。一般来说，除了输入部分和输出部分外，有限状态机还含有一组具有“记忆”功能的寄存器，这些寄存器的功能是记忆有限状态机的内部状态，它们常被称为状态寄存器。在有限状态机中，状态寄存器的的下一个状态不仅与输入信号有关，而且还与该寄存器的当前状态有关，因此有限状态机又可以认为是组合逻辑和寄存器逻辑的一种组合。其中，寄存器逻辑的功能是存储有限状态机的内部状态；而组合逻辑有可以分为次态逻辑和输出逻辑两部分，次态逻辑的功能是确定有限状态机的下一个状态，输出逻辑的功能是确定有限状态机的输出。

在实际的应用中，根据有限状态机是否使用输入信号，设计人员经常将其分为Moore型有限状态机和Mealy型有限状态机两种类型。1 Moore型有限状态机 其输出信号仅与当前状态有关，即可以把Moore型有限状态的输出看成是当前状态的函数。2 Mealy型有限状态机 其输出信号不仅与当前状态有关，而且还与所有的输入信号有关，即可以把Mealy型有限状态机的输出看成是当前状态和所有输入信号的函数。

有限状态机（FSM）又称为有限状态自动机或简称状态机，是表示有限个状态以及这些状态之间的转移和动作等行为的数学模型。

状态存储关于过去的信息，就是说它反映从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足来确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述。有多种类型的动作：

进入动作（Entry action）

在进入状态时进行

退出动作

在退出状态时进行

输入动作

依赖于当前状态和输入条件进行

转移动作

在进行特定转移时进行

有限状态机是一种算法思想，简单而言，有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。在Gof的23种设计模式里的state模式是一种面向对象的状态机思想，可以适应非常复杂的状态管理。

现在，在硬件领域，FSM被用于电路设计，而在软件领域被普遍用于搜索引擎的分词、编译器实现、游戏开发和工作流引擎实现。游戏开发中，通常用FSM实现NPC控制。在工作流引擎实现中，通常用FSM来实现对于流程实例、活动实例、转移实例、工作项实例的状态迁移。FSM的实现方式有多种，在工作流引擎中我们一般采用面向对象的方式来实现FSM。