1问题
2.18 考虑以下上下文无关文法 $G$：
描述 $L(G)$ 并证明 $G$ 是二义性的。给出一个无二义文法 $H$ 使得 $L(H)=L(G)$，并草拟一个证明 $H$ 是无二义性的论证。
*2.19 我们将语言 $A$ 的旋转闭包定义为 $R C(A)=\{y x \mid x y \in A\}$。证明 CFLs 类在旋转闭包下是封闭的。
*2.20 我们将语言 $A$ 的 CUT 定义为 $\operatorname{CUT}(A)=\{y x z \mid x y z \in A\}$。证明 CFLs 类在 CUT 下不是封闭的。
2.21 证明每个 DCFG 都是一个无二义 CFG。
${ }^{A \star}$ 2.22 证明每个 DCFG 生成一个无前缀语言。
*2.23 证明 DCFLs 类在以下运算下不是封闭的：
a. 并
b. 交
c. 连接
d. 星号
e. 逆
2.24 设 $G$ 为以下文法：
a. 证明 $L(G)=\{w-\mid w$ 包含等量的 a 和 b $\}$。使用对 $w$ 的长度进行归纳证明。
b. 使用 $D K$-测试证明 $G$ 是一个 DCFG。
c. 描述一个识别 $L(G)$ 的 DPDA。
2.25 设 $G_{1}$ 为我们在示例 2.45 中介绍的以下文法。使用 $D K$-测试证明 $G_{1}$ 不是一个 DCFG。
*2.26 设 $A=L\left(G_{1}\right)$，其中 $G_{1}$ 在问题 2.25 中定义。证明 $A$ 不是一个 DCFL。（提示：假设 $A$ 是一个 DCFL，并考虑其 DPDA $P$。修改 $P$，使其输入字母表为 $\{\mathrm{a}, \mathrm{b}, \mathrm{c}\}$。当它首次进入接受状态时，从那时起它假装输入中的 c 是 b。修改后的 $P$ 会接受什么语言？）
*2.27 设 $B=\left\{\mathrm{a}^{i} \mathrm{~b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0\right.$ 且 $i=j$ 或 $\left.i=k\right\}$。证明 $B$ 不是一个 DCFL。
${ }^{\star}$ 2.28 设 $C=\left\{w w^{\mathcal{R}} \mid w \in\{0,1\}^{*}\right\}$。证明 $C$ 不是一个 DCFL。（提示：假设当某个 DPDA $P$ 在状态 $q$ 启动，堆栈顶部为符号 $x$ 时，$P$ 无论从那时起读取什么输入字符串，都不会将其堆栈弹出到 $x$ 以下。在这种情况下，$P$ 堆栈在该点的内容不会影响其后续行为，因此 $P$ 的后续行为仅取决于 $q$ 和 $x$。）
*2.29 如果我们不允许 CFG 中的 $\varepsilon$-规则，我们可以简化 $D K$-测试。在简化测试中，我们只需要检查 $D K$ 的每个接受状态都只有一个规则。证明一个没有 $\boldsymbol{\varepsilon}$-规则的 CFG 通过简化 $D K$-测试当且仅当它是一个 DCFG。
${ }^{\mathrm{A}}$ 2.30 a. 设 $C$ 是一个上下文无关语言，$R$ 是一个正则语言。证明语言 $C \cap R$ 是上下文无关的。
b. 设 $A=\left\{w \mid w \in\{\mathbf{a}, \mathbf{b}, \mathbf{c}\}^{*}\right.$ 且 $w$ 包含等量的 a、b 和 c $\}$。使用 (a) 部分来证明 $A$ 不是一个 CFL。
*2.31 设 CFG $G$ 为以下文法。
用英语简要描述 $L(G)$。使用该描述给出 $\overline{L(G)}$ 的 CFG，即 $L(G)$ 的补集。
2.32 设 $A / B=\{w \mid w x \in A$ 对于某个 $x \in B\}$。证明如果 $A$ 是上下文无关的，$B$ 是正则的，那么 $A / B$ 是上下文无关的。
*2.33 设 $\Sigma=\{\mathrm{a}, \mathrm{b}\}$。给出一个生成包含两倍 a 数量的 b 数量的字符串语言的 CFG。证明你的文法是正确的。
*2.34 设 $C=\left\{x \# y \mid x, y \in\{0,1\}^{*}\right.$ 且 $\left.x \neq y\right\}$。证明 $C$ 是一个上下文无关语言。
*2.35 设 $D=\left\{x y \mid x, y \in\{0,1\}^{*}\right.$ 且 $|x|=|y|$ 但 $x \neq y\}$。证明 $D$ 是一个上下文无关语言。
*2.36 设 $E=\left\{\mathrm{a}^{i} \mathrm{~b}^{j} \mid i \neq j\right.$ 且 $\left.2 i \neq j\right\}$。证明 $E$ 是一个上下文无关语言。
2.37 对于任何语言 $A$，设 $\operatorname{SUFFIX}(A)=\{v \mid u v \in A$ 对于某个字符串 $u\}$。证明上下文无关语言类在 SUFFIX 运算下是封闭的。
2.38 证明如果 $G$ 是乔姆斯基范式下的 CFG，那么对于任何长度 $n \geq 1$ 的字符串 $w \in L(G)$，导出 $w$ 恰好需要 $2 n-1$ 步。
*2.39 设 $G=(V, \Sigma, R,\langle\mathrm{STMT}\rangle)$ 为以下文法。
$G$ 是一个看起来自然的编程语言片段文法，但 $G$ 是二义性的。
a. 证明 $G$ 是二义性的。
b. 给出一个针对相同语言的新的无二义文法。
*2.40 为以下语言给出无二义 CFG。
a. $\{w \mid w$ 的每个前缀中 a 的数量至少是 b 的数量 $\}$
b. $\{w \mid w$ 中 a 的数量和 b 的数量相等 $\}$
c. $\{w \mid w$ 中 a 的数量至少是 b 的数量 $\}$
*2.41 证明练习 2.9 中的语言 $A$ 是固有二义性的。
2.42 使用泵引理证明以下语言不是上下文无关的。
a. $\quad\left\{0^{n} 1^{n} 0^{n} 1^{n} \mid n \geq 0\right\}$
Ad. $\quad\left\{0^{n} \# 0^{2 n} \# 0^{3 n} \mid n \geq 0\right\}$
${ }^{\text {A }}$ c. $\quad\left\{w \# t \mid w\right.$ 是 $t$ 的子串，其中 $\left.w, t \in\{\mathbf{a}, \mathbf{b}\}^{*}\right\}$
d. $\quad\left\{t_{1} \# t_{2} \# \cdots \# t_{k} \mid k \geq 2\right.$，每个 $t_{i} \in\{\mathrm{a}, \mathrm{b}\}^{*}$，且对于某些 $i \neq j$ 有 $t_{i}=t_{j}\}$
2.43 设 $B$ 是所有由 $\{0,1\}$ 组成的回文串，其中 0 的数量和 1 的数量相等。证明 $B$ 不是上下文无关的。
2.44 设 $\Sigma=\{1,2,3,4\}$ 且 $C=\left\{w \in \Sigma^{*} \mid\right.$ 在 $w$ 中，1 的数量等于 2 的数量，且 3 的数量等于 4 的数量 $\}$。证明 $C$ 不是上下文无关的。
*2.45 证明 $F=\left\{\mathrm{a}^{i} \mathrm{~b}^{j} \mid i=k j$ 对于某个正整数 $k\}$ 不是上下文无关的。
2.46 考虑语言 $B=L(G)$，其中 $G$ 是练习 2.13 中给出的文法。上下文无关语言的泵引理，定理 2.34，说明了 $B$ 存在一个泵长度 $p$。在泵引理中，起作用的 $p$ 的最小值是多少？证明你的答案。
2.47 设 $G$ 是一个包含 $b$ 个变量的乔姆斯基范式下的 CFG。证明如果 $G$ 生成某个具有至少 $2^{b}$ 步推导的字符串，$L(G)$ 是无限的。
2.48 给出一个不是上下文无关语言但其行为在泵引理中与 CFL 相似的语言示例。证明你的示例是有效的。（参见问题 1.49 中正则语言的类似示例。）
*2.49 证明以下更强的泵引理形式，其中当字符串 $s$ 被分解时，$v$ 和 $y$ 两个部分都必须是非空的。
如果 $A$ 是一个上下文无关语言，那么存在一个数字 $k$，其中如果 $s$ 是 $A$ 中长度至少为 $k$ 的任何字符串，那么 $s$ 可以被分成五部分，$s=u v x y z$，满足以下条件：
a. 对于每个 $i \geq 0, u v^{i} x y^{i} z \in A$，
b. $\quad v \neq \varepsilon$ 且 $y \neq \varepsilon$，
c. $|v x y| \leq k$。
${ }^{\text {A }}$ 2.50 参考问题 1.31 获取完美洗牌操作的定义。证明上下文无关语言类在完美洗牌操作下不是封闭的。
2.51 参考问题 1.32 获取洗牌操作的定义。证明上下文无关语言类在洗牌操作下不是封闭的。
*2.52 称一个语言是前缀封闭的，如果该语言中每个字符串的所有前缀也都在该语言中。设 $C$ 是一个无限、前缀封闭的上下文无关语言。证明 $C$ 包含一个无限正则子集。
*2.53 阅读问题 1.45 中 $N O P R E F I X(A)$ 和 $N O E X T E N D(A)$ 的定义。
a. 证明 CFLs 类在 NOPREFIX 下不是封闭的。
b. 证明 CFLs 类在 NOEXTEND 下不是封闭的。
*2.54 设 $Y=\left\{w \mid w=t_{1} \# t_{2} \# \cdots \# t_{k}\right.$ 对于 $k \geq 0$，每个 $t_{i} \in 1^{*}$，且当 $i \neq j$ 时 $t_{i} \neq t_{j}\}$。这里 $\Sigma=\{1, \#\}$。证明 $Y$ 不是上下文无关的。
2.55 对于字符串 $w$ 和 $t$，如果 $w$ 的符号是 $t$ 的符号的排列，则写 $w \stackrel{\circ}{=} t$。换句话说，如果 $t$ 和 $w$ 具有相同数量的相同符号，但可能顺序不同，则 $w \stackrel{\circ}{=} t$。
对于任何字符串 $w$，定义 $\operatorname{SCRAMBLE}(w)=\{t \mid t \stackrel{\circ}{=} w\}$。对于任何语言 $A$，设 $\operatorname{SCRAMBLE}(A)=\{t \mid t \in \operatorname{SCRAMBLE}(w)$ 对于某个 $w \in A\}$。
a. 证明如果 $\Sigma=\{0,1\}$，那么正则语言的 SCRAMBLE 是上下文无关的。
b. 如果 $\Sigma$ 包含三个或更多符号，(a) 部分会发生什么？证明你的答案。
2.56 如果 $A$ 和 $B$ 是语言，定义 $A \diamond B=\{x y \mid x \in A$ 且 $y \in B$ 且 $|x|=|y|\}$。证明如果 $A$ 和 $B$ 是正则语言，那么 $A \diamond B$ 是一个 CFL。
${ }^{\star}$ 2.57 设 $A=\left\{w t w^{\mathcal{R}} \mid w, t \in\{0,1\}^{*}\right.$ 且 $\left.|w|=|t|\right\}$。证明 $A$ 不是一个 CFL。
2.58 设 $\Sigma=\{0,1\}$，设 $B$ 是包含至少一个 1 的字符串集合，且 1 位于字符串的后半部分。换句话说，$B=\left\{u v \mid u \in \Sigma^{*}, v \in \Sigma^{*} 1 \Sigma^{*}\right.$ 且 $\left.|u| \geq|v|\right\}$。
a. 给出一个识别 $B$ 的 PDA。
b. 给出一个生成 $B$ 的 CFG。
2.59 设 $\Sigma=\{0,1\}$。设 $C_{1}$ 是所有在其中间三分之一处包含一个 1 的字符串语言。设 $C_{2}$ 是所有在其中间三分之一处包含两个 1 的字符串语言。因此 $C_{1}=\left\{x y z \mid x, z \in \Sigma^{*}\right.$ 且 $y \in \Sigma^{*} 1 \Sigma^{*}$，其中 $|x|=|z| \geq|y|\}$ 且 $C_{2}=\left\{x y z \mid x, z \in \Sigma^{*}\right;且 $y \in \Sigma^{} 1 \Sigma^{} 1 \Sigma^{*}$，其中 $|x|=|z| \geq|y|\}$。
a. 证明 $C_{1}$ 是一个 CFL。
b. 证明 $C_{2}$ 不是一个 CFL。
精选解答
2.3 (a) $R, X, S, T$；(b) a, b；(c) $R$；(d) $L(G)$ 中的三个字符串是 ab, ba, 和 aab；(e) 不在 $L(G)$ 中的三个字符串是 a, b, 和 $\varepsilon$；(f) 假；(g) 真；(h) 假；(i) 真；(j) 真；(k) 假；(l) 真；(m) 真；(n) 假；(o) $L(G)$ 由所有不为回文串的 a 和 b 组成的字符串构成。
2.4 (a) $S \rightarrow R 1 R 1 R 1 R$
$R \rightarrow 0 R|1 R| \varepsilon$
(d) $S \rightarrow 0|0 S 0| 0 S 1|1 S 0| 1 S 1$
2.6 (a) $S \rightarrow T \mathrm{a} T$
$T \rightarrow T T|\mathrm{a} T \mathrm{~b}| \mathrm{b} T \mathrm{a}|\mathrm{a}| \varepsilon$
$T$ 生成所有 a 的数量至少与 b 的数量相同的字符串，$S$ 强制添加一个额外的 a。
(c) $S \rightarrow T X$
$T \rightarrow 0 T 0|1 T 1| \# X$
$X \rightarrow 0 X|1 X| \varepsilon$
2.7 (a) PDA 使用其堆栈来计算 a 的数量减去 b 的数量。每当此计数为正时，它就会进入接受状态。更详细地说，它的操作如下。PDA 扫描输入。如果它看到 b 且其堆栈顶部符号是 a，它会弹出堆栈。同样，如果它扫描 a 且其堆栈顶部符号是 b，它会弹出堆栈。在所有其他情况下，它会将输入符号推入堆栈。PDA 完成输入后，如果堆栈顶部是 a，它就接受。否则它就拒绝。
(c) PDA 扫描输入字符串，并将其读取的每个符号推入堆栈，直到它读取到 \#。如果从未遇到 \#，它就拒绝。然后，PDA 跳过部分输入，非确定性地决定何时停止跳过。在那一点上，它将下一个输入符号与其从堆栈中弹出的符号进行比较。在任何不一致的情况下，或者如果输入在堆栈非空时结束，则此计算分支拒绝。如果堆栈变空，机器读取输入的其余部分并接受。
2．8 这里是一个推导：
```
$\langle$ SENTENCE $\rangle \rightarrow\langle$ NOUN-PHRASE $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$
$\langle$ CMPLX-NOUN $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$
$\langle$ ARTICLE $\rangle\langle$ NOUN $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$
The $\langle$ NOUN $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$
The girl 〈VERB-PHRASE〉 →
The girl $\langle$ CMPLX-VERB $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$
The girl $\langle$ VERB $\rangle\langle$ NOUN-PHRASE $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$
The girl touches 〈NOUN-PHRASE〉 The girl touches $\langle$ CMPLX-NOUN $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$ The girl touches $\langle$ ARTICLE $\rangle\langle$ NOUN $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$ The girl touches the $\langle$ NOUN $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$ The girl touches the boy The girl touches the boy $\langle$ PREP $\rangle\langle$ CMPLX-NOUN $\rangle \rightarrow$ The girl touches the boy with $\langle$ CMPLX-NOUN $\rangle \rightarrow$ The girl touches the boy with $\langle$ ARTICLE $\rangle\langle$ NOUN $\rangle \rightarrow$ The girl touches the boy with the (NOUN) → The girl touches the boy with the flower ``` 这是另一个最左推导： ``` $\langle$ SENTENCE $\rangle \rightarrow\langle$ NOUN-PHRASE $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$ $\langle$ CMPLX-NOUN $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$ $\langle$ ARTICLE $\rangle\langle$ NOUN $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$ The $\langle$ NOUN $\rangle\langle$ VERB-PHRASE $\rangle \rightarrow$ The girl The girl The girl $\langle$ VERB $\rangle\langle$ NOUN-PHRASE $\rangle \rightarrow$ The girl touches 〈NOUN-PHRASE〉 → The girl touches $\langle$ CMPLX-NOUN $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$ The girl touches $\langle$ ARTICLE $\rangle\langle$ NOUN $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$ The girl touches the $\langle$ NOUN $\rangle\langle$ PREP-PHRASE $\rangle \rightarrow$ The girl touches the boy The girl touches the boy $\langle$ PREP $\rangle\langle$ CMPLX-NOUN $\rangle \rightarrow$ The girl touches the boy with 〈CMPLX-NOUN〉 → The girl touches the boy with $\langle$ ARTICLE $\rangle\langle$ NOUN $\rangle \rightarrow$ The girl touches the boy with the $\langle$ NOUN $\rangle \rightarrow$ The girl touches the boy with the flower ``` 这些推导中的每一个都对应着一个不同的英语含义。在第一个推导中，句子意味着女孩用花触碰了男孩。在第二个推导中，当女孩触碰男孩时，男孩正拿着花。 2．22 我们使用反证法。假设 $w$ 和 $w z$ 是 $L(G)$ 中两个不相等的字符串，其中 $G$ 是一个 DCFG。两者都是有效字符串，因此两者都有句柄，并且这些句柄必须一致，因为我们可以写 $w=x h y$ 和 $w z=x h y z=x h \hat{y}$，其中 $h$ 是 $w$ 的句柄。因此，$w$ 和 $w z$ 的第一个归约步骤分别生成有效字符串 $u$ 和 $u z$。我们可以继续这个过程直到我们获得 $S_{1}$ 和 $S_{1} z$，其中 $S_{1}$ 是起始变量。然而，$S_{1}$ 不出现在任何规则的右侧，所以我们不能归约 $S_{1} z$。这导致了矛盾。 2.30 (a) 设 $C$ 是一个上下文无关语言，$R$ 是一个正则语言。设 $P$ 是识别 $C$ 的 PDA，$D$ 是识别 $R$ 的 DFA。如果 $Q$ 是 $P$ 的状态集，$Q^{\prime}$ 是 $D$ 的状态集，我们构造一个 PDA $P^{\prime}$ 来识别 $C \cap R$，其状态集为 $Q \times Q^{\prime}$。$P^{\prime}$ 将执行 $P$ 的操作，并同时跟踪 $D$ 的状态。当且仅当它在状态 $q \in F_{P} \times F_{D}$ 停止时才接受字符串 $w$，其中 $F_{P}$ 是 $P$ 的接受状态集，$F_{D}$ 是 $D$ 的接受状态集。由于 $C \cap R$ 被 $P^{\prime}$ 识别，因此它是上下文无关的。 (b) 设 $R$ 是正则语言 $\mathrm{a}^{*} \mathrm{~b}^{*} \mathrm{c}^{*}$。如果 $A$ 是一个 CFL，那么根据 (a) 部分，$A \cap R$ 将是一个 CFL。然而，$A \cap R=\left\{\mathrm{a}^{n} \mathrm{~b}^{n} \mathrm{c}^{n} \mid n \geq 0\right\}$，并且示例 2.36 证明了 $A \cap R$ 不是上下文无关的。因此 $A$ 不是一个 CFL。 2.42 (b) 设 $B=\left\{0^{n} \# 0^{2 n} \# 0^{3 n} \mid n \geq 0\right\}$。设 $p$ 是泵引理给出的泵长度。设 $s=0^{p} \# 0^{2 p} \# 0^{3 p}$。我们证明 $s=u v x y z$ 不能被泵送。 $v$ 和 $y$ 都不能包含 \#，否则 $u v^{2} x y^{2} z$ 包含多于两个 \#。因此，如果我们用 \# 将 $s$ 分成三个段：$0^{p}, 0^{2 p}$, 和 $0^{3 p}$，则至少有一个段不包含在 $v$ 或 $y$ 中。因此 $u v^{2} x y^{2} z$ 不在 $B$ 中，因为段的 $1:2:3$ 长度比未保持。 (c) 设 $C=\left\{w \# t \mid w\right.$ 是 $t$ 的子串，其中 $\left.w, t \in\{\mathbf{a}, \mathbf{b}\}^{*}\right\}$。设 $p$ 是泵引理给出的泵长度。设 $s=\mathrm{a}^{p} \mathrm{~b}^{p} \# \mathrm{a}^{p} \mathrm{~b}^{p}$。我们证明字符串 $s=u v x y z$ 不能被泵送。 $v$ 和 $y$ 都不能包含 \#，否则 $u v^{0} x y^{0} z$ 不包含 \#，因此不在 $C$ 中。如果 $v$ 和 $y$ 都出现在 \# 的左侧，则字符串 $u v^{2} x y^{2} z$ 不可能在 $C$ 中，因为它的 \# 左侧更长。类似地，如果两个字符串都出现在 \# 的右侧，则字符串 $u v^{0} x y^{0} z$ 不可能在 $C$ 中，因为它再次在 \# 的左侧更长。如果 $v$ 和 $y$ 中的一个为空（两者不能都为空），则将其视为两者都出现在 \# 的同一侧，如上所述。 唯一剩下的情况是 $v$ 和 $y$ 都非空且跨越 \#。但那样的话，$v$ 由 b 组成，$y$ 由 a 组成，因为第三个泵引理条件 $|v x y| \leq p$。因此，$u v^{2} x y^{2} z$ 在 \# 的左侧包含更多的 b，所以它不能是 $C$ 的成员。 2.50 设 $A$ 是语言 $\left\{0^{k} 1^{k} \mid k \geq 0\right\}$，设 $B$ 是语言 $\left\{\mathrm{a}^{k} \mathrm{~b}^{3 k} \mid k \geq 0\right\}$。$A$ 和 $B$ 的完美洗牌是语言 $C=\left\{(0 \mathrm{a})^{k}(0 \mathrm{~b})^{k}(1 \mathrm{~b})^{2 k} \mid k \geq 0\right\}$。语言 $A$ 和 $B$ 很容易看出是 CFL，但 $C$ 不是 CFL，原因如下。如果 $C$ 是 CFL，设 $p$ 是泵引理给出的泵长度，设 $s$ 是字符串 $(0 \mathrm{a})^{p}(0 \mathrm{~b})^{p}(1 \mathrm{~b})^{2 p}$。因为 $s$ 比 $p$ 长，且 $s \in C$，我们可以将 $s$ 分成五部分，$s=u v x y z$，满足泵引理的三个条件。$C$ 中的字符串恰好有四分之一的 1 和八分之一的 a。为了使 $u v^{2} x y^{2} z$ 具有该性质，字符串 $v x y$ 必须同时包含 1 和 a。但这不可能，因为 1 和 a 在 $s$ 中被 $2p$ 个符号隔开，而第三个条件说 $|v x y| \leq p$。因此 $C$ 不是上下文无关的。 [^0]: ${ }^{1}$ $D K$ 这个名称是 "deterministic $K$" 的助记符，但它也代表唐纳德·克努特（Donald Knuth），他首先提出了这个想法。