DFA 空語言問題（the DFA emptiness problem）
現在問的不是關於某一個字串，而是關於一台 DFA 所識別的『整個語言』：這台 DFA 究竟有沒有接受『任何』字串，還是它的語言是空的？寫成語言，E_DFA = {B : B 是一台 DFA 且 B 的語言是空集合 ∅}。你也許擔心這要檢查無窮多個字串，其實不必——有個巧妙的辦法，只看機器的接線就能了結。
訣竅是忘掉字串，把 DFA 看成一張「狀態為點、標籤箭頭為邊」的圖。一台 DFA 接受某個字串，若且唯若存在一條從起始狀態通往至少一個接受狀態的轉移路徑。（一條路徑沿途拼出的符號『就是』一個被接受的字串，而任何被接受的字串都描出這樣一條路徑。）於是問題化為純粹的可達性：從起始狀態出發，反覆把「從已標記狀態經一次轉移可達」的每個狀態都標記起來，直到沒有新狀態被標記為止。這個標記過程會停，因為狀態只有有限多個。停下時，檢查是否有任何接受狀態被標記。若沒有，語言為空（把 B 接受進 E_DFA）；若有，語言非空（拒絕）。
因此 E_DFA 是『可判定』的。這是個小而關鍵的結果。它顯示：即使是一個對無窮多個可能輸入做量化的問題，也能用一次有限的圖搜尋來判定，因為有限自動機只有有限多個狀態要探索。空語言測試也是一個常用的主力，用來建構其他判定程序——例如，要判定兩台 DFA 是否等價，就化約成對一台巧妙合成出來的機器做空語言測試。
一台 DFA，若它唯一的接受狀態從起始狀態根本到不了（沒有任何箭頭鏈通到它），它的語言為空：可達性標記從不碰到那個接受狀態，於是把它接受進 E_DFA。一台 DFA，若起始狀態本身就是接受狀態，它的語言非空（空字串被接受）。
空語言 = 從起始狀態到任何接受狀態都沒有路徑——一次有限的可達性搜尋即可了結。
測試空語言時你『不』去枚舉字串——那會是無窮的。你在有限的狀態圖上搜尋是否能到達某個接受狀態，這總會終止。