Fsm基础 - littleboy12580/learning_python GitHub Wiki
FSM介绍
FSM(Finite State Machine) 即有限状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
FSM分类
有两类FSM：接受器/识别器与变换器
接受器/识别器
接受器/识别器也叫序列检测器，其产生一个二元输出，说要么“是”要么“否”来回答输入是否被机器接受。所有FSM的状态被称为要么接受要么不接受。在所有输入都被处理了的时候，如果当前状态是接受状态，输入被接受，否则被拒绝；其存在3种状态：开始状态、中间状态与接受状态（最终状态），一个接受器只有一个开始状态和接受状态，可以存在多个中间状态；
在状态图中，开始状态通常用“没有起点的箭头”指向它来表示，表示接受器开始工作的状态；接受状态（或称最终状态）是机器成功地进行了它的程序之后的状态。状态图中通常将其标示为双圆圈。
开始状态也可以是接受状态，此情况下会接受空字符串。如果开始状态不是接受状态，且没有可以连到任何接受状态的箭头，那么此有限机就不会“接受”任何输入。
一个接受状态的例子如下图所示：
该图表示一台判断输入二进位字符串是否含有偶数个0的 确定有限自动机（DFA），S1 代表着已经输入了偶数个0，因此S1 即为接受状态（同时亦为开始状态）。若输入含有偶数个0（包含没有0的字符串），则此机器会以接受状态来结束。
变换器
变换器使用动作基于给定的输入和/或状态生成输出。它们用于控制应用，常分为两种类型—Moore机和Mealy机。输出只有当前状态的成为Moore机，输出不但与当前状态有关，还和输入有关的机器成为Mealy机
FSM数学模型
FSM的下一个状态和输出是由输入和当前状态决定的，其逻辑如下图所示：
根据类型不同，有多种定义，下面给出接受器和变换器的一种常见数学定义：
接受器有限状态机是五元组（∑，S，s0，δ，F）
- ∑是输入字母表（符号的非空有限集合）
- S是状态的非空有限集合
- s0是初始状态，它是S的元素
- δ是状态转移函数，δ：S × ∑ → S
- F是最终状态的集合，S的（可能为空）子集
变换器有限状态自动机是六元组（∑，Γ，S，s0，δ， ω ）
- ∑是输入字母表（符号的非空有限集合）
- Γ是输出字母表（符号的非空有限集合）
- S是状态的非空有限集合
- s0是初始状态，它是S的元素
- δ是状态转移函数，δ：S × ∑ → S
- ω是输出函数
如果输出函数是状态和输入字母表的函数 ω：S × ∑ → Γ，则定义对应于Mealy模型；如果输出函数只依赖于状态ω：S → Γ，则定义对应于Moore模型
性质比较
通过归纳比较，两种状态机具有如下性质特点。
-
Mealy机比Moore机“响应”速度快。Mealy机的输出与当前状态和输入有关，而Moore机输出仅与当前状态有关。Mealy机的输入立即反应在当前周期；Moore机的输入影响下一状态，通过下一状态影响输出。为此Mealy机比Moore机输出序列超前一个周期，即“响应速度”较快。Mealy机的输出在当前周期，具有较长的路径（组合逻辑）；Moore机的输出具有一个周期的延时，容易利用时钟同步，Moore机具有较好的时序
-
Mealy机状态少，Moore机结构简单。由于Moore机的输出只有当前的状态有关，一个状态对应一个输出，Moore机具有更多的状态。Mealy和Moore机之间可以相互转化，对于每个Mealy机，都有一个等价的Moore机，Moore机状态的上限为所对应的Mealy机状态的数量和输出数量的乘积
-
状态机的状态通过触发器的数量来反应，Mealy机具有较少的状态，为此具有较少的触发器