非确定型有穷自动机

前言

上述在讨论的过程中，计算的每一步都按照唯一的方式跟在前一步的后面。当机器处于给定的状态并读入下一个输入字符时，就可以唯一确定下一个状态。因此称这是 确定型计算，在 非确定型 机器中，任何一个点，下一个状态都可能存在若干个 选择。非确定型是确定型的推广，因此每一台确定型有穷自动机（简称DFA）都是一台非确定型有穷自动机（简称NFA）

NFA状态图

非确定型有穷自动机 N1

需要特别指出NFA与DFA不同之处：

1. 对于1有两个射出的箭头；
2. 对于1没有箭头；
3. 中包含 的箭头；

如果一个状态，在射出的箭头上标有 ，则不用读任何输入，机器分裂成多个备份，每一个标记 的射出箭头有一个备份跟踪，还有一个备份停留在当前状态。然后机器和前面一样非确定性的运行。这里可以把非确定性看做是若干独立的“过程”或者“线程”分别的进行，如果这些子过程至少有一个接受，则整个过程计算接受。以 接受 010110 的计算为例：

NFA 示意图

类似的给出 非确定性有穷自动机 的5元组描述 ，其中

1. 是有穷的状态集
2. 是有穷的字母表
3. 是转移函数
4. 是起始状态
5. 是接受状态集

这里的 是任意的集合 的所有子集组成的集合，称 是 的幂集 ；

由此我们可以用5元组来描述上面的非确定性有穷自动机：，其中

1. 
2. 
3. 由下表给出：
   NFA 转移函数
4. 是起始状态
5. 

同样 NFA 计算的形式化定义 也和 DFA 类似，设 是一台NFA， 是一个字符串并且其中任一 是字母表 的成员，如果存在 中的状态序列是 ，满足下述条件：

1. 
2. 
3. 

则称 接受 ;