決定性問題是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。
注意在翻譯上 decidable 和 deterministic 都可以翻作「決定性」，但是意思和用法差很多，前者是問題可分Yes和NO，後者是狀態機能不能「分支」。
圖靈可決定語言定義
設 $S ⊆ \Sigma^*$ 是一個語言，$M$ 是一台圖靈機， 若對於任何字符串 $\omega \in \Sigma^*$，有
- $\omega \in S$ 若且唯若 $M$ 接受 $\omega$
- $\omega \notin S$ 若且唯若 $M$ 拒絕 $\omega$
圖靈可決定語言閉包性質
可決定語言是在下列運算下是閉合的。就是說，如果 L 和 P 是兩個可決定語言，則下列語言也是可決定語言:
- L 的Kleene星號：$L^*$
- L的非刪除(non-erasing)同態：$\phi(L)$
- L 和 P 的串接： $L \circ P$
- 並集：$L \cup P$
- 交集：$L \cap P$
- L 的補集：$L'$,
- 差集：$L - P$ ,
決定性問題 (Decision problem) 討論方向
- A：Accept，是否一個自動機會接受一個字串。
- E：Empty，是否一個自動機會接受任何一個字串 (沒有的話為空，接受)
- EQ：Equal，是否兩個自動機相等。
ㄧ、接受問題 (Accept Problem)
$A_{DFA}$是一個決定性語言
$A_{DFA} = \{ (B,w)\ |\ B 是接受字串w的DFA\ \}$
證明概念：
- 在機器$B$上模擬字串$w$。
- 如果模擬結束後在接受狀態就接受該字串，反之則拒絕該字串。
- [用心去感覺] $A_{DFA}$、$A_{NFA}$、$A_{REX}$
- $A_{NFA}$ 也是一個決定性語言 (因為 DFA = NFA)
- $A_{REX}$ 也是一個決定性語言 (因為 DFA = NFA = Regular Expression)
$A_{CFG}$是一個決定性語言
$A_{CFG} = \{ (B,w)\ |\ B 是接受字串w的CFG\ \}$
證明概念：
- 把G轉成喬姆斯基範式(chomsky normal form)。
- 在喬姆斯基範式中最多要 2n-1 步可找到所有接受的字串。 (n是字串長 : n-1次增長，n次轉至終止符號)
- 所有找到的字串有w的話接受，反之拒絕。
二、空問題 (Empty Problem)
$E_{DFA}$是一個決定性語言
$E_{DFA} = \{ ⟨D⟩\ |\ D 是一個 DFA 且 L(D) = \phi \}$
證明概念：
- 標記起始點。
- 以寬度優先搜尋走訪n層（因為狀態有n個），走到的狀態就標記。
- 若沒有接受狀態被標記，就接受，反之拒絕。
$E_{CFG}$是一個決定性語言
$E_{CFG} = \{ ⟨D⟩\ |\ D 是一個 CFG 且 L(D) = \phi \}$
證明概念：
- 因為可能由 變數(variable)$\rightarrow$變數 而沒有終止符號(terminal)，所以從終止符號倒推，似CYK演算法。
- 標記所有終止符號。
- 標記可倒推的變數。
- 若起始變數沒有被標記，就接受，反之拒絕。
三、相等問題 (Equal Problem)
$EQ_{DFA}$是一個決定性語言
$EQ_{DFA} = \{ <A,B> \ |\ A和B是DFA，且 L(A) = L(B) \}$
證明概念：構造一個新的DFA為$C$，$L(C) = ( L(A) \times L(B)' ) + ( L(A)' \times L(B) )$，如果A和B辨認(recognize)同一個語言 ，C將接受「空」。
$EQ_{CFG}$ 是一個非決定性語言 (undecidable language)
References
Wiki - 決定性問題
交大陳穎平教授正規語言講義
發表文章
