Sipser CH2 PROBLEMS'ANSWER 6-10

2.23

$且$ 这个语言（长度相等但内容不同）也是上下文无关的，因为我们可以构造一个非决定性下推自动机（NPDA）来接受它：

NPDA 非决定性地猜测一个位置，并认定和在该位置的字符不同（）。
执行逻辑：
1. 自动机读取的前个字符，但不使用栈。
2. 读取第个字符，并利用有限状态（例如，转移到“记忆0”或“记忆1”等特定状态）将其“记忆”下来。
3. 读取的后缀（之后的所有字符），每读一个字符就向栈中推入一个标记。
4. 读取 # ，然后读取的前个字符，同样不使用栈。
5. 读取的第个字符，并与状态中记忆的比较。如果两者相同，则此路不通；如果不同，则继续。
6. 读取的后缀，每读一个字符就从栈中弹出一个标记。
如果输入结束时栈正好变空，说明和的前后缀长度均对应相等，总长度也相等，且在位置存在不匹配。因此，字符串被受理。

所以，是上下文无关语言。

2.24

问题

证明语言是一个上下文无关语言 (Context-Free Language, CFL)。

解答

要证明语言是上下文无关的，我们可以通过以下两种主要方法之一：

构造一个接受该语言的下推自动机 (Pushdown Automaton, PDA)。
构造一个生成该语言的上下文无关文法 (Context-Free Grammar, CFG)。

一个更简洁的策略是，将语言分解为几个更简单的语言的并集。因为上下文无关语言类在并集运算下是封闭的，所以如果我们可以证明每个子语言都是上下文无关的，那么它们的并集（即语言）也一定是上下文无关的。

步骤 1: 分解语言 E

语言的定义条件是并且。其中。

我们可以将这个复合条件分解。

条件等价于或。

因此，一个字符串属于语言当且仅当它满足以下四个条件之一：

并且
并且
并且
并且

现在我们来分析这些条件：

对于条件 1: 如果，那么。对于所有，都有。因此，必然意味着。所以这个条件可以简化为。
对于条件 2: 如果，那么。所以条件不可能成立。这个情况对应的语言是空集。
对于条件 4: 如果，那么。这自然意味着。所以这个条件可以简化为。
对于条件 3: 并且。这个条件不能再简化，它等价于。

综上所述，语言是以下三个语言的并集： * * *

因此，。

步骤 2: 证明每个子语言都是上下文无关的

现在我们只需要证明都是上下文无关语言。

1. 证明是 CFL

我们可以为构造一个上下文无关文法。思路是，字符串可以分解为的形式，其中。，其中：

包含以下产生式：
是开始符号。

产生式生成语言。

产生式确保在的基础上，至少多一个前导。因此，生成的字符串中的数量严格大于的数量。所以，故是一个 CFL。

2. 证明是 CFL

我们可以为构造一个上下文无关文法。思路是，字符串可以分解为的形式，其中。，其中：

包含以下产生式：
是开始符号。

产生式每生成一个，就对应生成两个。产生式生成至少一个。因此，总的的数量至少是的数量的两倍加一，即，这满足。所以，故是一个 CFL。

3. 证明是 CFL

对于，构造一个非确定性下推自动机 (NPDA) 更为直观。一个字符串属于的条件是。这个条件意味着，对于每一个，都对应至少一个，但又不多于两个。并且总体来看，总的的数量严格大于的数量，且严格小于的数量的两倍。

我们可以构造一个 NPDA，其工作原理如下：

当读入字符串的部分时，对于每一个读入的，NPDA 非确定性地选择执行以下两个操作之一：
- 将一个符号（例如）压入堆栈。
- 将两个符号（例如）压入堆Stack。
当读完所有的个后，堆栈中将包含个，其中。这是因为要满足最终条件，NPDA 必须至少有一次选择压入一个，也必须至少有一次选择压入两个。（我们可以通过状态转换来强制这一点）。
当开始读入字符串的部分时，每读入一个，就从堆栈中弹出一个。
如果在读完所有的那一刻，堆栈也刚好变空，那么该字符串被接受。

