（有限）状态机

状态机是最基本的设计模式。

而我们常常说的状态机指有限状态机，缩写是FSM（Finite State Machine）。

无限状态机仅仅是理论上存在的概念，比如，把1/3变成一个状态机的话，那这个状态就是无限循环了，实际上没啥实际的应用意义。

我们常说的状态机指有限状态机。

不夸张的说，状态机模型是世界运行的基础，大脑做的决策推演，在火星上运行的祝融号，计算机软件的底层设计，游戏中的沙雕AI，其底层逻辑都是状态机。

有限状态机的定义： 有限个状态 及在这些状态之间的转移和动作等行为的数学模型；在计算机科学中，状态机的关键要素是状态和状态的转移。

按照输入输出关系，状态机模型有2个，分别是Moore模型（发明者：Edward Moore 1956）和Mealy模型（发明者：George H. Mealy 1955），看到这俩名字，莫名的就想到了《Rick and Morty》...

这两个模型的特点可以用如下公式概括：

一句话：

Moore的设计仅仅与状态有关，Mealy的设计与状态和输入有关系。

Mealy的状态比Moore的状态要少。

它们的设计和表示方法如下所示：

moore和mealy本质上并没有什么差别，设计上可以互相转化。

上图中的A Mealy 转为 Morre 如下所示：

上图中的B Moore 转为 Mealy 如下所示：

推导过程可以参考：http://catonblack.cn/2019-01-18/mealy2moore/

回到程序设计的话题，要设计一个通用的状态机程序，只用switch，case肯定是不够的；

当然，不管是用哪种语言，只要把握住状态机的三个核心要素即可，即：

画成一张图如下（手动 @陈振）：

把它转换成一个数据结构，即：

通用的设计思路是把所有的状态和状态转换表达成一个表，通过查表的形式驱动状态机运转起来。

状态转移表，示例是一个输入4个数字密码（9527）的状态转移表：

状态机的查询和运转：

运行结果展示：

在python里面有一个transitions状态机库，感兴趣的同学可以自己学习一把。

运行结果：

掌握了核心思想，设计一个状态机的通用程序并不是很复杂的事情。

-- EOF --

module HDL_000(cp,a,b,y)//定义模块

input cp,a,b //定义输入端口

output y //定义输出端口

parameter yuan=0,q1=1,q2=2,q3=3,q4=4,q5=5

//yuan q1 q2 q3 q4 q5 六个模块用数字代表定义

reg[2:0] c_s,n_s //定义寄存器变量 这两个是状态机的中间变量

always@(posedge cp or posedge b) //always语句 当cp上升沿或b上升沿有效时启动

begin

if(b) c_s<=yuan //当b有效时 把yuan即0赋给c_s变量

elsec_s<=n_s //否则将n_s的值赋给c_s变量

end

always@( a,c_s)//always语句当a或c_s有效时启动

begin

case(c_s)//case语句 利用c_s的值来判断跳转到对应处

yuan:if(a==1'b1)n_s<=q1//当c_s为yuan的值时 当a为1 跳转到q1处

else n_s<=yuan //否则 n_s跳转到yuan处

q1:if(a==1'b1) n_s<=q2 //当c_s为q1的值时 当a为1 跳转到q2处

else n_s<=yuan //否则 n_s跳转到yuan处

q2:if(a==1'b0) n_s<=q3//当c_s为q2的值时 当a为0 跳转到q3处

else n_s<=yuan //否则 n_s跳转到yuan处

q3:if(a==1'b0) n_s<=q4//当c_s为q3的值时 当a为0 跳转到q4处

else n_s<=yuan //否则 n_s跳转到yuan处

q4:if(a==1'b1) n_s<=q5//当c_s为q4的值时 当a为1 跳转到q5处

else n_s<=yuan //否则 n_s跳转到yuan处

default:n_s<=yuan//当c_s为default时 即非以上情况时 跳转到yuan处

endcase

end

assign y=(c_s==q5)? 1:0 //assign语句 输出y端口的判断输出 c-s是否为q5 是输出1否0

endmodule

状态机一定要根据case语句画出状态图 这样看懂这一道 那你别的也能看懂 也会根据状态图写出程序 否则 学不会

其实状态机懂了之后蛮简单的 就是一个套路 仔细点就好~

之前18年曾经写过一篇关于状态机的博客，链接如下:

https://www.jianshu.com/p/8def04b34b3c

在楼主当初的设计过程中，已经认为是非常完美的一篇关于状态机的文章了，后续，做相关交易系统的时候，觉得该状态机还是太重，过于复杂，于是，便重新设计了一套极简状态机，为什么说是极简状态机，因为这套状态机太过于简单，只有仅仅几个类，而且，轻依赖，仅仅依赖于lombok.jar和slf4j，用于生成set，get方法和打印日志。

还是和上文一样，举个请假的例子，当我们需要请假的时候，首先需要领导审批，领导审批完成ceo审批，当然，并不是所有假条都能够审批完成，也有可能CEO拒绝这个假单，也可能直线领导拒绝这个假单，随着不同的审批意见，则会有不同的流程，去处理假条。

在这里，我们把假单看成业务单(可以是交易单，也可以是业务订单)，状态机就是整个审批过程(审批过程的过程，审批链就是状态机)，而审批意见就决定了状态机走哪条路。

我们还是拿着请假来说事，先想想我们请假需要经过的几个步骤。

当然，也可能是到了领导，或者ceo审批终止，请假失败。

所以我们需要一个枚举类，来定义我们需要的步骤。

知道了该找谁批假条，也得看领导或者ceo批还是不批，所以还需要审批意见，在这里用一个枚举来定义,叫做event。这里为什么会有提交假单和领导审批，因为当你写完假单之后，你就自己会去找领导审批，而非有其他人督促你去提交假单，也就意味着有些步骤是你自己去驱动，自己决定要不要往下走。对于需要外部的意见，就只能等外部意见再接着走了。

审批动作和相关审批意见都已经有了，怎么把动作和审批意见关联起来，也就是状态机刻画出来，状态机怎么知道，这个意见是到了哪个动作去处理的？先画个图:

解释一下:

当我们需要请假的时候，首先拿一个请假条(Event就是SUBMIT_COMMIT)，然后填写相关请假信息(LeavePermitHandler)，然后找领导审批(Event就是LEADER_PERMIT，意思是找领导审批),领导审批就会有两种不同意见，同意或者不同意，如果同意，则就要ceo审批，如果不同意，整个假条就失败了。ceo审批通过，则请假成功，假条才会到成功状态。怎么把这一系列动作刻画出来？在状态机里，可以在Spring上下文创建完成，加载状态机相关配置，也可以在静态方法中初始化。

程序到底如何运行，才能跑起来？

有种类似开车的场景，状态机就像地图，指示牌就是Event，然后汽车是假条，当汽车走到某一个路口，会按照指示牌选择不同的路走，假条也是按照不同的Event(审批意见)在走，状态机和假条之前并没有必然关系，都是线程所有。不存在并发问题，就像汽车走在路上，然而路并和汽车没有关系，只是因为汽车上走的是路，所以状态机与业务并没有关系，而是业务跑在状态机上。

运行结果:

这个例子写的比较粗，懂其意思即可。

感兴趣的可以看源码，我把状态机核心和demo做了分离，了解使用，仅关心demo即可，想了解原理，查看core即可。

相关源码见github: https://github.com/shxz130/statemachine

---