非确定有穷自动机的定义#

非确定有穷自动机（NFA）是一个五元组：

$A = (Q, \Sigma, \delta, q_0, F)$

其中：

• $Q$ 是一个有限的状态集合
• $\Sigma$ 是一个有限的输入符号集合（字母表）
• $\delta: Q \times (\Sigma \cup \{\epsilon\}) \to 2^Q$ 是状态转移函数，定义了在给定状态和输入符号的情况下，自动机可以转移到哪些下一个状态。这里，$\epsilon$表示空字符串，允许自动机在没有输入符号的情况下进行状态转移
• $q_0 \in Q$ 是初始状态
• $F \subseteq Q$ 是终结状态集或接受状态集合

其中和DFA的区别在于$\delta$的定义，DFA的$\delta$是一个函数，定义了每个状态和输入符号对应一个唯一的下一个状态，而NFA的$\delta$是一个多值函数，定义了每个状态和输入符号对应一组可能的下一个状态

条件#

1. 转移是非确定的：对于每个状态 $q \in Q$ 和每个输入符号 $a \in \Sigma$，转移函数 $\delta(q, a)$ 定义了一组可能的下一个状态
2. NFA在任何时候可以处于多个状态
3. NFA接受一个字符串，如果从初始状态出发，按照输入字符串的符号进行状态转移，最终停在一个接受状态上
4. NFA拒绝一个字符串，如果从初始状态出发，按照输入字符串的符号进行状态转移，最终停在一个非接受状态上
5. NFA可以有ε-转移，即可以在没有输入符号的情况下进行状态转移

关系#

1. 每个DFA都是一个NFA，因为DFA的转移函数满足NFA的定义
2. 每个NFA都可以转换成一个等价的DFA，虽然转换可能会导致状态数量的指数增长
3. DFA和NFA接受同样的语言，即它们识别的语言类是相同的，称为正则语言

对于NFA的$\delta$的理解可以参考类UNIX系统调用的fork，NFA的$\delta$就类似于fork，允许自动机在当前状态下分叉成多个状态

转换成DFA-子集构造法#

e.g.

现有一NFA如下：

通过子集构造法得到DFA：

也就是把状态的集合作为一个新状态，每次输入后把所有输出收集起来拼成一个集合作为新的状态，直到没有新的状态产生为止