有限状态自动机

DFA

有限状态自动机（FSM “finite state machine” 或者FSA “finite state automaton” ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。

一般有限状态自动机分为两种，确定有限自动机（DFA）和不确定有限自动机（NFA）。

• 有限状态自动机是具有离散输入和输出的系统的一种数学模型。
  其主要特点有以下几个方面：
  (1)系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。
  (2)我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。
  (3)系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。
  (4)系统中有一个状态，它是系统的开始状态。
  (5)系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子。

确定有限自动机
M =（S，∑，f，So，Z）其中：
S是一个有限状态集合。
∑是一个字母表，输入字符的集合。
f是从S x ∑*至S的子集映照。
S0⊆S，是唯一的初态。
Z⊆S，是一个终态集。
如图：

不确定有限自动机
M =（S，∑，f，So，Z）其中：
S是一个有限状态集合。
∑是一个字母表，输入字符的集合。
f是从S x ∑*至S的子集映照。
S0⊆S，是一个非空初态集。
Z⊆S，是一个终态集。
如图：

NFA与DFA的区别在于初态是否确定。

####NFA转化为DFA:
1. 找出NFA的初态集
2. 找出初态集中的每一个初态分别通过0和1到达的状态
3. 将通过b找到的集合（此集合不能同初态一样也不能为空）重新作为初态，继续b
4. 重复b,c直到没有新的集合
5. 将得到的状态进行编号（这些状态不能重复且不包括空状态）重新连接就是DFA了