不确定性有限自动机

DFA：当给定了当前所在状态，在遇到一个字符之后，我们就可以确定要向哪一个状态转移。打个比方，就是在我们当前位置没有岔路口，没有给我们多选的机会。
NFA：NFA即不确定性有限自动机（nondeterminism finite automaton）,它允许我们在遇到一个状态时可以有多条转移路径可以选择。特殊的是，它允许我们不读入任何字符就进行状态转移（此操作称为 ϵ−move ϵ − m o v e ）。
能力： 令人惊讶的是，DFA和NFA的能力相同。也就是说，DFA和NFA都只能识别正则语言。所以，现在一种语言是正则的当且仅当它可以被某个DFA或NFA识别。此结论在之后的文章中将会证明。

NFA的正式定义和DFA差不多，但是因为NFA可以同时向多个状态转移，所以它的转移函数的值域应该是状态集 Q Q 的幂集（一个幂集是这个集合的所有子集的集合），记作 P(Q) P ( Q ) 。除此之外，由于NFA还有 ϵ−move ϵ − m o v e ,所以它的转移函数应该是 Q×∑ϵ→P(Q) Q × ∑ ϵ → P ( Q ) ,其中 ∑ϵ=∑∪{ ϵ} ∑ ϵ = ∑ ∪ { ϵ } 。因此我们可以继续用5元组 (Q,∑,δ,q0,F) ( Q , ∑ , δ , q 0 , F ) 定义NFA。
1. Q Q 是有限状态集。
2. ∑ ∑ 是有限字符表。
3. δ δ 是转移函数： Q×∑ϵ→P(Q) Q × ∑ ϵ → P ( Q ) 。
4. q0 q 0 是开始状态，它是 Q Q 中的元素。
5. F F 是接受状态集合， 它是 Q Q 的子集。

对于 N1=(Q,∑,δ,q1,F) N 1 = ( Q , ∑ , δ , q 1 , F ) ,其中
1. Q={  q1,q2,q3,q4} Q = {   q 1 , q 2 , q 3 , q 4 } ，
2. ∑={  0,1} ∑ = {   0 , 1 } ，
3. δ δ 是：

q1q2q3q40{ q1}{ q3}∅{ q4}1{  q1,q2}∅{ q4}{ q4}ϵ∅{ q3}∅∅， 0 1 ϵ q 1 { q 1 } {   q 1 , q 2 } ∅ q 2 { q 3 } ∅ { q 3 } q 3 ∅ { q 4 } ∅ q 4 { q 4 } { q 4 } ∅ ，

4.

q1 q 1 是开始状态，

5.

F={ q4} F = { q 4 } 。

我们假定 N=(Q,∑,δ,q0,F) N = ( Q , ∑ , δ , q 0 , F ) , w=y1y2...ym w = y 1 y 2 . . . y m ,其中 yi∈∑ϵ y i ∈ ∑ ϵ ,如果存在一序列状态 r0,r1,...,rm∈Q r 0 , r 1 , . . . , r m ∈ Q 使得以下3个条件成立，骂我们就说 Nacceptsw N a c c e p t s w :
1. r0=q0 r 0 = q 0 ,
2. ri+1∈δ(ri,yi+1),其中i=0,...,m−1 r i + 1 ∈ δ ( r i , y i + 1 ) , 其 中 i = 0 , . . . , m − 1 ,
3. rm∈F r m ∈ F 。

解释：上述第一个条件是指明NFA从开始状态出发；条件二表示当机器处于状态 ri r i 时，它读到 w w 中的字符时是可以转移到下一个状态的；条件三表明最后的转移状态 rm r m 要属于接受集合。