NFA 與 DFA 的等價（NFA-DFA equivalence）

你或許會合理地猜想：一台能複製自己、探索多條路徑的機器，會比被迫只走單一路徑的機器更強。但等價定理出人意料地說「不」：對有限自動機而言，非確定性在「純粹能力」上沒有給你任何好處。每一個被某 NFA 辨識的語言，也都被某 DFA 辨識，而且（理所當然地）每個 DFA 本來就是一個 NFA。這兩個模型是等價的——它們辨識的恰好是同一族，即正規語言。

證明分兩個方向。容易的方向：DFA 不過是一種轉移集合「恰好總是只有一個元素」且沒有 ε-移動的 NFA，所以每個 DFA 本來就是 NFA。實質的方向：給定任一 NFA，子集構造法會建出一台 DFA，其狀態是 NFA 狀態的集合，再對輸入長度做歸納，證明 DFA 抵達的「恰好」是 NFA 此時可能所處的狀態集合——所以 DFA 接受某字串，當且僅當 NFA 接受它。兩個方向都得到同一個語言。

其結論是理論的基石事實之一：NFA 與 DFA 可以互換，所以你可以挑方便的那個來設計，需要時再轉換。不過要對這裡的「等價」說精確。它指的是「相同的辨識能力」（相同的語言），而不是「相同的大小」——等價的 DFA 可能指數倍大。而且這只對「有限」自動機成立：類比的說法在下推自動機上失敗，那裡確定型與非確定型版本的能力是真的不同。