• home > theory > CST > Compiling >

    状态机概念通俗理解有限状态机

    Author:zhoulujun Date:

    状态机是有限状态自动机的简称,是现实事物运行规则抽象而成的一个数学模型。状态机是一种编程思路。一种对对自然界某种事物(或数据)状态变化的抽象。它规定了一个实例(某种抽象),某一时刻只能有一种状态(属性)。

    状态机

    有限状态机(Finite State Machine,FSM),指上诉的状态机,总状态数种类是有限个

    且规定变化到某种状态,需要验证当前状态是都合理。实现的话,实例化时候需要接收允许从某状态,变化到哪些状态。

    状态机是有限状态自动机的简称,是现实事物运行规则抽象而成的一个数学模型。

    先来解释什么是“状态”( State )。现实事物是有不同状态的,例如一个自动门,就有 open 和 closed 两种状态。我们通常所说的状态机是有限状态机,也就是被描述的事物的状态的数量是有限个,例如自动门的状态就是两个 open 和 closed 。

    状态机,也就是 State Machine ,不是指一台实际机器,而是指一个数学模型。说白了,一般就是指一张状态转换图。例如,根据自动门的运行规则,我们可以抽象出下面这么一个图。

    状态机转换门

    图解状态机

    以物理课学的灯泡图为例,就是一个最基本的小型状态机

    初中实验课,电学实验,灯泡实验

    这里就是两个状态:①打开开关,灯泡亮,②关闭开关,灯泡灭

    假设为了节约,小灯泡开了超过8个小时就自动关闭,除非再次做打开开关的操作,画出此时的状态机图如下

    灯泡实验状态机图

    判断不是状态机必要的,如正常小灯泡的两种状态,可以不需要经过判断

    起始和终止状态可能是相同的,也可能是不同的,即同一种状态可能是起始状态,也可能为终止状态

    状态机是一种编程思路。一种对对自然界某种事物(或数据)状态变化的抽象

    • 它规定了一个实例(某种抽象),某一时刻只能有一种状态(属性)。一般用字符串表示。

    • 规定了只能通过实例的方法,即执行某个动作(函数),之后才可以改变状态(属性)。

    状态变更回调

    状态变更回调,指状态变更动作之前和之后执行的函数

    状态变更动作可能是异步完成,有时候需要知道开始和结束。例如调试时候。

    只要你满足了这些特征。就是状态机。

    以美团外卖为例,制作了一个简单的状态机图

    6306801-e16015aae6725083.jpg


    状态机4要素

    状态机可归纳为4个要素,即现态、条件、动作、次态。这样的归纳,主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因,“动作”和“次态”是果。详解如下:

    1. 现态:是指当前所处的状态。

    2. 条件:又称为“事件”,当一个条件被满足,将会触发一个动作,或者执行一次状态的迁移。

    3. 动作:条件满足后执行的动作。动作执行完毕后,可以迁移到新的状态,也可以仍旧保持原状态。动作不是必需的,当条件满足后,也可以不执行任何动作,直接迁移到新状态。

    4. 次态:条件满足后要迁往的新状态。“次态”是相对于“现态”而言的,“次态”一旦被激活,就转变成新的“现态”了。

    http 请求就是一个典型的有限状态机。状态有 open pending ending error等 ,stateChange ,success 等就是它的状态变更回调。且如果当前是 error ,不能从 error 变成 pending 了。

    四大概念

    1. State ,状态。一个状态机至少要包含两个状态。例如上面自动门的例子,有 open 和 closed 两个状态。

    2. Event ,事件。事件就是执行某个操作的触发条件或者口令。对于自动门,“按下开门按钮”就是一个事件。

    3. Action ,动作。事件发生以后要执行动作。例如事件是“按开门按钮”,动作是“开门”。编程的时候,一个 Action 一般就对应一个函数。

    4. Transition ,变换。也就是从一个状态变化为另一个状态。例如“开门过程”就是一个变换。

    上面这四大概念,在使用状态机思想来写程序时候经常用到,参考:https://github.com/jakesgordon/javascript-state-machine

    计算机中的状态机

    状态机就是指内存里的某个复杂数据结构从当前状态变成下一个状态。

    比如象棋的某一刻就是状态机的一个当前状态,给他一个命令将4平5,当前状态必定转换到下一个确定性状态

    如果用一个二维数组来表示棋盘的状态,那么状态机就是一个函数,他接受当前状态和新的命令,输出下一个状态:S₂=λ(Sf₁,cmd)

    原理简单,但实现可能非常复杂。如果要回滚状态(悔棋),那么需要执行撤销命令。


    最后推荐阅读《状态机图教程 (UML State Diagram)


    参考文章:

    最佳实践之有限状态机 https://www.cnblogs.com/orange-CC/p/12933433.html

    状态机 https://www.jianshu.com/p/403f750e1d3a

    深入浅出理解有限状态机 https://zhuanlan.zhihu.com/p/46347732

    什么是状态机? https://zhuanlan.zhihu.com/p/47434856

    状态机入门:从定义到使用 www.woshipm.com/pmd/682326.html



    转载本站文章《状态机概念通俗理解有限状态机》,
    请注明出处:https://www.zhoulujun.cn/html/theory/ComputerScienceTechnology/Compiling/2020_0708_8509.html

    下一篇:Last page