Formal Language - Ch14.5 歸約相關習題 Exercises for Reducibility

可怕習題一覽~ 多做練習培養decidable和recognizable的直覺~

一、多一歸約與正則語言
因為多一歸約是用「可計算函數」去定義，因此歸約的能力「太強」，導致「分不出」正則語言的難度。

1.1   如果A可多一歸約(mapping reduce)成B ($A \leq_m B$)，且B是正則語言(regular language)，則A也必是正則語言嗎?

Ans : 錯! 

以下是反例 :

• 語言$A = \{0^n1^n\ |\ n \leq 0 \}$
• 語言$B = \{1\}$
• 可計算函數 $f : \Sigma^* \rightarrow \Sigma^* $,
• $f(w)=\begin{cases} 1& \text{if w $\in$ A}\\0& \text{if w $\notin$ A}\end{cases}$

因為A是CFG，也就是可決定語言，所以f是可計算函數，因此$A \leq_m B$，得一反例。

二、$A_{TM}$和$E_{TM}$的歸約

2.1   試證$A_{TM}$不可多一歸約成$E_{TM}$。

Proof : 先設$A_{TM}$可多一歸約成$E_{TM}$，則存在一可計算函數 $f:\Sigma^* \rightarrow \Sigma^*$，對每個 $w$ 而言， $W \in A $ 若且唯若 $ f(w) \in B$。

因此，用同一個可計算函數可得到$A_{TM}' \leq_m E_{TM}'$，但$E_{TM}'$是圖靈可辨識語言，而$A_{TM}'$不是圖靈可辨識語言，矛盾！

三、$EQ_{CFG}$的難度
$EQ_{CFG}$是 undecidable，co-Turing-recognizable的語言。

3.1   Show that $EQ_{CFG}$ is undecidable.

Assume it is decidable. Then there exists a TM $R$ that decides $EQ_{CFG}$. A construction of TM $S$ that uses $R$ to decide $ALL_{CFG}$ follows.

$S$ = On input $⟨G⟩$ , where $G$ is a CFG:

1. Run $R$ on input $⟨G,G_1⟩$ where $G_1$ is a CFG that generates $\Sigma^*$.
2. If $R$ accepts, accept; if $R$ rejects, reject.

If $R$ decides $EQ_{CFG}$, S decides $ALL_{CFG}$. But $ALL_{CFG}$ is undecidable, so $EQ_{CFG}$ must also be undecidable.


3.2   Show that $EQ_{CFG}$ is co-Turing-recognizable. 

This implies that we must show that $EQ_{CFG}'$ is Turing recognizable. Let TM $R$ be a decider for the known decidable language $A_{CFG}$. We use this fact to construct a TM $M$ to recognize $EQ_{CFG}'$.

$M$ = On input $⟨G,G_1⟩$ where $G$ and $G_1$ are CFGs:
1. Convert $G$ and $G_1$ to equivalent CNF CFGs $C$ and $C_1$, respectively.
2. For $i \leftarrow 0, \infty$:
For each string $s$ of length $i$ generated by $C$:
1. Run $R$ on input $⟨C_1, s⟩$.
2. If $R$ rejects, accept.



四、關於迴文(palindrome)
「通常」無論何種複雜的(nontrivial)的特性，輸入的機器M的型別是DFA或CFG的話，是可決定語言；而輸入的機器M的型別是TM的話，是不可決定語言，也就是rice theorem所敘述的道理。

4.1   L = {<M>| M is a DFA that accepts some palindrome } is a decidable language.

Let $PAL_{DFA}$ = {⟨M⟩ | M is a DFA that accepts some palindrome}. To show $PAL_{DFA}$ is decidable, we construct a decider D for $PAL_{DFA}$ as follows (Let K be a TM that decides $E_{CFG}$):

D = “On input ⟨M⟩,
1. Construct a PDA P such that L(P) = {w | w is a palindrome}
2. Construct a PDA Q such that L(Q) = L(P) ∩ L(M)
3. Convert Q into an equivalent CFG G
4. Use K to check if L(G) is empty.
5. If L(G) is empty, reject. Else, accept.

In the above TM,
Step 1 can be done in finite steps.
Step 2 can be done in finite steps.
Step 3 is the conversion of PDA into an equivalent CFG, which can be done in finite steps
Step 4 is done in finite steps, because the decider K can check whether the language of a CFG is empty
In summary, D runs in finite steps for any input, and is thus a decider.


4.2    L = {⟨M⟩ : M is a TM, which accepts some palindrome}.
a) Is L Turing decidable?
b) Is L Turing recognizable?
Note: recall that a palindrome is a string which is equal to its reverse.

Solution:

a): not Turing decidable. This follows from Rice’s theorem as the property defining L is not trivial and it depends on the language accepted by the Turing machine.

b) Turing recognizable. The TM M∗ recognizing L works as follows: given an input ⟨M⟩, for every i = 0,1,2,..., it lists all strings w of length at most i, checks if w is a palindrome and if it is then it simulates M on w for i steps. If M accepts w then M∗ accepts ⟨M⟩, otherwise it continues.