Lecture 8: 有限状态机 Finite State Machine

概述

有限状态机（有时称为有限状态自动机 finite state automaton）是一种可以用硬件或软件实现的计算模型。
可以用来模拟时序逻辑和一些计算机程序。
有限状态自动机生成正则语言。Finite state automata generate regular languages.
它可用于对许多领域的问题进行建模，包括数学、人工智能、游戏和语言学。

两大有限状态机

Mealy State Machine 米利型有限状态机：基于它的当前状态和输入生成输出
Moore State Machine 摩尔型有限状态机：输出只由当前的状态所确定

有限状态机的特殊类型

DFA 确定性有限状态自动机：每个节点的每个字母只有一种转移路径
NFA 非确定有限状态自动机：每个节点的每个字母有多种可能的转移

FSM 的优点

灵活
易于从抽象转移到代码执行
对处理器的开销比较低
可以轻松确定状态的可达性

FSM 的缺点

不适用于所有的领域
在游戏等领域，可能不需要 FSM 的预期特性（expected character）
状态转移的顺序不灵活
如果没有设计理念，那么大型的 FSM 将难以管理