指數爆炸（the exponential blowup）
當你把一個 NFA 確定化時，新 DFA 的狀態是 NFA 狀態的「集合」。一個有 n 個狀態的 NFA 有 2^n 個可能的子集，所以最壞情況下，DFA 可能需要多達 2^n 個狀態——例如從 20 個狀態暴增到超過一百萬個。把一台 n 狀態的 NFA 轉成 DFA 時這種最壞情況的大小暴增，就叫指數爆炸。這是你為非確定性的便利可能付出的代價。
這不只是理論上的杞人憂天；有具體的語言會逼出它。教科書上的見證又是「倒數第 k 個符號是 a」：NFA 只需約 k+1 個狀態，但可以證明，「任何」辨識此語言的 DFA 都至少需要 2^k 個狀態，因為 DFA 必須區分「最後 k 個符號」的全部 2^k 種可能樣式——沒有更小的機器能辦到。所以這個爆炸有時是真的無法避免，而不只是構造方法笨拙。
兩點誠實的補充能讓我們看清全貌。第一，2^n 是上界、是最壞情況；子集構造法只建造「可達」的子集，對多數 NFA 而言那只是全部 2^n 中極小的一部分，所以得到的 DFA 常常與 NFA 大小相當。第二，爆炸關乎「大小」，絕不關乎「能力」——DFA 辨識的仍是完全相同的正規語言。實務上的教訓很簡單：轉換可能耗記憶體，所以直接處理 NFA（或讓它惰性展開）的工具，往往效率高得多。
對「倒數第三個符號是 a」：NFA 有 4 個狀態，最小的 DFA 有 2^3 = 8 個。把 k 推高：在 k = 20 時，NFA 仍維持約 21 個狀態，而每一台 DFA 都至少需要 2^20 = 1,048,576 個狀態。這個落差就是指數爆炸的具體化。
一台 n 狀態的 NFA 可能需要多達 2^n 個 DFA 狀態；有時這個界限可被證明是無法避免的。
2^n 是最壞情況的「上界」，不是每次都會發生——只有可達的子集會被建出來。而且爆炸影響的是大小，從不影響所辨識的語言。