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