习题集学习路线与代表题¶

参考解答

解答。 这里 \(2^A=\mathcal P(A)\) 表示 \(A\) 的全部子集。两项都是“集合的集合”，不是数值幂。

(d) 大幂集有 \(2^3=8\) 个元素；小幂集正好是其中不含 \(8\) 的四个子集。作差后保留所有含 \(8\) 的子集：

(e) 空集唯一的子集是空集自身，因此幂集只有一个元素。满足原题格式的答案是：

判分要点： (d) 四个子集齐全且没有多项；(e) 保留两层花括号，并能解释为什么基数为 \(1\)。

参考解答

解答。 任取元素 \(x\)，分别证明两向包含。

从左到右：若 \(x\in A\)，则它同时属于 \(A\cup B\) 和 \(A\cup C\)；若 \(x\notin A\) 而属于左边，就必须同时属于 \(B\) 和 \(C\)，仍属于右边。因此左边包含于右边。

从右到左：若 \(x\in A\)，直接属于左边；若 \(x\notin A\)，右边的两个并集条件分别迫使 \(x\in B\) 和 \(x\in C\)，所以 \(x\in B\cap C\)，仍属于左边。两向合并，等号成立。

全程只使用任意元素的成员条件，对 \(A,B,C\) 为空集或无限集同样成立。

判分要点： 明确任意 \(x\)；两方向都覆盖 \(x\in A\) 和 \(x\notin A\) 的情况；由两向包含得出集合相等。

参考解答

解答。 是正则语言。\(m\) 和 \(n\) 彼此独立：\(a\) 的数量为偶数；\(b\) 先固定有 \(2020\) 个，再按每次三个增加。一个正则表达式是

这里 \(b^{2020}\) 是固定 \(2020\) 次连接的缩写。

表达式生成的串恰有 \(2m\) 个 \(a\) 和 \(2020+3n\) 个 \(b\)，故属于 \(L\)；反过来，任一满足题意的串都能选择前面重复 \(m\) 次、后面重复 \(n\) 次，故由表达式生成。

边界 \(m=n=0\) 给出 \(b^{2020}\)，不是空串。若来源课堂采用 \(\mathbb N=\{1,2,\ldots\}\)，表达式调整为 \(aa(aa)^*b^{2023}(bbb)^*\)，正则结论不变。

判分要点： 结论为正则；表达式保留 \(2020\) 与独立周期；解释生成与覆盖两个方向，说明自然数约定。

参考解答

解答。 是正则语言。继续按上一题的非负整数约定，\(m\) 只有 \(0,1,\ldots,2021\) 共 \(2022\) 种取值，而且一旦选定 \(m\)，\(n=2021-m\) 就确定。所以 \(L\) 有限。

将每个合法串作为一个固定表达式，再作有限并即可：

这行是 \(2022\) 个表达式的有限并缩写，不是含自由计数变量的单个正则操作。每项总长为 \(2021\)，故生成串都合法；每个合法串的 \(m\) 都在枚举范围内，故没有遗漏。

边界包含 \(b^{2021}\) 和 \(a^{2021}\)，不包含空串。

若采用正整数约定，枚举范围改为 \(m=1,\ldots,2020\)，共 \(2020\) 个串，仍是有限正则语言。

判分要点： 抓住总长是固定常数；给出有限枚举或等价构造；不把固定常数 \(2021\) 当成随输入增大的变量。

参考解答

解答。 是 CFL。取开始符号 \(S\)，构造文法：

最后一项 \(b^{2021}\) 表示右侧写下固定 \(2021\) 个终结符 \(b\)，是记号缩写。

生成方向： \(S\to aSc\) 用 \(k\) 次，产生 \(k\) 对 \(a,c\)；\(A\to aA\) 用 \(r\) 次，补 \(r\) 个 \(a\)；\(B\to bB\) 用 \(t\) 次，在基底上补 \(t\) 个 \(b\)。最终串为

满足 \(m=k+r\ge k\) 与 \(n=2021+t\ge2021\)。

覆盖方向： 任给合法 \(a^m b^n c^k\)，选择 \(k\) 次配对递归、\(m-k\) 次补 \(a\)、\(n-2021\) 次补 \(b\)。这三个次数均非负，所以都有合法推导。

例如 \(a^2b^{2022}c\)：

边界 \(k=m=0,n=2021\) 由 \(S\Rightarrow A\Rightarrow B\Rightarrow b^{2021}\) 生成。若 \(\mathbb N\) 从 \(1\) 起，将第一行的结束选项 \(S\to A\) 改为 \(S\to aAc\)，其余不变，即强制至少一对 \(a,c\)。

判分要点： 文法保持串的区段顺序；配对与多余 \(a\) 分开；两向正确性和固定下界都说明。

参考解答

解答。 不是 CFL。假设它是 CFL，设泵长度为 \(p\ge1\)，取

考虑任意符合 CFL 泵引理的分解 \(s=uvxyz\)，其中 \(|vxy|\le p\)、\(|vy|>0\)。中间 \(b\) 段长度为 \(3p\)，所以长度不超过 \(p\) 的窗口 \(vxy\) 不可能同时接触 \(a\) 段和 \(c\) 段。

令 \(\Delta_a,\Delta_b,\Delta_c\) 分别为 \(vy\) 中三种符号的数量。所有合法位置可按下表覆盖：

