自动机
自动机是一种判断一个信号序列是否满足特定规则的数学模型
- 信号序列：一个按顺序排列的信号，可以是字符串，数字等
- 判断满足规则：该序列是否属于某个特定集合，返回真或假
自动机由输入，状态与输出组成，从起始状态开始，每一次转换，函数根据当前状态与输入，决定下一个状态
若最后达到了一个可接受的状态，则称自动机接受这个输入，返回真，否则称不接受，返回假
确定有限状态自动机
确定性有限状态自动机(DFA)状态数量有限且转移方式确定，由五部分组成：
- 有限状态集合：自动机中所有可能的状态
- 起始状态：从该状态开始
- 接收状态集合：可以接受的输入可以到达的状态
- 字符集：可接受的输入
- 转移函数：自动机状态间转移方式
因此可以用一个有向图表示，状态相当于有向图的顶点，转移函数相当于有向图的边
特别的，如果一个状态没有对应的转移，我们认为转移到状态null，状态null只能转移到它自己，且不是接收状态
求出输入串在DFA中的状态序列，并判断它是否被接受的过程称为计算
当DFA读入一个字符串时，从初始状态起按照转移函数一个个字符的转移，如果读完一个字符串的所有字符后位于一个接受状态，那么我们称这个DFA接受这个字符串，否则称不接受这个字符串
字符集合上的一个语言，是字符集合上字符串的一个集合，如果一个语言能被某个DFA识别，则称为正则语言
非确定有限状态自动机
确定性有限状态自动机(NFA)对于任意状态和任意字符，都可能存在零个、一个或多个后继状态，且接受空字符（即不消耗任何字符），显然所有DFA都是一个NFA
它的组成和DFA相同，计算过程相当于同时运行多个DFA，每一步都穷举所有可能性，最后只要有一条分支到达接受状态，NFA就接受整个串
由于允许空字符，字符串可以插入任意多的空字符，因此NFA的每次输入可以对应多个结果，形成一个结果集
常见应用
