關於自動機的可判定問題（decidable problems about automata）

把那一長串「關於有限自動機、正規表示式、上下文無關文法、且有保證會停機演算法」的問題集中在一處，會很有幫助。把它想成「關於這些較簡單模型，你『總能』計算出來的事實工具箱」。它們全都可判定的反覆原因是同一個：DFA 只有有限多個狀態、固定輸入產生有界的執行，而 CFG 能化為一種把推導長度限住的正規形式——於是「看起來無窮」的問題塌縮成有限的搜尋。

對確定型與非確定型有限自動機以及正規表示式，下列全都可判定：機器是否接受某個給定字串（接受）；它的語言是否為空（空語言）；它的語言是有限還是無限（檢查「有用路徑上是否有迴圈」）；其中兩者是否識別相同語言（等價，靠「對稱差再測空語言」的技巧）；某個語言是否為另一個的子集（相關的空語言檢查）；語言是否就是整個 Σ*（Sigma-star），即普遍性（測補集是否為空）。因為正規表示式、DFA、NFA 全都可由「總會停機的程序」互相轉換（Thompson 構造法、子集構造法、狀態消去法），對其一成立的結果就轉移到其他。對上下文無關文法，成員（w 是否被產生，靠 CYK）與空語言（它是否能產生任何東西，靠可生成符號標記）都可判定，有限性也可判定。

知道這份目錄既有實用價值，也在概念上重要。實用上，它告訴工具開發者哪些檢查可以放心自動化——正規表示式等價、死碼（無用符號）偵測、可達性分析。概念上，它畫出下一章將跨越的邊界：同樣這些問題，一旦往上爬到上下文無關文法（等價、歧義、普遍性）或圖靈機（接受、空語言、等價，幾乎所有非平凡的問題），就變得『不可判定』。這個模式很乾淨——更多記憶買來更強的表達力，卻以演算法的可判定性為代價。