判定问题 ¶

\(A_{\text{DFA}}=\{\texttt{"}D\texttt{"}\texttt{"}w\texttt{"}: D\text{ is a DFA that accpets }w\}\)

设计一个图灵机 \(M_{R_1}\) 判定这个问题，输入为 \(\texttt{"}D\texttt{"}\texttt{"}w\texttt{"}\)

0. 默认的判断（以后不再重复写）
   1. 如果输入是非法的，则 reject
   2. 如果输入是合法的，则进行解码，得到 \(D\) 和 \(w\)
1. run \(D\) on \(w\)
2. if \(D\) ends with final (\(D\) accept \(w\))
3.   accept \(\texttt{"}D\texttt{"}\texttt{"}w\texttt{"}\)
4. else
5.   reject

\(A_{\text{NFA}}\)，即 NFA \(N\) 是否接受字符串 \(w\)

\(M_{R_2}\) = on input \(\texttt{"}N\texttt{"}\texttt{"}w\texttt{"}\)

1. \(N\) -> an equivalent DFA \(D\)
2. run \(M_{R_1}\) on \(\texttt{"}D\texttt{"}\texttt{"}w\texttt{"}\)
3. return the result of \(M_{R_1}\)

\(\texttt{"}N\texttt{"}\texttt{"}w\texttt{"}\in A_{\text{NFA}}\) <=> \(\texttt{"}D\texttt{"}\texttt{"}w\texttt{"}\in A_{\text{DFA}}\) 称为 a reduction from \(A_{\text{NFA}}\) to \(A_{\text{DFA}}\)，即规约

\(A_{\text{REX}}=\{\texttt{"}R\texttt{"}\texttt{"}w\texttt{"}: R\text{ is a regular expression that generates }w\}\)

\(M_{R_3}\) = on input \(\texttt{"}R\texttt{"}\texttt{"}w\texttt{"}\)

1. \(R\) -> an equivalent NFA \(N\)
2. run \(M_{R_2}\) on \(\texttt{"}N\texttt{"}\texttt{"}w\texttt{"}\)
3. return the result of \(M_{R_2}\)

\(E_{\text{DFA}}=\{\texttt{"}D\texttt{"}: D\text{ is a DFA with }L(D)=\emptyset\}\)

\(M_{R_4}\) = on input \(\texttt{"}D\texttt{"}\)

1. if \(D\) has no final state
2.   accept
3. else
4.   "conceptually" do BFS in the diagram
5.   if there is a path from \(s\) to a final state
6.     reject
7.   else
8.     accept

\(EQ_{\text{DFA}} = \{\texttt{"}D_1\texttt{"}\texttt{"}D_2\texttt{"}: D_1\text{ and }D_2\text{ are two DFAs with }L(D_1)=L(D_2)\}\)

Hint:

• 对称差 \(A\oplus B=\{x\in A\cup B\text{ and }x\notin A\cap B\}=A\cup B - A\cap B\)
  • \(A\oplus B = (A\cup B)\cap(\overline{A\cap B}) = (A\cup B)\cap(\overline{A}\cup\overline{B})\)
• \(A=B\) iff \(A\oplus B = \emptyset\)（可以借此规约至 \(R_4\)）

\(M_{R_5}\) = on input \(\texttt{"}D_1\texttt{"}\texttt{"}D_2\texttt{"}\)

1. construct \(D_3\) with \(L(D_3) = L(D_1)\oplus L(D_2)\)
2. run \(M_{R_4}\) on \(\texttt{"}D_3\texttt{"}\)
3. return the result of \(M_{R_4}\)

\(A_{\text{CFG}} = \{\texttt{"}G\texttt{"}\texttt{"}w\texttt{"}: G\text{ is a CFG that generates }w\}\)

\(M_{C_1}\) = on input \(\texttt{"}G\texttt{"}\texttt{"}w\texttt{"}\)

