有穷状态自动机简单介绍
十月 13, 2009 – 5:40 下午有穷状态自动机，名字听起来很牛。
我在sql_parse的词法解析的过程中使用过，但是一直没仔细的学习过。
最近从图书馆借了这方面的书，仔细看一看，学习学习。
计算机理论的东西实在很深奥，我只能谈谈自己的理解，并不一定那么准备，仅供参考。
有穷状态自动机顾名思义是由有限个状态组成的，在有限个输入的情况下在这些状态中转移并期望最终达到终止状态。
这个定义是我自己遍的。
有穷指的是自动机的状态个数是有限的。
有穷状态自动机根据确定性可以分为确定有穷状态自动机和非确定有穷自动机。
下面通过数学表达式更加严谨的介绍下这两个概念。
确定有穷状态自动机
一个确定有限状态自动机（DFA “Deterministic finite automaton”）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F)
有穷状态集合 Q ；
有穷输入字母表 Σ；
转移函数 δ: Q × Σ -> Q；
初始状态 q0；
终结状态集合 F，F 包含于 Q 。
自动机从初始状态 q0 起，逐一读入输入串（由输入字母表 Σ 的字母构成）的每一个字母，根据当前状态、输入字母和转移函数 δ 决定自动机的下一步状态；
如果输入串结束时，自动机处于终结状态集合 F 的某一个状态，这表示自动机接受该字串；否则自动机不接受该字串。
非确定有穷状态自动机
一个非确定有限状态自动机（NFA “Non-deterministic finite automaton”）M 是由下述元素构成的五元组 (Q,Σ,δ,q0,F)
有穷状态集合 Q ；
有穷输入字母表 Σ；
转移函数 δ: Q × Σ -> 2Q；
初始状态 q0；
终结状态集合 F，F 包含于 Q 。
自动机从初始状态 q0 起，逐一读入输入串（由输入字母表 Σ 的字母构成）的每一个字母，根据当前状态、输入字母和转移函数 δ 决定自动机的下一步状态；
如果输入串结束时，自动机处于终结状态集合 F 的某一个状态，这表示自动机接受该字串；否则自动机不接受该字串。
确定有穷状态自动机和非确定有穷状态自动机的唯一区别在于：
对于确定有穷状态自动机来说，任意一个当前状态和任意一个输入转移函数的结果不会超过1，也就是最多可以确认唯一的一个状态。
而对于非确定有穷状态自动机来说，存在一个当前状态和一个输入使得转移函数的结果会超过1，也就是可能会有多个状态对应。
确定指的就是自动机的转移函数是否可以确认唯一的状态。
生活中有很多的例子可以用来说明两者的区别，
比如说父亲和子女，一个子女只会有一个父亲，这是确定的。反过来一个父亲可能会有多个孩子，这是不确定的。
表示有穷状态自动机有两种常用的方法，状态图和状态表。
下面通过状态表来表示下两种有穷状态机。
1,确定有穷状态自动机(DFA)
1 0
a a b
b c c
在状态a和b的情况下，无论输入是1还是0都可以得到确定的下一个状态。
2,非确定有穷状态自动机(NFA)
1 0
a {a,b} b
b c c
在状态a的情况下，输入为1时不能确定下一个状态到底是a还是b。
