理论计算机科学基础 – 期中复习

写于2022年5月7日，主要包括一些常见语言类的可识别性与可判定性

\begin{aligned} A_{DFA}可判定：&直接模拟\\ A_{NFA}可判定：&转换为DFA\\ A_{REX}可判定：&转换为NFA\\ E_{DFA}可判定：&从起始状态开始标记状态\\ EQ_{DFA}可判定：&RL对差封闭，规约为E_{DFA}\\ \\ A_{CFG}可判定：&转换为乔姆斯基范式\\ E_{CFG}可判定：&从终结符开始标记变元\\ ALL_{CFG}不可判定：&构造PDA：派生所有串\Leftrightarrow M不接受\omega\\ &(拒绝M在\omega上的接受计算历史)\\ EQ_{CFG}不可判定：&ALL_{CFG}可规约到它\\ \\ A_{TM}不可判定：&对角线法\\ HALT_{TM}不可判定：&A_{TM}可规约到它\\ E_{TM}不可识别：&A_{TM}\le_m \overline{E_{TM}}\\ \overline{E_{TM}}可识别：&按字符串顺序和运行步长枚举\\ &(因此，A_{TM}\not\le_m E_{TM})\\ EQ_{TM}不可识别：&A_{TM}\le_m \overline{EQ_{TM}}\\ \overline{EQ_{TM}}不可识别：&A_{TM}\le_m EQ_{TM}\\ ALL_{TM}不可识别：&构造TM，拒绝M在\omega上的计算历史\\ &(事实上，A_{TM}\le_m \overline{ALL_{TM}})\\ \overline{ALL_{TM}}不可识别：&A_{TM}\le_m ALL_{TM} \\ \end{aligned}