有限状态机
有限状态机(英语:finite-state machine,缩写:FSM)又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
组成要素:
现态:是指当前所处的状态。
事件:又称为条件。当一个条件被满足(发生事件),可能将会触发一个动作,或者执行一次状态的迁移。
动作:条件满足后执行的动作行为。动作执行完毕后,可以迁移到新的状态,也可以仍旧保持原状态。动作不是必需的,当条件满足后,也可以不执行任何动作,直接迁移到新状态。
次态:条件满足后要迁往的新状态。“次态”是相对于“现态”而言的,“次态”一旦被激活,就转变成新的“现态”了。
三个特征:
状态总数有限
任意时刻,只能处于一种状态
某种状态下,会从一种状态转变
transition
为另一种状态
执行逻辑:
状态机的分类
识别器(正则识别)
也称为序列检测器。输入字符符号,产生一个二元输出,“是”或“否”,来回答输入是否被机器接受。
主要应用于正则语言中,比如如下识别地址的状态机:
变换器(Moore机)
摩尔型有限状态机(Moore机),输出只依赖于当前状态。即:
变换器(Mealy机)
米利型有限状态机(Mealy机),输出依赖于当前状态和输入。即:
状态机表示法
状态转移表
状态表表示了事件与当前状态之间的关系,下面是用于读取有头有尾的消息的消息读取其的状态机的转移表:
状态/事件 | 消息头 | 消息体数据 | 消息尾 | 其他 |
---|---|---|---|---|
初始状态 | 读取 | 出错 | 出错 | 出错 |
读取状态 | 出错 | 读取 | 完成 | 出错 |
完成状态 | 出错 | 出错 | 出错 | 出错 |
状态图
活动图
应用场景
正则语言解析
正则表达式。正则表达式仅仅是用来表示语言规则的一种形式。为了让机器理解正则表达式,我们需要通过程序来实现一种与正则表达式等价的结构,这种结构就是状态机。
例如正则 [a|b]*abb
的状态机为:
DFA:deterministic finite automaton,确定有限状态自动机或确定有限自动机。是一个能实现状态转移的自动机。
编译器
网络协议
游戏设计
复杂的状态、事件、动作。游戏主逻辑、游戏大厅等具有复杂UI交互的类,都可以考虑使用状态机来进行代码编写,细分状态,保证代码的健壮性,方便以后扩展新的特性。例如:挂机时自动刷怪。
web前端UI控制
业务系统
实现状态机
使用if else
或者switch case
if else
或者switch case
状态迁移表法
状态模式
开源状态机引擎
spring-statemachine
与spring天然集成,线程不安全,但是使用较为复杂。
stateless4j
轻量、简单、轻度使用,对代码入侵小。
squirrel-foundation
功能丰富,较为轻量,上手简单。
最后更新于