NFA 的接受（acceptance by an NFA）

一台能往許多方向分岔的機器，要怎麼決定該不該說「是」？規則很寬鬆：只要「存在」至少一條路徑——一串與輸入相符的合法移動序列——能讀完整個字串並停在接受狀態上，NFA 就接受這個字串。把所有分岔的路徑想成一棵「可能性之樹」；當這棵樹至少有一片葉子是接受狀態時，答案就是「是」。

實際操作時，要追蹤機器「可能」所處的狀態「集合」。從起始狀態出發（再加上所有經 ε-移動可達的狀態）。對每個輸入符號，把目前的集合換成：從集合中任一狀態讀該符號可達的所有狀態之聯集（再補上經 ε 可達的狀態）。讀完最後一個符號後，只要最終的集合「含有任一」接受狀態，字串就被接受。若某條路徑「卡住」——走到一個對下一個符號沒有出邊的狀態——它就直接死掉；這本身不會造成拒絕，因為其他路徑可能還活著。

這條「存在式」規則正是非確定性的核心。拒絕是「所有路徑都失敗」的情形：唯有「每一條」可能的路徑都死掉、或都停在非接受狀態時，字串才被拒絕。所以一條存活的接受路徑，就能蓋過任意多條死路或拒絕路徑。這種不對稱——某條路行得通就接受，唯有全部失敗才拒絕——正是讓非確定性成為如此便利的設計視角的原因。