这个 NPDA 能够接受的字符串必须满足，其中是堆栈中的数量。由于 NPDA 的构造保证了，因此被接受的字符串满足。所以是一个 CFL。

步骤 3: 结论

我们已经将语言表示为三个语言的并集：。我们也已经证明了 , , 和都是上下文无关语言。

由于上下文无关语言类在并集运算下是封闭的，所以这三个上下文无关语言的并集也必然是上下文无关语言。

因此，语言是一个上下文无关语言。

2.25

问题陈述

对于任意语言，定义 $使得$ 。证明上下文无关语言（CFL）类在运算下是封闭的。

证明思路

为了证明上下文无关语言类在某个运算下是封闭的，我们通常采用构造性证明。也就是说，如果我们有一个上下文无关语言，我们需要证明经过运算后得到的语言也是一个上下文无关语言。

证明一个语言是上下文无关的，主要有两种方法： 1. 为其构造一个上下文无关文法（Context-Free Grammar, CFG）。 2. 为其构造一个下推自动机（Pushdown Automaton, PDA）。

这里，我们使用第一种方法，即通过改造语言的上下文无关文法来为构建一个新的上下文无关文法。

证明过程

假设是一个上下文无关语言 (CFL)。根据定义，存在一个上下文无关文法，使得。我们的目标是构造一个新的上下文无关文法，使得。

第一步：处理空串

首先，我们可以简化问题，先考虑不包含空串的语言。令。如果我们可以证明是一个 CFL，那么我们就可以证明也是一个 CFL。这是因为：

如果，那么。
如果，那么。

由于 CFL 类在并集运算下是封闭的，而是一个（有限的，因此也是正则的）上下文无关语言，所以如果是 CFL，那么也一定是 CFL。

因此，我们只需证明对于任意不含的 CFL ，其也是 CFL。

第二步：文法规范化

对于任何不含的 CFL ，都存在一个乔姆斯基范式（Chomsky Normal Form, CNF）的文法来生成它。在 CNF 文法中，所有的产生式都具有以下两种形式之一：

(其中是非终结符)
(其中是终结符)

第三步：构造新的文法

基于，我们构造新文法。其核心思想是，对于原先的每个非终结符，我们创造两种新的非终结符：

：用于生成与原先完全相同的字符串集合。
：用于生成由所生成的任意字符串的所有后缀。

下面是的具体构造方法：

非终结符集合 :
终结符集合 : (终结符不变)
起始符号 : (因为我们的目标是生成中字符串的后缀)
产生式集合 : 中的产生式根据中的规则生成，规则如下：
- 对于中形如的规则：一个由生成的字符串就是。它的后缀是和。因此，我们向中添加以下规则：
- 对于中形如的规则：一个由生成的字符串是由一个来自的字符串和一个来自的字符串连接而成，即。的后缀有两种可能：
  1. 它完全是的一个后缀。
  2. 它包含了整个，前面还跟了的一个后缀。
  为了生成这些后缀，我们向中添加以下规则：
  - (生成完整的字符串)
  - (对应情况1，只生成的后缀)
  - (对应情况2，生成的后缀拼接上完整的 )

第四步：证明构造的正确性

我们需要证明我们构造的文法确实生成了，即。这可以通过证明一个更强的结论来实现：对于任意非终结符：

(a) 的证明：

通过观察构造过程，我们可以发现所有带有 full 下标的非终结符的产生式都与原 G 中的产生式一一对应。对应，对应。因此，从出发的任何推导都与从出发的推导具有完全相同的结构。所以成立。

(b) 的证明： 我们可以通过对推导长度的归纳来证明这个等式。

证明

假设，这意味着存在某个使得。我们对的推导步骤数进行归纳。

基础情况: 推导为一步。此时。后缀只能是或。根据我们的构造，中有规则和。所以。
归纳步骤: 假设推导的第一步是，所以。字符串可以被分解为，其中且。
- 情况 i: 之间的分割点在内部。即且，其中。这意味着。根据归纳假设，。由于中有规则，所以，因此。
- 情况 ii: 之间的分割点在内部或边界上。即，其中。这意味着并且。根据归纳假设，。又因为，所以。中有规则，所以。因此。

