非確定型有限自動機（NFA）
NFA 的簡潔性（the conciseness of NFAs）
如果 NFA 並不比 DFA 更強，何必用它？理由就和你畫藍圖前先打草稿一樣：NFA 往往小得多、也好設計得多。一個能用乾淨小巧 NFA 描述的性質，可能需要大得多的 DFA——有時是指數倍大。非確定性讓你描述「要找什麼」，把「精確記住自己在哪」這種麻煩的記帳工作往後延。
經典範例是 Σ = {a, b} 上的語言「倒數第 k 個符號是 a」。一個 NFA 用大約 k+1 個狀態就能解：停在起始狀態猜「還沒接近結尾」，然後「猜」出那個倒數第 k 個符號的位置，檢查它是 a，再數掉到結尾的另外 k-1 個符號。但 DFA 實際上必須時時刻刻記住「最近讀到的 k 個符號」，所以它需要約 2^k 個狀態——每個可能的近期符號視窗各對應一個。小小一個非確定型的猜測，取代了龐大的確定型記憶。
這種簡潔性是非確定性之於有限自動機的真正、實際的好處。誠實地把那句叮嚀再說一次：簡潔純粹是描述大小的問題，不是運算得更多。任何 NFA 都能用子集構造法變成 DFA，雖然最壞情況下那台 DFA 可能指數爆炸，但它辨識的「語言」完全相同。NFA 省下的是設計時的人力、常常還有篇幅；它並沒有拓展「什麼是可計算」的邊界。
「倒數第三個符號是 a」（k = 3）：一個 NFA 只需 4 個狀態（猜倒數第三個符號在哪，再讀三個）。最小的等價 DFA 需要 2^3 = 8 個狀態，分別對應它必須記住的「最後三個符號」的每一種可能樣式。
對同一語言，k+1 個狀態的 NFA 對上 2^k 個狀態的 DFA——是簡潔，不是能力。
簡潔只關乎描述長度。NFA 與其 DFA 辨識的是「同一個」語言；非確定性永遠不會讓有限自動機去辨識一個非正規語言。
又称
另见