故至少一个 \(\Delta\) 为 \(0\)；又由 \(|vy|>0\)，至少另一个 \(\Delta\) 为正。选择泵次数 \(i=0\)，删除 \(v,y\)。删除不改变剩余符号的区段顺序。如果 \(uxz\) 仍在 \(L\)，应存在 \(n'\) 满足

任一未变区段都迫使 \(n'=p\)；代回三式，三个 \(\Delta\) 必须全为 \(0\)，与至少一个为正矛盾。因此每个合法分解都在 \(i=0\) 时离开 \(L\)，违反泵引理。非负或正整数约定都不影响本反证，因为所选 \(n=p\ge1\)。

判分要点： 先假设 CFL 并取泵长度；证明窗口最多覆盖相邻两段；覆盖任意分解；用未变区段锁定 \(n'\)，与非空删除矛盾。

参考解答

解答。 下表位置从左端标记格 \(0\) 起编号。每行表示执行该步之后的完整配置；显示右侧一个空白，其余格仍为空白。

检查机制：每个非空白格执行“交换 \(a/b\)、右移”两步；六个输入格共 \(12\) 步，再在首个空白格写空白并进入 \(h\)，共 \(13\) 步。停机时头仍在位置 \(7\)。

判分要点： 初始头位置与全部转移正确；写入和右移分步；结果 \(bbaaab\)、\(13\) 步及停机头位置一致。

参考解答

解答。 定义域为非负整数，包含 \(0!=1\)。不能只写阶乘递推式，还要证明递推中的积木属于原始递归函数。

先由零函数 \(Z\)、后继函数 \(Succ\) 和投影函数构造加法、乘法：

加法的初值是投影，更新是后继与投影的复合，故由原始递归得到；乘法的初值是零，更新由已得到的加法复合而成，故也原始递归。常数 \(1=Succ(0)\) 同样可由复合得到。

现在定义

更新函数 \(g(n,z)=Mul(Succ(n),z)\) 是已知原始递归函数的复合，故原始递归模式给出 \(F\)。用归纳检查：初值 \(F(0)=0!=1\)；若 \(F(n)=n!\)，则 \(F(n+1)=(n+1)n!=(n+1)!\)。因此 \(F=factorial\)。

计算 \(F(n)\) 只进行有限的 \(n\) 轮更新，每轮的加法、乘法也全定义，因此所有非负整数输入均有结果。例：\(F(0)=1,F(1)=1,F(2)=2,F(3)=6\)。

判分要点： 初值 \(1\)；更新 \((n+1)F(n)\)；常数、加法、乘法的原始递归依据；归纳对应阶乘和全定义性。

参考解答

解答。 \(L_2\) 非递归可枚举，即不可识别，因而也不可判定。

先核对 Rice 条件：性质“接受语言至多三个元素”只依赖 \(L(M)\)，不依赖代码写法；空语言满足它，而接受所有二元串的机器不满足它。

所以这是非平凡的语言性质，Rice 定理说明不可判定。Rice 并不能直接推出不可识别，下面另证。

使用已知不可识别的 \(\overline{A_{TM}}\)，其中 \(A_{TM}=\{\langle M,w\rangle:M\text{ 接受 }w\}\)。

从有效编码 \(\langle M,w\rangle\) 构造机器 \(N\)，对任意输入 \(z\)：模拟 \(M\) 在 \(w\) 上运行；如果模拟接受，就接受 \(z\)；如果模拟拒绝，可以拒绝 \(z\)；如果模拟一直运行，就一直等待。

转换程序只是将 \(M,w\) 写入上述有限程序模板，然后输出 \(\langle N\rangle\)，不等待 \(M\) 的模拟结果，因此总能完成。

若源输入不是有效机器／字符串对编码，则输出一个固定的空语言机器；这也使归约在所有编码上全定义。

两向检查：\(M\) 不接受 \(w\) 时，\(N\) 不接受任何 \(z\)，所以 \(L(N)=\varnothing\)，\(\langle N\rangle\in L_2\)；\(M\) 接受 \(w\) 时，\(N\) 接受所有二元串，所以 \(|L(N)|>3\)，\(\langle N\rangle\notin L_2\)。无效源编码也属于 \(\overline{A_{TM}}\)，并被映射到 \(L_2\)。于是

若 \(L_2\) 有识别器，先算 \(f(x)\) 再运行它即可识别 \(\overline{A_{TM}}\)，矛盾。顺便看补集：对有效 \(M\) 的全部输入公平交错模拟，一旦发现四个不同串被接受就接受；无效编码直接接受。

这能识别 \(\overline{L_2}\)，所以 \(L_2\) 还是 coRE，但本题要求的三分类答案为非 RE。

判分要点： Rice 条件完整；另给不可识别归约；模板转换总停机；真假两向都写；明确模拟等待的是“接受”，不是笼统“停机”。

参考解答

解答。 \(L_3\) 递归可枚举但非递归，即可识别、不可判定。

构造识别器：先验证机器编码，无效则拒绝。按长度、再按字典序枚举全部输入串 \(z_0,z_1,\ldots\)。第 \(t\) 轮，对前 \(t+1\) 个输入各模拟一步；保存它们各自的配置和已接受输入的集合。

一旦其中有三个不同输入被接受，就接受 \(\langle M\rangle\)。

这叫公平交错模拟：每个输入最终得到无限多步模拟，不会被某个不停止的输入挡住。

若 \(|L(M)|\ge3\)，任选三个被接受串，它们的编号和接受所需步数都有限，因此某个有限轮次必定已发现三者；若 \(|L(M)|<3\)，永远不会误报，识别器可一直运行。这证明可识别性。

再用 Rice 定理证明不可判定：性质只依赖接受语言，且非平凡——空语言不满足，接受所有二元串的语言满足。因此不存在判定器，三分类落在“递归可枚举但非递归”。

判分要点： 明确三条不同串的有限见证；公平交错而非逐个等停机；成员最终接受、非成员不误接受；另用 Rice 给出不可判定。