证明

假设。我们对的推导步骤数进行归纳。

基础情况: 推导为一步或。这要求原语法中必须有规则。和都是的后缀，而。所以。
归纳步骤: 假设推导的第一步是。
- 情况 i: 规则是 (原规则为 )。。根据归纳假设，，即存在使得。因为是中的规则，我们可以任取一个，然后得到。令，则。因此。
- 情况 ii: 规则是 (原规则为 )。可以被分解为，其中且。根据归纳假设，且。意味着存在使得。由于是中的规则，那么。这个字符串可以写成。因此。

综上所述，我们证明了。由于，我们有。

结论

我们已经成功地为任意一个上下文无关语言构造出了一个上下文无关文法，该文法生成的语言恰好是。这就证明了也是一个上下文无关语言。

因此，上下文无关语言类在运算下是封闭的。

2.26

陈述

证明：如果 G 是一个 Chomsky 范式 (CNF) 的上下文无关文法 (CFG)，那么对于 L(G) 中任意长度为 () 的字符串，的任何推导都需要恰好步。

证明

1. 回顾 Chomsky 范式 (CNF) 的定义

一个上下文无关文法 G 如果是 Chomsky 范式，那么它的所有产生式规则都必须是以下两种形式之一：

(其中 A, B, C 都是非终结符)
(其中 A 是非终结符, a 是终结符)

(注：对于可能产生空串的语言，允许有规则，其中 S 是开始符号。但本题明确指出字符串长度，所以我们不考虑产生空串的情况。)

2. 分析推导过程中的规则类型和作用

一个从开始符号 S 推导出最终字符串的过程，就是一系列应用上述产生式规则的步骤。我们可以将推导步骤分为两类，并分析它们各自的作用：

类型 1:
- 这类规则是推导过程中唯一能够产生终结符的规则。
- 最终的字符串的长度为，意味着它包含个终结符。
- 由于每应用一次类型 1 规则只会产生一个终结符，因此要生成长度为的字符串，必须且正好使用次这种类型的规则。
类型 2:
- 这类规则的作用是将一个非终结符替换为两个非终结符。
- 我们来观察推导过程中非终结符数量的变化：每应用一次规则，推导式中的非终结符总数会净增加 1 (一个非终结符 A 消失，两个非终结符 B 和 C 出现)。

3. 组合分析并计算总步数

一个完整的推导从一个单一的非终结符——开始符号 S——开始。推导的最终目标是生成一个由个终结符组成的字符串。

推导的起点：推导开始时，我们只有一个非终结符 S。
推导的终点：推导结束时，我们有一个长度为的终结符串。
中间过程：为了从非终结符得到终结符，我们必须使用次类型 1 () 的规则。这些规则将个非终结符分别转换为个终结符。因此，在应用这些规则之前，推导式中必须正好有个非终结符。
计算类型 2 规则的步数：我们的任务是从 1 个非终结符 (S) 开始，通过应用类型 2 () 的规则，最终得到一个含有个非终结符的串。
- 初始状态：1 个非终结符。
- 目标状态：个非终结符。
- 每应用一次规则，非终结符数量增加 1。
- 因此，从 1 个非终结符变为个非终结符，需要执行的步数是次。
- 所以，任何推导都必须包含恰好次类型 2 () 的规则应用。
计算总步数：
- 应用类型 1 () 规则的步数 =
- 应用类型 2 () 规则的步数 =
- 总推导步数 = (类型 1 步数) + (类型 2 步数)
- 总推导步数 =

结论

对于任何在 Chomsky 范式文法 G 中的字符串（长度），其任何推导过程都精确地包含次将非终结符转换为终结符的操作和次扩展非终结符的操作。因此，总的推导步数恰好为。

证明完毕。

2.27

考虑字符串'if condition then if condition then a:=1 else a:=1' 容易看出有两个解析树(else匹配不同的if)
新的无模糊文法可以定义如下：

变量集合
终端符号集合 :
起始符号:
产生式规则 R′:

More info for this

ZC's Blog