有限状态自动机
维基百科，自由的百科全书
有限状态自动机（FSM "finite state machine" 或者FSA "finite state automaton" ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。
有多种类型的有限状态自动机：接受器判断是否接受输入；转换器对给定输入产生一个输出。常见的转换器有 Moore机 与 Mealy机。Moore 机对每一个状态都附加有输出动作，Mealy 机对每一个转移都附加有输出动作。
有限状态自动机还可以分成确定与非确定两种。非确定有限状态自动机可以转化为确定有限状态自动机。
有限状态自动机识别的语言是正规语言。
有限状态自动机除了它在理论上的价值，还在数字电路设计、词法分析、文本编辑器程序等领域得到了应用。
目录 |
[编辑] 形式定义
[编辑] 确定有限状态自动机
一个确定有限状态自动机（DFA "Deterministic finite automaton"）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F)
- 有穷状态集合 Q ；
- 有穷输入字母表 Σ；
- 转移函数 δ: Q × Σ -> Q；
- 初始状态 q0；
- 终结状态集合 F，F 包含于 Q 。
自动机从初始状态 q0 起，逐一读入输入串（由输入字母表 Σ 的字母构成）的每一个字母，根据当前状态、输入字母和转移函数 δ 决定自动机的下一步状态；如果输入串结束时，自动机处于终结状态集合 F 的某一个状态，这表示自动机接受该字串；否则自动机不接受该字串。
自动机接受的所有字串构成了自动机识别的语言 L(M)。
[编辑] 非确定有限状态自动机
一个非确定有限状态自动机（NFA "Non-deterministic finite automaton"）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F)
- 有穷状态集合 Q ；
- 有穷输入字母表 Σ；
- 转移函数 δ: Q × Σ -> 2Q；
- 初始状态 q0；
- 终结状态集合 F，F 包含于 Q 。
自动机从初始状态 q0 起，逐一读入输入串（由输入字母表 Σ 的字母构成）的每一个字母，根据当前状态、输入字母和转移函数 δ 决定自动机的下一步状态；如果输入串结束时，自动机处于终结状态集合 F 的某一个状态，这表示自动机接受该字串；否则自动机不接受该字串。
非确定有限状态自动机与确定有限状态自动机的唯一区别是它们的转移函数不同。确定有限状态自动机对每一个可能的输入只有一个状态的转移。非确定有限状态自动机对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。
自动机接受的所有字串构成了自动机识别的语言 L(M)。1
[编辑] 有限状态自动机的最小化
根据 Myhill-Nerode 定理，在同构意义下接受一个正则语言的最少状态的确定有限状态自动机是唯一的。同时我们还存在有效的算法（时间开销是O(n2)的）构造出与给定确定有限状态自动机等价的最小化的确定有限状态自动机。
[编辑] 计算能力与判定问题
确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质，许多为其他自动机（下推自动机或图灵机）不能判定的问题，在有限状态自动机的情形下，都可以得到判定，并且存在有效的算法。
对一个确定有限状态自动机，下述判定问题都可以判定，并且存在有效的算法。
- 该自动机识别的语言是否为空集。
- 该自动机识别的语言是否为有限集。
- 该自动机是否与另一个确定有限状态自动机识别同一个的语言
[编辑] 参考条目
- 马文·明斯基
