用户: Housefz房子/理论计算机科学基础 (信科) 讲义及作业

本页是 2021 秋季信息科学技术学院刘田老师所开理论计算机科学基础课程的知识梳理和作业解答

0引言

简单说下为什么写这玩意. 主要是这 TCS 的作业是真的难, 一道题做一天, 搜答案也搜不到, 所以我就在这里写一份解答, 方便需要学习 TCS 课的同学们.

由于我学习也比较忙, 所以这里会慢慢更新 (

1第一章习题

习题 1.1 (中译本 1.35). 设 $A/B=\{w\mid \exists x\in B,wx\in A\}$. 证明若 $A$ 是正则语言, $B$ 是任意语言, 则 $A/B$ 是正则语言.

证明. 设 $M=(Q,\Sigma ,\delta ,q_0,F)$ 是识别 $A$ 的 DFA, 令$$F^{\prime }=\{q\in Q\mid \exists y\in B,\delta (q,y)\in F\}$$则 $M^{\prime }=(Q,\Sigma ,\delta ,q_0,F^{\prime })$ 为识别 $A/B$ 的 DFA.

$\square$

2第二章习题

习题 2.1 (中译本 2.33). 对于字母表 $\Sigma =a,b$, 给出产生所有 $a$ 的个数是 $b$ 的两倍的字符串的语言的 CFG, 并证明其正确性.

证明. 构造 CFG 如下$$\begin{array}{rl}& S\to ABA\mid BAA\mid AAB\mid ϵ\\ & A\to a\mid SA\mid AS\\ & B\to b\mid SB\mid BS\end{array}$$容易发现, 这个 CFG 生成的字符串都满足 $a$ 的个数是 $b$ 的两倍. 下证其生成所有这样的字符串. 为此, 只需证明其生成所有 $A$ 和 $B$ 构成的 $A$ 的个数是 $B$ 的两倍的串. 设这样的串的长度是 $3n$, 对 $n$ 归纳易证.

$\square$

习题 2.2 (中译本 2.35). 设 $D=\{xy\mid x,y\in \{0,1{\}}^{\ast },|x|=|y|,x\ne y\}$, 证明 $D$ 是上下文无关语言.

证明. 构造 CFG 如下$$\begin{array}{rl}& S\to AB\mid BA\\ & A\to TAT\mid 0\\ & B\to TBT\mid 1\\ & T\to 0\mid 1\end{array}$$证明留作习题.

$\square$

3第三章习题

习题 3.1 (中译本 3.13). 证明: 一个语言是可判定的, 当且仅当有枚举器以标准字符串顺序枚举这个语言.

证明. $\Rightarrow$: 设图灵机 $M$ 判定语言 $A$, 将 ${\Sigma }^{\ast }$ 按标准序排列: $s_1,s_2\cdots$, 枚举器$$\begin{array}{rl}E=‘& \text{忽略输入},\\ & \text{对}i=1,2,\cdots \text{重复以下步骤,}\\ & M\text{以}{s}_i\text{为输入,有限步后停下},\\ & \text{若接受,则打印}{s}_i,\text{若拒绝则不打印. ’}\end{array}$$则 $E$ 按标准序打印 $A$.

$\Leftarrow$: 设枚举器 $E$ 按标准序枚举语言 $A$.

$\square$

4第四章习题

习题 4.1 (中译本 4.23). 证明可判定的语言类在同态下不封闭.

证明. 将下题中的 $D$ 同态到 $C$ 即可.

$\square$

习题 4.2 (中译本 4.24). 设 $C$ 是一个语言. 证明 $C$ 是图灵可识别的, 当且仅当存在一个可判定语言 $D$, 使 $C=\{x\mid \exists y(⟨x,y⟩\in D)\}$.

证明. 喵

$\square$

5第五章习题

6期中考试

试题

一、名词解释

1. 正则运算 2. 乔姆斯基范式 3. 图灵可枚举 4. PCP 5. 歧义文法

二、判断题

1. 无穷上下文无关语言是否一定有无穷正则语言子集?

2. 无穷图灵可判定语言是否一定有无穷上下文无关语言子集?

3. 无穷图灵可识别语言是否一定有无穷图灵可判定语言子集?

4. 无穷图灵不可识别语言是否一定有无穷图灵可识别语言子集?

5. $A$ 是正则语言, 则 $\mathrm{subseq}(A)$ 是正则语言.

6. $A$ 是上下文无关语言, 则 $\mathrm{subseq}(A)$ 是上下文无关语言.

7. $A$ 是图灵可判定语言, 则 $\mathrm{subseq}(A)$ 是图灵可判定语言.

8. $A$ 是图灵可识别语言, 则 $\mathrm{subseq}(A)$ 是图灵可识别语言.

9. $A$ 是补图灵可识别语言, 则 $\mathrm{subseq}(A)$ 是补图灵可识别语言.

10. $A$ 是任意语言, 则 $\mathrm{subseq}(A)$ 是正则语言.

三、语言分类与证明

1. 将以下 10 个语言分入它所在的最小的语言类. $$\begin{array}{r}A=\{1^{k}y\mid y\in \{0,1{\}}^{\ast },k\ge 1,y\text{至少有}k\text{个}1\}\end{array}$$

解答

一、名词解释

1. 正则运算 2. 乔姆斯基范式 3. 图灵可枚举 4. PCP 5. 歧义文法

解. 请自行查阅课本.

$\square$

二、判断题

1. 无穷上下文无关语言是否一定有无穷正则语言子集?

解. 错. 反例 $0^n{1}^n$. 用泵引理即可证明.

$\square$

2. 无穷图灵可判定语言是否一定有无穷上下文无关语言子集?

解. 错. 反例 $0^n{1}^n{2}^n$. 用泵引理即可证明.

$\square$

3. 无穷图灵可识别语言是否一定有无穷图灵可判定语言子集?

解. 对. 此为中译本课后习题 3.12, 证明略.

$\square$

4. 无穷图灵不可识别语言是否一定有无穷图灵可识别语言子集?

解. 错. 反例 $MI{N}_{TM}$, 见中译本课后习题 6.2, 证明略.

$\square$

5. $A$ 是正则语言, 则 $\mathrm{subseq}(A)$ 是正则语言.

6. $A$ 是上下文无关语言, 则 $\mathrm{subseq}(A)$ 是上下文无关语言.

7. $A$ 是图灵可判定语言, 则 $\mathrm{subseq}(A)$ 是图灵可判定语言.

8. $A$ 是图灵可识别语言, 则 $\mathrm{subseq}(A)$ 是图灵可识别语言.

9. $A$ 是补图灵可识别语言, 则 $\mathrm{subseq}(A)$ 是补图灵可识别语言.

10. $A$ 是任意语言, 则 $\mathrm{subseq}(A)$ 是正则语言.

解. 10 是对的, 从而 5 到 9 都是对的. 参见 Higman 定理.

$\square$

7第七章习题

习题 7.1 (中译本 7.20). 单带确定性图灵机在 $o(n\log n)$ 时间内只能识别正则语言.

证明. 下文中的图灵机均指单带确定性图灵机.

定义 7.2 (穿越序列). 将带子写成$$|x_0|x_1|\cdots |x_n|\cdots$$其中 $|$ 表示两个格子之间的边界. 记 $x_k$ 左边的那个边界为第 k 个边界.

设 $S_k(i)$ 是图灵机第 $i$ 次穿过第 $k$ 个边界后的瞬间的状态, 则序列 $C_k=S_k(1),\cdots ,S_k(i),\cdots$ 称作图灵机在第 $k$ 个边界上的穿越序列.

定义 7.3 (穿越数). 穿越数是穿越序列的长度, 记为 $|C_k|$.

注 7.4. 图灵机在一个输入上运行的总时间是它所有穿越序列的长度之和.

引理 7.5 (Hennie). 如果一个图灵机在任意输入和边界上的穿越数是有界的, 则它识别正则语言.

引理的证明. 设图灵机 $M$ 在任意输入和边界上的穿越数不超过 $K$, 则长度不超过 $K$ 的穿越序列是只有有限种. 从而所有穿越序列构成的集合的幂集有限. 设 $L=L(M)$ 由 Myhill–Nerode 定理, 只需要证明 $L$ 的指数是有限的.

设 $S(x)=\{C\mid xz\in L,C$ 是 $x|z$ 处的穿越序列 $\}$, 则 $S(x)$ 是有限集. 下证若 $S(x)=S(y)$, 则 $x$ 和 $y$ 等价.

设 $S(x)=S(y)$. $\forall xz\in L,C_x$ 为 $x|z$ 处的穿越序列, $\exists w$ 使 $yw\in L$ 且 $C_y=C_x$ 为 $y|w$ 处的穿越序列. 容易证明 $yz\in L$. 故 $x$ 和 $y$ 等价.

这说明 $L$ 被分成有限个等价类, 即 $L$ 指数有限, 故 $L$ 是正则语言, 证毕.

$\square$

定理 7.6 (Kobayashi). 如果一个图灵机运行时间为 $o(n\log n)$, 则它在任何输入和边界上的穿越数是 $O(1)$ 的.

证明. 设 $f(n)=o(n\log n)$, $M$ 是一个有 $s⩾2$ 个状态的图灵机. $M$ 在 $f(n)$ 时间内接受语言 $L$. 定义 $g(n)$ 为: $$g(n)=\{\begin{array}{ll}\frac{n\log n}{f(n)},& n⩾2,\\ 1,& n=0,1.\end{array}$$我们有 ${\lim }_{n\to \infty }g(n)=\infty$, 从而可以选取 $c$ 使$$3\frac{n^{(\log s)/g(n{)}^{1/2}+1}-1}{s-1}+1⩽n-2-\frac{n}{g(n{)}^{1/2}}+c\frac{g(n{)}^{1/2}}{\log n}$$对所有的 $n⩾2$ 成立.

下面证明, 对 $M$ 在任何满足 $x\in L$ 且 $|x|⩾2$ 的输入 $x$ 和任何边界上的穿越序列的长度不超过 $c$.

假设存在 $x\in L$ 且 $|x|⩾2$ 使得 $M$ 在输入 $x$ 和某个边界上的穿越序列的长度大于 $c$. 取 $x_0$ 是这样的 $x$ 中最短的, $x_0$ 的长度是 $n_0$, $P_1$ 是使 $|C_{P_1}|>c$ 的一个位置.

在输入 $x_0$ 上运行 $M$. 记 $h$ 是前 $n_0+1$ 个位置中使穿越序列的长度小于 $(\log n_0)/g(n_0{)}^{1/2}$ 的位置的个数, 则$$\frac{n_0\log n_0}{g(n_0)}=f(n_0)>c+(n_0-2-h)\frac{\log n_0}{g(n_0{)}^{1/2}}$$从而有: $$\begin{array}{rl}h& >n_0-2-\frac{n_0}{g(n_0{)}^{1/2}}+c\frac{g(n_0{)}^{1/2}}{\log n_0}\\ & ⩾3\frac{n_0^{(\log s)/g(n_0{)}^{1/2}+1}-1}{s-1}+1\\ & =3\frac{s^{(\log n_0)/g(n_0{)}^{1/2}+1}-1}{s-1}+1.\end{array}$$并且, 至多有 $\frac{s^{(\log n_0)/g(n_0{)}^{1/2}+1}-1}{s-1}$ 种长度小于 $(\log n_0)/g(n_0{)}^{1/2}$ 的穿越序列. 从而由抽屉原理, $x_0$ 中至少有四个位置的穿越序列完全一样. 它们中至少有两个和 $P_1$ 不同且在 $P_1$ 的同一侧, 设为 $P_2$ 和 $P_3$. 设 $x_0^{\prime }$ 由 $x_0$ 删除 $P_2$ 和 $P_3$ 之间的字串得到. 则 $M$ 接受 $x_0$, 且在某个边界上的穿越序列比 $c$ 长, 且 $2⩽|x_0^{\prime }|<|x_0|$. 这与 $x$ 的最小性矛盾, 从而不可能存在这样的 $x$.

$\square$

结合引理 7.5 和定理, 我们就完成了习题的证明.

$\square$