轉移到一個狀態集合（a transition to a set of states）

DFA 與 NFA 之間全部的形式差異，都集中在一個地方：轉移函數 δ（delta）的型別。在 DFA 中，δ 吃一個狀態與一個符號，回傳恰好一個狀態——δ(q, a) = p。在 NFA 中，δ 吃一個狀態與一個符號，回傳的是一個「狀態集合」——Q 的一個子集——寫作 δ(q, a) ⊆ Q（Q 的子集）。這個集合可能有好幾個成員（分岔）、恰好一個成員（被迫的移動），或是空集 ∅（空集合，代表此路不通）。

因此，對一個在字母表 Σ（Sigma）上的 NFA，其簽章是 δ : Q × Σ → P(Q)，其中 P(Q) 是 Q 的冪集（Q 所有子集所成的集合）。用白話讀：從每個狀態、對每個符號，機器宣告它「被允許」移動到的完整狀態集合。空集是一個完全合法的值，這正是 NFA 用來表達「這裡沒有移動可走」的方式，而不必另外發明一個明確的陷阱狀態。ε-NFA 更進一步擴充這個想法，連空字串 ε（epsilon）上的轉移也一併定義。

這個「集合值」的 δ，正是非確定性寫起來如此精簡的原因：你不必小心翼翼地把每個（狀態，符號）配對都導向唯一的目的地、還要發明死狀態去吸收不可能的輸入，而是只列出被允許的目標，剩下的交給存在式的接受規則。當你日後執行子集構造法時，這個集合值的 δ 恰好就會變成某台 DFA 的單值 δ——而那台 DFA 的狀態「就是」NFA 狀態所成的集合。