（有限）状态机

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

而我们常常说的状态机指有限状态机，缩写是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 --

VHDL设计一个双进程状态机，原程序如下（后面的图是仿真结果）：

LIBRARY ieee

use ieee.std_logic_1164.all

use ieee.std_logic_arith.all

use ieee.std_logic_unsigned.all

entity dou_state is

port(clk,rst : in std_logic

      din    : in std_logic_vector(1 downto 0)

      dout   : out std_logic_vector(3 downto 0))

end dou_state

architecture arch of dou_state is

type state_type is (s0,s1,s2,s3)

signal state : state_type

begin

P1: process(clk,rst)

begin

if rst='0' then

state <= s0

dout  <= "0000"

elsif clk'event and clk='1' then

case state is

when s0 =>

   if din = "10" then

      state <= s1

   else

      state <= s0

      dout <= "1001"

   end if

when s1 =>

   if din = "11" then

      state <= s2

   else

      state <= s1

      dout <= "0101"

   end if

when s2 =>

   if din = "01" then

      state <= s3

   else

      state <= s2

      dout <= "1100"

    end if

when s3 =>

   if din = "00" then

      state <= s0

   else

      state <= s3

      dout <= "0010"

   end if

when others =>

   NULL

end case

end if

end process

end arch

---