1. \(G\) -> \(G'\) in CNF
2. enumerate all the derivations of length \(2|w|-1\)
3. if any of them generates \(w\)
4.   accept \(\texttt{"}G\texttt{"}\texttt{"}w\texttt{"}\)
5. else
6.   reject

\(A_{\text{PDA}} = \{\texttt{"}P\texttt{"}\texttt{"}w\texttt{"}: P\text{ is a PDA that accepts }w\}\)

可以规约到问题 \(C_1\)。

\(E_\text{CFG} = \{\texttt{"}G\texttt{"}: G\text{ is a CFG with }L(G)=\emptyset\}\)

提供一个算法来进行判断：

• 标记所有的 terminal symbol
• 如果一个规则的右侧均被标记，则同样标记左侧符号出现的所有位置
• 最终无法进一步标记时，如果 S 被标记了，则 \(L(G)\) 不为空

S 被标记了相当于存在一种方案可以推导至均为 terminal。

e.g. S->Aa A->CB C->e C->a B->b，先标记 abe，再标记 CB，再标记 A（因为 A->CB），再标记 S，所以这个 CFG 的 language 不为空。

可以规约到 \(C_3\)。

试图进行规约 \(H\leq A_1\)，根据规约的定义需要满足将任意输入给 \(H\) 的字符串 \(\texttt{"}M\texttt{"}\texttt{"}w\texttt{"}\) 转换为输入给 \(A_1\) 的字符串 \(\texttt{"}M^*\texttt{"}\)，满足 \(M\) 在 \(w\) 上停机当且仅当 \(M^*\) 在 \(e\) 上停机。

则定义图灵机 \(M^*\) = on input \(u\)

1. run \(M\) on \(w\)

这样就可以达到效果。即 \(M^*\) 在 \(e\) 上停机 <=> \(M^*\) 在某些字符串上停机 <=> \(M^*\) 在任意输入上停机 <=> \(M\) 在 \(w\) 上停机。

根据上面 \(A_1\) 的结论，使用 \(M^*\) 即可，是完全等价的。

同理等价

尝试规约 \(A_3\leq A_4\)，\(A_3\) 的输入为 \(\texttt{"}M\texttt{"}\)，\(A_4\) 的输入为 \(\texttt{"}M_1\texttt{"}\texttt{"}M_2\texttt{"}\)，需要满足 \(M\) 在任意输入上停机当且仅当 \(M_1\) 和 \(M_2\) 半判定的语言相同。

令 \(M_1\) = \(M\), \(M_2\) = on input \(x\):

1. halts

这样我们知道 \(M_2\) 会在任意输入上停机，所以 \(M\) 在任意输入上停机 <=> \(M\) 即 \(M_1\) 和 \(M_2\) 半判定的语言相同。

问题 \(\overline{R_\text{TM}} = \{\texttt{"}M\texttt{"}: M\text{ is a TM with }L(M)\text{ is not regular}\}\) 是可判定的则 \(R_\text{TM}\) 也是可判定的。

接下来尝试规约 \(H\leq\overline{R_\text{TM}}\)，\(H\) 的输入 \(\texttt{"}M\texttt{"}\texttt{"}w\texttt{"}\) 转换为 \(\overline{R_\text{TM}}\) 的输入 \(\texttt{"}M^*\texttt{"}\)，需要满足 \(M\) 在 \(w\) 上停机当且仅当 \(L(M^*)\) 不是 regular 的。

构造图灵机 \(M^*\) = on input \(x\)

1. run \(M\) on \(w\)
2. run \(U\) on \(x\)

则 \(L(M^*)\) 有两种情况：

• 在第一行停机时 \(L(M^*) = L(U) = H\)
• 在第一行不停机时 \(L(M^*) = \emptyset\)

因为 \(\emptyset\) 是 regular 的，所以 \(L(M^*)\) 不是 regular 的 <=> \(M\) 在 \(w\) 上停机。

同上，\(\emptyset\) 也是 context-free 的，所以同样可以规约 \(H\leq CF_\text{TM}\)。

同上，\(\emptyset\) 也是 recursive 的，所以同样可以规约 \(H\leq REC_\text{TM}\)。

将所有输入的字符串按照长度降序排列为 \(s_1, s_2, \cdots\)，idea 是对每个串同时并行跑图灵机，直到有一个输入停机，这就半判定了。不过因为字符串可能是无穷多的，所以当然没办法并行跑无穷个图灵机。解决方案是将二维无穷结构一维化，即先对 \(s_1\) 跑一步，没停机就对 \(s_1\) 和 \(s_2\) 都跑两步，没停机就对 \(s_1, s_2, s_3\) 都跑三步，以此类推。这样就可以保证每个串都会被跑到，假设在 \(s_j\) 的第 \(k\) 步停机的话，则跑 \(\max(j, k)\) 步即可。

即定义图灵机 \(M_A\) = on input \(\texttt{"}M\texttt{"}\):

1. for \(i = 1, 2,\cdots\)
2.   for \(s = s_1, s_2, \cdots, s_i\)
3.     run \(M\) on \(s\) for \(i\) steps
4.     if \(M\) halts on \(s\) within \(i\) steps
5.       halt

假设 \(H\) 是可判定的，则存在 \(M_H\) 判定 \(H\)。接下来构造图灵机 \(R\) = on input \(w\):

1. obtain \(\texttt{"}R\texttt{"}\)
2. run \(M_H\) on \(\texttt{"}R\texttt{"}w\)
3. if \(M_H\) accepts \(\texttt{"}R\texttt{"}w\)
4.   looping forever
5. else // \(M_H\) rejects \(\texttt{"}R\texttt{"}w\)
6.   halt

意思就是如果第三行成立，那么就说明 \(M_H\) 认为 \(R\) 在 \(w\) 上停机，所以接下来会进入第四行死循环，导致 \(R\) 在 \(w\) 上并没有停机。否则第五行成立，说明 \(M_H\) 认为 \(R\) 在 \(w\) 上不停机，但接下来第六行又会停机。产生了矛盾，所以假设并不成立。