DFA 接受問題（the DFA acceptance problem）

這是你能對有限自動機提出的最基本的計算問題：給定一台特定的確定型有限自動機（deterministic finite automaton, DFA）與一個特定的輸入字串，這台自動機是否接受那個字串？寫成語言，就是集合 A_DFA = {(B, w) : B 是一台 DFA 且 B 接受 w}。像一座只記得自己處在哪個狀態的旋轉閘門，DFA 在固定輸入上的行為完全是機械式的，所以這個問題有個極為簡單、總會停機的答案。

判定程序就是去模擬。讀入 DFA B 的編碼（它的狀態、字母表、轉移函數 δ（delta）、起始狀態與接受狀態）以及字串 w。把手指放在起始狀態上。對 w 的每個符號依序，沿著唯一的轉移 δ(狀態, 符號) 走到下一個狀態。沒有選擇、也不必回溯——DFA 是確定型的，每個符號恰好導向一個下一狀態。讀完 w 的最後一個符號後，檢查目前狀態是否為接受狀態：是就接受、否就拒絕。這個模擬恰好做 |w| 次轉移然後停下，所以它總會停機。

因此 A_DFA 是『可判定』的。這是一個基礎的「健全性」結果：最簡單的計算模型，其成員問題顯然可判定。它也鋪陳了一個反覆出現的主題。同一個表面問題——「這台機器是否接受這個輸入？」——對 DFA（以及 NFA 和 CFG）可判定，但對圖靈機卻變成不可判定的 A_TM。原因正是：DFA 的執行是有界的（它持續 |w| 步且不可能迴圈），而圖靈機的執行可以永遠遊蕩下去。