非确定有限状态自动机 在计算理论中非确定有限状态自动机或非确定有限自动机NFA是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机这区别于确定有限状态自动机DFA它的下一个可能状态是唯一确定的尽管DFA和NFA有不同的定义在形式理论中可以证明它们是等价的就是说对于任何给定NFA都可以构造一个等价的DFA反之亦然通过使用幂集构造两种类型的自动机只识别正则语言非确定有限自动机有时被称为有限类型的子移位subshift非确定有限状态自动机可推广为概率自动机它为每个状态转移指派概率 非确定有限自动机是Michael O Rabin和达纳斯科特Dana Scott在年介入的他们证明了它与确定自动机的等价性