非确定有限自动机（Non-deterministic Finite Automaton，简称NFA）是一种用来描述、分析和设计计算机系统的数学模型。它由以下元素组成：
有限的状态集合：
一个包含有限个状态（S）的集合。
输入符号的有限集合：
一个包含有限个输入符号（Σ）的集合，通常还包括空字符ε（epsilon）。
转移函数：
对于每一个状态和每一个属于Σ或{ε}的符号，转移函数定义了输出迁移状态的集合。
初始状态：
一个特定的状态（s0），作为自动机的起始点。
接受状态：
一个状态集合（F），用于标记自动机在处理完特定输入字符串后所达到的终止状态。
NFA的主要特点是在处理输入时，可以从当前状态转移到多个可能的状态，这种不确定性使得NFA在处理某些问题时比确定有限自动机（DFA）更为灵活。例如，在正则表达式匹配、语言识别和网络流量分析等领域，NFA得到了广泛应用。
NFA与DFA的关系
虽然NFA在某些方面比DFA更为强大，但它们都可以用来识别正则语言。实际上，可以通过构造一个特定的DFA来模拟任何NFA的行为，这个过程称为子集构造法（Subset Construction）。这种转换过程有时会导致状态数的急剧增加，因此并不总是最优解。
NFA的应用场景
正则表达式匹配：
NFA非常适合用于匹配正则表达式，因为它们可以处理多字符的转移和ε转移。
语言识别：
在自然语言处理中，NFA可以用于识别语言中的模式。
网络流量分析：
在网络安全领域，NFA可以用于识别和过滤特定的网络流量模式。
示例
考虑以下NFA，它用于识别字符串"aabb"：
```
状态 0： -> 状态 1 （输入a）
状态 1： -> 状态 2 （输入a）
状态 2： -> 状态 3 （输入b）
状态 3： -> 状态 4 （输入b）
状态 4： （接受状态）
```
从状态0开始，依次输入字符a、a、b、b，最终到达状态4，表示该字符串被识别。
总的来说，NFA是一种简单而强大的工具，适用于处理具有不确定性的问题，在计算机科学和工程领域有着广泛的应用。