状态机
状态机，表示若干个状态，以及在这些状态之间的转义和动作的模型。1 状态机是一个离散数学模型。给定一个输入集合，根据对输入的接受次序来决定一个输出集合。
-
有限状态机
-
无限状态机
一般认为无限状态机很好，因为这表示计算能力更强，但是有限状态理论和模型在实践中更容易检验。 有限状态机的计算能力等价于正则语言，无限状态机用于描述非确定性问题，计算能力等价于自然语言。
有限状态机
有限状态机 finite-state machine， FSM， 输入集合和输出集合都是有限的，并只有有限数目的状态。 一般说到状态机即是对有限状态机的简称。
-
接受器和识别器
-
变换器
-
Moore机（摩尔型有限状态机），输出只依赖于状态
-
Mealy机，（米利型有限状态机），输出依赖于输入和状态。Mealy FSM的使用经常可以使状态数简约。
FSM的下一个状态和输出是由输入和当前状态决定的。
如果输出函数是状态和输入字母表的函数，则定义对应于Mealy模型，它可以建模为Mealy机。
如果输出函数只依赖于状态 ，则定义对应于Moore模型，它可建模为Moore机。
根本没有输出函数的有限状态机叫做半自动机或转移系统。
有限状态机的分类
-
确定有限状态机，deterministic finite automaton, DFA 2
-
非确定有限状态机，non-deterministic finite automaton, NFA
确定有限状态机
对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，他能根据事先给定的转移函数转移到下一个状态。
-
能被确定有限状态机识别的语言是正则语言
-
确定有限状态机是非确定有限状态机的一种极限形式
-
确定有限状态机在计算能力上等价于非确定有限状态机
非确定有限状态机
对每个状态和输入符号对可以有多个可能的下一个状态的有限状态机。这区别于确定有限状态机（DFA），他的下一个可能状态是唯一确定的。
-
非确定有限状态机可以转化为确定有限状态机。
-
非确定有限状态机接受正则语言。
有限状态机的用途
一个地址分析的有限状态机
-
用它分析网页，找出网页中的地址部分，建立本地搜索的数据库 3
-
可以在搜索引擎中对用户输入的查询进行分析，挑出其中描述地址的部分
有限状态机的缺点 4
-
每一种有限状态机均功能唯一，即设计好之后无法完成其他原理不同的工作；
-
因为其状态有限，当所要描述的系统的状态太多时，可能确定的有限状态机无能为力；
-
有一些任务是有限状态机无法完成的，比如它可以判断输入的0、1数列中0或1的个数是否为奇数或偶数，但是无法判断0是否比1多或者相反。
无限状态机
无限状态机 infinite-state machine，ISM ，输入和输出集合无线，状态数目无限的状态机。
