1 语言类的计算性实例
若以√表示问题可判定，以×表示问题不可判定，则有下表：
| 乔姆斯基谱系 | 语言类 | 自动机 | 接受性 | 空性 | 满性 | 等价性 |
|---|---|---|---|---|---|---|
| 3型文法 | 正则语言 | DFA,NFA,REX | √ | √ | √ | √ |
| 2型文法 | 上下文无关语言 | PDA,CFG | √ | √ | × | × |
| 1型文法 | 上下文有关语言 | LBA,CSG | √ | × | × | × |
| 0型文法 | 图灵可识别语言 | TM | × | × | × | × |
接下来尽可能的一一证明。
每个证明均是按照：
- 先给出定义
- 若可判定，则给出判定器的构造；
- 若不可判定，则尽可能的给出归约。
1.1 正则语言类
DFA,NFA,REX互相等价，故在证明中不做区分。他们的之间的转化都可以交给图灵机完成。
1.1.1 $A_{DFA}$可判定
- 定义
- 给出判定器(第三版书-P123)
直接让图灵机解码$M$和$w$运行看结果就好了。
1.1.2 $E_{DFA}$可判定
- 定义
- 判定器(第三版书-P124)
先解码$M$，然后从初始状态出发，有转移函数路径就染色；
终止后检查所有被染色的状态，若有接收状态则拒绝，否则就接受。
1.1.3 $ALL_{DFA}$可判定
- 定义
- 判定器(第三版书-P124)
先解码$M$，然后从初始状态出发，有转移函数路径就染色；
这里需要对状态图作限定，为了接受所有语言，必须考察每一个状态的每一种转移函数路径。如果没有给出，则默认进入一个拒绝状态。
终止后检查所有被染色的状态，若均为接受状态则接受，否则就拒绝。
- 归约
在已知1.1.4的结论的情况下，可以有：
\[ALL_{DFA}\le_m EQ_{DFA}\ via\ f\]只需构造$f:\langle M\rangle \mapsto \langle M,M_A\rangle$
而$M_A$就是接受$\Sigma^{*}$的DFA。只需要在$M$的编码后续添加一个DFA的编码，这样的计算可以由图灵机完成。
1.1.4 $EQ_{DFA}$可判定
- 定义
- 给出判定器(第三版书-P124)
由于正则语言类对于交并补封闭，所以可以构造对称差：
\[L(C)=\big(L(M)\cap \overline{L(M')}\big)\bigcup\big(L(M')\cap \overline{L(M)} \big)\]随后用1.1.2的判定器即可。
- 归约
同2给出对称差，随后归约到$E_{PDA}$。
对称差只是一种构造算法，可以由图灵机完成，也就是多一归约的可计算函数。
1.2 上下文无关语言类
CFG,PDA互相等价，故在证明中不做区分。他们的之间的转化都可以交给图灵机完成。
1.2.1 $A_{CFG}$可判定
- 定义
- 给出判定器(第三版书-P124)
直接让图灵机解码$G$转化成PDA，输入$w$运行看结果就好了。
或者将$G$转化成CNF，由于其线性生成，故求得输入串长度$\mid w\mid=l$；随后穷举所有的$2l-1$步派生比较即可。
1.2.2 $E_{CFG}$可判定
- 定义
- 判定器(第三版书-P125)
- 对终结符做标记；
- 如果一个生成式右侧全部被标记，则标记左侧；如此遍历直到不再标记新符号
- 检查起始变元，若被标记则接受，否则拒绝。
1.2.3 $ALL_{CFG}$补图灵可识别
- 定义
- 判定器
能给出来就有鬼了。
- 归约(第三版书-P142)
直观的看，对于上下文无关文法G
- 如果它是满的，那么不断枚举串，每一个串都能接受，这样是不会停机的；
- 反之，则必然会停机。
所以$ALL_{CFG}$最多是一个补图灵可识别语言。为了证明方便，我们考虑PDA。
接下来，假设我们已知$A_{TM}$是图灵可识别的。我们试图证明：
\[A_{TM}\le_m \overline{ALL_{CFG}}\]H是接受计算历史。我们利用PDA来检查接受计算历史的合法性。
我们的目的是构造一个PDA D，它能接受除了$\langle M,w\rangle$的接受计算历史外的所有串。
现在的问题就来到了，我们如何构造一个可以判定接受计算历史的PDA。
这显然做不到，PDA只能判定“不是接受计算历史”这件事，不过对于我们的归约来说，也够了。
它分为三个不确定的部分。
- 第一个部分检查初始格局，这依赖于对应图灵机的编码和串是否正确。
- 第二个部分检查接受格局，这依赖于对应图灵机的编码。
- 第三个部分检查跳转是否错误。这里我们需要将格局正反依次放置。
PDA只能检查“不是接受计算历史”的能力局限，由第三部分限制。只要不是，PDA D就输出这个串。
综上，我们构造可计算函数：
\[f:\langle M,w\rangle\mapsto\langle D\rangle\]最后我们检查计算的正确性，如果$\langle M,w\rangle\in A_{TM}$，那么就存在接受计算历史H，则PDA D不能派生所有字符串。
1.2.4 $EQ_{CFG}$补图灵可识别
- 定义
- 归约
直观来看，用图灵机枚举串输入，如果不等必然可以检测出；否则就是不停机。
它最多是一个补图灵可识别语言，接下来给出证明。
只需要证明：
\[ALL_{CFG}\le_m EQ_{CFG}\]而这种归约只需要加入一个满的CFG即可。类似于1.1.3.
1.3 上下文有关语言类
CSG不会考察，只考虑LBA。
1.3.1 $A_{LBA}$可判定
- 定义
- 给出判定器(第三版书-P140)
接受自然停机，怕的是死循环不停机。但是LBA的格局是有限的，所以可以记录步数，如果超过了最多格局数，可以判定为拒绝了。
1.3.2 $E_{LBA}$补图灵可识别
- 定义
- 归约（书-P141）
直观来看，还是若接受某个串就拒绝，否则就穷举不停机。所以最多是补图灵可识别。
同样，我们考虑接受计算历史归约：
\[\overline{A_{TM}}\le_m E_{LBA}\]通过可计算函数$f:\langle M,w\rangle\mapsto\langle M’\rangle$
$M’$能接受$M$在$w$上的接受计算历史。则当其没有接受计算历史时，$M’$接受空语言。
构造方式类似于1.2.3
1.3.3 $ALL_{LBA}$补图灵可识别
- 定义
- 归约
直观的看
- 如果它是满的，那么不断枚举串，每一个串都能接受，这样是不会停机的；
- 反之，则必然会停机。
所以$ALL_{LBA}$最多是一个补图灵可识别语言。
接下来，假设我们已知$A_{TM}$是图灵可识别的。我们试图证明：
\[\overline{A_{TM}}\le_m ALL_{LBA}\]同样利用计算历史归约。构造出只拒绝接受计算历史串的LBA即可。
1.3.4 $EQ_{LBA}$补图灵可识别
- 定义
- 归约
直观来看，用图灵机枚举串输入，如果不等必然可以检测出；否则就是不停机。
它最多是一个补图灵可识别语言，接下来给出证明。
只需要证明：
\[ALL_{LBA}\le_m EQ_{LBA}\]而这种归约只需要加入一个满的LBA即可。类似于1.1.3.
1.4 图灵机类
CFG,PDA互相等价，故在证明中不做区分。他们的之间的转化都可以交给图灵机完成。
1.4.1 $A_{TM}$图灵可识别
- 定义
- 对角化(第三版书-P130)
对角化证明其不可判定。然后接受就必然能停机接受，否则可能不停机。这就是可识别的定义。
1.4.2 $E_{TM}$补图灵可识别
要和1.4.3一起读。否则祸害无穷。
- 定义
- 归约（书-P137）
还是直观来看，如果是接受空语言的图灵机，那么用楔形过程，还是不会停机；
如果不是，则必然有一个串会停机接受。所以最多是一个补图灵可识别语言。
以上的直观有一点问题。
给出归约和可计算函数：
\[A_{TM}\le_m \overline{E_{TM}} \\ f:\langle M,w\rangle\mapsto\langle M_w\rangle\]利用$M$和$w$构造$M_w$：对于输入$x$：
- 检查是否是$w$，如果不是，就拒绝；
- 如果是，则模拟$M$在$w$上的运行结果，如果接受就接受.
这个可计算函数的正确性并不显然，给出证明。
如果$\langle M,w\rangle\in A_{TM}$，那么$M_w$接受串$w$。反之则接受空语言。
1.4.3 $ALL_{TM}$？补图灵可识别？
- 定义
-
归约
- 如果它是满的，那么不断枚举串，每一个串都能接受，这样是不会停机的；
- 反之，则必然会停机。
所以$ALL_{TM}$最多是一个补图灵可识别语言。
接下来，假设我们已知$A_{TM}$是图灵可识别的。我们试图证明：
\[\overline{A_{TM}}\le_m ALL_{TM}\]同样可以用计算历史归约，和前面的证明类似。
但是$ALL_{TM}$既不是图灵可识别，也不是补图灵可识别。$ALL_{TM}$是$\Pi_2$语言类。
这说明直观的方式有问题，问题就出在接受性问题上。
前三类语言的接受性问题都是可判定的，而图灵机的接受性问题不是可判定的。
利用图灵归约的概念十分好理解，也就是利用$A_{TM}$作谕示的归约。
所以$ALL_{TM}$，是相对于可识别语言的补图灵可识别语言。而真正确定$E_{TM}$的位置，还需要证明：
\[{E_{TM}}\le_m \overline A_{TM}\\ f:\langle M\rangle\mapsto\langle M',w\rangle\]如果$M$接受空语言，那么任给一个$w$都不接受。
1.4.4 $EQ_{TM}$是$\Pi_2$语言类？
- 定义
- 归约
直观来看，用图灵机枚举串输入，如果不等必然可以检测出；否则就是不停机。
它最多是一个相对于图灵可识别语言的补图灵可识别语言，接下来给出证明。
只需要证明：
\[ALL_{TM}\le_m EQ_{TM}\]而这种归约只需要加入一个空的TM即可。类似于1.1.3.
1.5 杂项问题
1.5.1 $REGULAR_{TM}$不可判定
取归约和可计算函数：
\[A_{TM}\le_m REGULAR_{TM} \\ f:\langle M,w\rangle\mapsto\langle M'\rangle\]其中$M’$行为：对于输入$x$
- 检查$x$的形式，如果为$0^n1^n$则接受；
- 否则在$w$上运行$M$，若接受则接受。
通过以上构造，得到；
- 若$\langle M,w\rangle\in A_{TM}$，则接受$\Sigma^*$；否则接受$0^n1^n$。
1.5.2 PCP问题
未完待续。
2 语言类的封闭性实例
| 语言类 | 自动机 | 交 | 并 | 补 | 连接 | 星号 | 多一归约 | 图灵归约 |
|---|---|---|---|---|---|---|---|---|
| 正则语言 | DFA,NFA,REX | √ | √ | √ | √ | √ | x | x |
| 上下文无关语言 | PDA,CFG | x | √ | x | √ | √ | x | x |
| 上下文有关语言 | LBA,CSG | √ | √ | ? | √ | √ | ? | ? |
| 图灵可判定语言 | TM | √ | √ | √ | √ | √ | √ | √ |
| 图灵可识别语言 | TM | √ | √ | √ | √ | √ | √ | x |
2.1 正则语言
2.1.1 交
同时跑两个自动机，停止时两个都处于接受状态。
2.1.2 并
同时跑两个自动机，停止时有一台处于接受状态。
2.1.3 补
交换自动机的接受状态与拒绝状态。
2.1.4 连接
第一台自动机每进入接受状态一次就启动一台自动机2.
2.1.5 星号
对连接做归纳
2.1.6 多一归约
没用，是对可判定语言保持，可以在可判定语言内部变换。
2.1.6 图灵归约
没用，是对可判定语言保持，可以在可判定语言内部变换。
2.2 上下文无关语言
2.2.1 交
012，01个数等和02个数等，交起来不是CFL。
2.2.2 并
同时跑两个自动机，停止时有一台处于接受状态。
2.2.3 补
ww。不是，但是其补语言是。
用非确定性，读进i个弹i个，然后读进n-i个弹n-i个。
2.2.4 连接
第一台PDA每进入接受状态一次就启动一台PDA2.
2.2.5 星号
对连接做归纳
2.2.6 多一归约
没用，是对可判定语言保持，可以在可判定语言内部变换。
2.2.6 图灵归约
没用，是对可判定语言保持，可以在可判定语言内部变换。
2.3 LBA
2.3.1 交
考虑图灵机的计算能力，限制在有穷空间上。理应是封闭的。
2.3.2 并
同时跑两个LBA，停止时有一台处于接受状态。
2.3.3 补
是的吧。。。
2.3.4 连接
第一台LBA每进入接受状态一次就启动一台LBA2.
2.3.5 星号
对连接做归纳
2.3.6 多一归约
没用，是对可判定语言保持，可以在可判定语言内部变换。
2.3.6 图灵归约
没用，是对可判定语言保持，可以在可判定语言内部变换。
2.4 图灵可判定语言
2.4.1 交
考虑图灵机的计算能力，理应是封闭的。
2.4.2 并
同时跑两个TM，停止时有一台处于接受状态。
2.4.3 补
是的.
2.4.4 连接
第一台TM每进入接受状态一次就启动一台TM2.
2.4.5 星号
对连接做归纳
2.4.6 多一归约
是的。
2.4.6 图灵归约
是的。
2.5 图灵可识别语言
2.4.1 交
考虑图灵机的计算能力，理应是封闭的。
2.4.2 并
同时跑两个TM，有一台停机接受。
2.4.3 补
不是。
2.4.4 连接
非确定的分段，这里不能用之前的办法，因为可能循环了。
图灵机并非要读入所有的串后再接受或拒绝。
2.4.5 星号
对连接做归纳
2.4.6 多一归约
是的。
2.4.6 图灵归约
不是的，他对取补运算不敏感。