非確定型有限自動機（nondeterministic finite automaton）

確定型有限自動機（DFA）就像一台販賣機：在每個狀態下，對你投入的每一枚硬幣都只有唯一一種反應——按下按鈕，就只會發生一件確定的事。非確定型有限自動機（NFA）放寬了這一點：在某個狀態下讀到某個符號時，機器可能有好幾個被允許的下一狀態，也可能一個都沒有。它就是內建了「猜測」能力的有限自動機，只要「有一條」合法的選擇序列通往接受狀態，它就接受該字串。

形式上，NFA 是一個五元組 (Q, Σ, δ, q0, F)：一個有限的狀態集合 Q；一個輸入字母表 Σ（Sigma）；一個轉移函數 δ（delta），它在給定一個狀態與一個符號時，回傳的是一個狀態「集合」（Q 的一個子集），而不是單一狀態；一個起始狀態 q0；以及一組接受狀態 F。與 DFA 的關鍵差異就在 δ 的輸出型別：DFA 是 δ(q, a) = p（單一狀態），而 NFA 是 δ(q, a) = 一個集合，例如 {p, r}——可能是空集，也可能有好幾個。許多定義還允許 ε-移動，也就是不讀任何符號就換狀態。

為什麼要費這個事？因為 NFA 往往比等價的 DFA 小得多、也好設計得多，而它們辨識的語言族恰好相同——都是正規語言。NFA 並沒有更強的能力（每個 NFA 都能用子集構造法轉成 DFA）。它帶來的好處純粹是簡潔與設計上的清晰：你只要描述「要找什麼」，剩下的記帳工作就交給「猜測」去處理。