5_可归约性5.1.ZH

1可归约性

在第4章中，我们将图灵机确立为通用计算机的模型。我们展示了几个可以在图灵机上解决的问题示例，并给出了一个计算上不可解的问题示例，$A_{\mathrm{TM}}$。在本章中，我们将研究一些额外的不可解问题。在此过程中，我们引入了证明问题计算上不可解的主要方法。它被称为可归约性。

归约是将一个问题转换为另一个问题的方法，使得第二个问题的解决方案可以用来解决第一个问题。这种可归约性在日常生活中经常出现，即使我们通常不这样称呼它们。

例如，假设你想在一个新城市里找到路。你知道如果有一张地图，这样做会很容易。因此，你可以将找路的问题归约到获得城市地图的问题。

可归约性总是涉及两个问题，我们称之为$A$和$B$。如果$A$归约到$B$，我们可以使用$B$的解决方案来解决$A$。所以在我们的例子中，$A$是找路的问题，$B$是获得地图的问题。请注意，可归约性并没有说明单独解决$A$或$B$的问题，而只是说明在有$B$的解决方案的情况下，$A$的可解性。

以下是可归约性的更多例子。从波士顿到巴黎旅行的问题归约到购买两城市之间机票的问题。而购买机票的问题又归约到赚取机票钱的问题。而赚取机票钱的问题又归约到找工作的问题。

可归约性也出现在数学问题中。例如，测量矩形面积的问题归约到测量其长度和宽度的问题。求解线性方程组的问题归约到求矩阵逆的问题。

可归约性在根据可判定性对问题进行分类中扮演着重要角色，在随后的复杂性理论中也同样重要。当$A$可归约到$B$时，解决$A$不会比解决$B$更难，因为$B$的解决方案也给出了$A$的解决方案。就可计算性理论而言，如果$A$可归约到$B$且$B$是可判定的，那么$A$也是可判定的。同理，如果$A$是不可判定的且可归约到$B$，那么$B$是不可判定的。这最后一个版本是证明各种问题不可判定性的关键。

简而言之，我们证明一个问题不可判定的方法是，证明某个已知不可判定的问题可以归约到它。

5.1

语言理论中的不可判定问题

我们已经确立了$A_{\mathrm{TM}}$的不可判定性，即判断图灵机是否接受给定输入的问题。让我们考虑一个相关的问题，$H A L T_{\mathrm{TM}}$，即判断图灵机是否在给定输入上停机（通过接受或拒绝）的问题。这个问题广为人知为停机问题。我们利用$A_{\mathrm{TM}}$的不可判定性，通过将$A_{\text {TM }}$归约到$H A L T_{\text {TM }}$来证明停机问题的不可判定性。设

定理 5.1

$H A L T_{\mathrm{TM}}$是不可判定的。

证明思路 这个证明是通过反证法进行的。我们假设$H A L T_{\mathrm{TM}}$是可判定的，并利用这个假设来证明$A_{\mathrm{TM}}$是可判定的，这与定理4.11相矛盾。关键思想是证明$A_{\text {TM }}$可以归约到$H A L T_{\text {TM }}$。

假设我们有一个图灵机$R$来判定$H A L T_{\text {TM }}$。然后我们使用$R$来构造$S$，一个判定$A_{\text {TM }}$的图灵机。为了感受一下构造$S$的方法，假设你就是$S$。你的任务是判定$A_{\text {TM }}$。你得到一个$\langle M, w\rangle$形式的输入。如果$M$接受$w$，你必须输出接受；如果$M$循环或拒绝$w$，你必须输出拒绝。尝试模拟$M$在$w$上的运行。如果它接受或拒绝，你也这样做。但你可能无法确定$M$是否正在循环，在这种情况下，你的模拟将不会终止。这很糟糕，因为你是一个判决器，因此绝不允许循环。所以这个想法本身是行不通的。

相反，使用你拥有判定$H A L T_{\mathrm{TM}}$的图灵机$R$的假设。有了$R$，你可以测试$M$是否在$w$上停机。如果$R$指示$M$不在$w$上停机，则拒绝，因为$\langle M, w\rangle$不在$A_{\mathrm{TM}}$中。但是，如果$R$指示$M$在$w$上停机，你可以进行模拟而没有任何循环的危险。

因此，如果图灵机$R$存在，我们可以判定$A_{\text {TM }}$，但我们知道$A_{\text {TM }}$是不可判定的。根据这个矛盾，我们可以得出结论，$R$不存在。因此，$H A L T_{\text {TM }}$是不可判定的。

证明 为了获得矛盾，我们假设图灵机$R$判定$H A L T_{\mathrm{TM}}$。我们构造图灵机$S$来判定$A_{\mathrm{TM}}$，其操作如下。

$S=$"在输入$\langle M, w\rangle$上，其中$M$是图灵机和$w$是字符串的编码：

1. 在输入$\langle M, w\rangle$上运行图灵机$R$。
2. 如果$R$拒绝，则拒绝。
3. 如果$R$接受，则模拟$M$在$w$上的运行直到停机。
4. 如果$M$接受了，则接受；如果$M$拒绝了，则拒绝。"

显然，如果$R$判定$H A L T_{\text {TM }}$，那么$S$判定$A_{\text {TM }}$。因为$A_{\text {TM }}$是不可判定的，$H A L T_{\text {TM }}$也必须是不可判定的。

定理5.1阐明了我们证明一个问题不可判定的策略。这种策略是大多数不可判定性证明所共有的，除了$A_{\text {TM }}$本身的不可判定性，它是通过对角线法直接证明的。

我们现在提出其他几个定理及其证明，作为使用归约方法证明不可判定性的进一步例子。设

定理 5.2

$E_{\mathrm{TM}}$是不可判定的。

证明思路 我们遵循定理5.1中采用的模式。我们假设$E_{\mathrm{TM}}$是可判定的，然后证明$A_{\mathrm{TM}}$是可判定的——这会产生矛盾。设$R$是判定$E_{\mathrm{TM}}$的图灵机。我们使用$R$来构造判定$A_{\mathrm{TM}}$的图灵机$S$。当$S$接收输入$\langle M, w\rangle$时，它将如何工作呢？

一个想法是让$S$在输入$\langle M\rangle$上运行$R$，看它是否接受。如果接受，我们知道$L(M)$是空的，因此$M$不接受$w$。但如果$R$拒绝$\langle M\rangle$，我们只知道$L(M)$不是空的，因此$M$接受某个字符串——但我们仍然不知道$M$是否接受特定的字符串$w$。所以我们需要使用一个不同的想法。

我们不在$\langle M\rangle$上运行$R$，而是在$\langle M\rangle$的修改版上运行$R$。我们修改$\langle M\rangle$以确保$M$拒绝除了$w$之外的所有字符串，但在输入$w$上它像往常一样工作。然后我们使用$R$来确定修改后的机器是否识别空语言。现在机器唯一能接受的字符串是$w$，所以它的语言非空当且仅当它接受$w$。如果$R$在输入修改后的机器描述时接受，我们知道修改后的机器不接受任何东西，并且$M$不接受$w$。

证明 让我们用我们的标准符号来表示证明思路中描述的修改后的机器。我们称之为$M_{1}$。

$M_{1}=$"在输入$x$上：

1. 如果$x \neq w$，则拒绝。
2. 如果$x=w$，则在输入$w$上运行$M$，如果$M$接受，则接受。"

这台机器的描述中包含字符串$w$。它通过扫描输入并逐个字符地与$w$进行比较，以确定它们是否相同，从而以显而易见的方式进行$x=w$的测试。

综上所述，我们假设图灵机$R$判定$E_{\mathrm{TM}}$，并构造图灵机$S$来判定$A_{\text {TM }}$，如下所示。

$S=$"在输入$\langle M, w\rangle$上，其中$M$是图灵机和$w$是字符串的编码：

1. 使用$M$和$w$的描述构造刚刚描述的图灵机$M_{1}$。
2. 在输入$\left\langle M_{1}\right\rangle$上运行$R$。
3. 如果$R$接受，则拒绝；如果$R$拒绝，则接受。"

如果$R$是$E_{\mathrm{TM}}$的判决器，$S$将是$A_{\mathrm{TM}}$的判决器。$A_{\mathrm{TM}}$的判决器不能存在，所以我们知道$E_{\mathrm{TM}}$必须是不可判定的。

关于图灵机的另一个有趣的计算问题是确定给定图灵机识别的语言是否也可以被更简单的计算模型识别。例如，我们让$R E G U L A R_{\mathrm{TM}}$成为判断给定图灵机是否具有等价的有限自动机的问题。这个问题等同于判断图灵机是否识别正则语言。设

定理 5.3

$R E G U L A R_{\text {TM }}$是不可判定的。

证明思路 与不可判定性定理通常一样，这个证明是通过从$A_{\mathrm{TM}}$进行归约。我们假设$R E G U L A R_{\mathrm{TM}}$可以被图灵机$R$判定，并使用这个假设来构造一个判定$A_{\text {TM }}$的图灵机$S$。现在不那么明显的是如何利用$R$的能力来帮助$S$完成任务。尽管如此，我们还是可以做到。

其思路是，$S$接收其输入$\langle M, w\rangle$，然后修改$M$，使得生成的图灵机当且仅当$M$接受$w$时才识别正则语言。我们称修改后的机器为$M_{2}$。我们设计$M_{2}$，使其在$M$不接受$w$时识别非正则语言$\left\{0^{n} 1^{n} \mid n \geq 0\right\}$，在$M$接受$w$时识别正则语言$\Sigma^{*}$。我们必须说明$S$如何从$M$和$w$构造这样的$M_{2}$。在这里，$M_{2}$通过自动接受$\left\{0^{n} 1^{n} \mid n \geq 0\right\}$中的所有字符串来工作。此外，如果$M$接受$w$，则$M_{2}$接受所有其他字符串。

请注意，图灵机$M_{2}$的构造并非是为了实际在某些输入上运行它——这是一个常见的误解。我们构造$M_{2}$仅仅是为了将其描述输入到我们假设存在的$R E G U L A R_{\mathrm{TM}}$判决器中。一旦该判决器返回其答案，我们就可以使用它来获得$M$是否接受$w$的答案。因此，我们可以判定$A_{\mathrm{TM}}$，这是一个矛盾。

证明 我们设$R$是判定$R E G U L A R_{\mathrm{TM}}$的图灵机，并构造图灵机$S$来判定$A_{\text {TM }}$。那么$S$按以下方式工作。

$S=$"在输入$\langle M, w\rangle$上，其中$M$是图灵机，$w$是字符串：

1. 构造以下图灵机$M_{2}$。

$M_{2}=$"在输入$x$上：

1. 如果$x$具有$0^{n} 1^{n}$的形式，则接受。
2. 如果$x$不具有此形式，则在输入$w$上运行$M$，如果$M$接受$w$，则接受。"
3. 在输入$\left\langle M_{2}\right\rangle$上运行$R$。
4. 如果$R$接受，则接受；如果$R$拒绝，则拒绝。"

同样，可以通过类似的证明来表明，测试图灵机的语言是否是上下文无关语言、可判定语言，甚至是有限语言的问题都是不可判定的。实际上，一个称为赖斯定理的通用结果指出，判断图灵机识别的语言的任何属性都是不可判定的。我们在问题5.16中给出赖斯定理。

到目前为止，我们证明语言不可判定的策略涉及从$A_{\text {TM }}$进行归约。有时，当我们需要证明某些语言不可判定时，从其他不可判定语言（例如$E_{\mathrm{TM}}$）进行归约会更方便。定理5.4表明，测试两台图灵机的等价性是一个不可判定的问题。我们可以通过从$A_{\mathrm{TM}}$进行归约来证明它，但我们借此机会提供一个通过从$E_{\mathrm{TM}}$进行归约来证明不可判定性的示例。设

定理 5.4

$E Q_{\text {TM }}$是不可判定的。

证明思路 证明如果$E Q_{\mathrm{TM}}$是可判定的，那么$E_{\mathrm{TM}}$也将是可判定的，方法是从$E_{\mathrm{TM}}$到$E Q_{\mathrm{TM}}$进行归约。这个想法很简单。$E_{\mathrm{TM}}$是判断图灵机的语言是否为空的问题。$E Q_{\mathrm{TM}}$是判断两台图灵机的语言是否相同的问题。如果其中一种语言恰好是$\emptyset$，我们最终的问题是判断另一台机器的语言是否为空——即$E_{\mathrm{TM}}$问题。因此，从某种意义上说，$E_{\text {TM }}$问题是$E Q_{\text {TM }}$问题的一个特例，其中一台机器被固定为识别空语言。这个想法使得归约变得容易。

证明 我们设图灵机$R$判定$E Q_{\text {TM }}$，并构造图灵机$S$来判定$E_{\text {TM }}$，如下所示。

$S=$"在输入$\langle M\rangle$上，其中$M$是图灵机：

1. 在输入$\left\langle M, M_{1}\right\rangle$上运行$R$，其中$M_{1}$是拒绝所有输入的图灵机。
2. 如果$R$接受，则接受；如果$R$拒绝，则拒绝。"

如果$R$判定$E Q_{\mathrm{TM}}$，则$S$判定$E_{\mathrm{TM}}$。但根据定理5.2，$E_{\mathrm{TM}}$是不可判定的，因此$E Q_{\mathrm{TM}}$也必须是不可判定的。

通过计算历史进行归约

计算历史方法是证明$A_{\text {TM }}$可归约到某些语言的重要技术。当要证明不可判定的问题涉及测试某事物是否存在时，此方法通常很有用。例如，此方法用于证明希尔伯特第十问题（测试多项式是否存在整数根）的不可判定性。

图灵机在输入上的计算历史仅仅是机器处理输入时所经历的配置序列。它是这台机器计算的完整记录。

定义 5.5

设$M$是一个图灵机，$w$是一个输入字符串。$M$在$w$上的接受计算历史是配置序列$C_{1}, C_{2}, \ldots, C_{l}$，其中$C_{1}$是$M$在$w$上的起始配置，$C_{l}$是$M$的接受配置，并且每个$C_{i}$根据$M$的规则合法地跟随$C_{i-1}$。$M$在$w$上的拒绝计算历史定义类似，只是$C_{l}$是拒绝配置。

计算历史是有限序列。如果$M$在$w$上不停机，则$M$在$w$上不存在接受或拒绝计算历史。确定性机器在任何给定输入上最多有一个计算历史。非确定性机器在单个输入上可能有多个计算历史，对应于各种计算分支。目前，我们继续关注确定性机器。我们第一个使用计算历史方法证明不可判定性的证明涉及一种称为线性有界自动机的机器。

定义 5.6

线性有界自动机是一种受限制的图灵机，其中磁头不允许移出包含输入的磁带部分。如果机器试图将磁头移出输入的两端，则磁头会停留在原地——就像普通图灵机的磁头不会移出磁带的左端一样。

线性有界自动机是一种内存受限的图灵机，如下图所示。它只能解决需要适应输入所用磁带的内存问题。使用比输入字母表更大的磁带字母表可以使可用内存增加一个常数因子。因此，我们说对于长度为$n$的输入，可用内存量与$n$成线性关系——因此得名。

图 5.7

线性有界自动机示意图

尽管有内存限制，线性有界自动机（LBA）的功能相当强大。例如，$A_{\mathrm{DFA}}、A_{\mathrm{CFG}}、E_{\mathrm{DFA}}$和$E_{\mathrm{CFG}}$的判决器都是LBA。每个CFL都可以由LBA判决。事实上，要找到一个不能由LBA判决的可判定语言需要一些功夫。我们将在第9章中发展这样做的技术。

在这里，$A_{\mathrm{LBA}}$是确定LBA是否接受其输入的问题。尽管$A_{\text {LBA }}$与不可判定问题$A_{\text {TM }}$相同，其中图灵机被限制为LBA，但我们可以证明$A_{\text {LBA }}$是可判定的。设

在证明$A_{\mathrm{LBA}}$的可判定性之前，我们发现以下引理很有用。它指出，当长度为$n$的字符串作为输入时，LBA只能有有限数量的配置。

引理 5.8

设$M$是一个LBA，它有$q$个状态和磁带字母表中的$g$个符号。对于长度为$n$的磁带，$M$恰好有$q n g^{n}$个不同的配置。

证明 回想一下，$M$的配置就像其计算过程中的快照。配置由控制状态、磁头位置和磁带内容组成。在这里，$M$有$q$个状态。其磁带长度为$n$，因此磁头可以位于$n$个位置之一，并且磁带上可以出现$g^{n}$种可能的磁带符号串。这三个量的乘积是$M$在长度为$n$的磁带上不同配置的总数。

定理 5.9

$A_{\text {LBA }}$是可判定的。

证明思路 为了判断LBA $M$是否接受输入$w$，我们模拟$M$在$w$上的运行。在模拟过程中，如果$M$停机并接受或拒绝，我们相应地接受或拒绝。如果$M$在$w$上循环，就会出现困难。我们需要能够检测循环，以便我们可以停机并拒绝。

检测$M$何时循环的想法是，当$M$在$w$上计算时，它会从一个配置转移到另一个配置。如果$M$重复某个配置，它将一遍又一遍地重复这个配置，从而进入循环。因为$M$是LBA，它可用的磁带量是有限的。根据引理5.8，$M$在这样数量的磁带上只能处于有限数量的配置。因此，$M$在进入它以前进入过的某个配置之前，只有有限的时间可用。通过模拟$M$引理5.8给出的步数，可以检测$M$是否正在循环。如果$M$在那之前还没有停机，它一定是在循环。

证明 判定$A_{\mathrm{LBA}}$的算法如下。

$L=$"在输入$\langle M, w\rangle$上，其中$M$是LBA，$w$是字符串：

1. 模拟$M$在$w$上的运行，持续$q n g^{n}$步或直到停机。
2. 如果$M$已停机，如果它接受了，则接受；如果它拒绝了，则拒绝。如果它没有停机，则拒绝。"

如果$M$在$w$上在$q n g^{n}$步内没有停机，它必然根据引理5.8重复了一个配置，因此正在循环。这就是为什么我们的算法在这种情况下拒绝的原因。

定理5.9表明LBA和TM在一个基本方面有所不同：对于LBA，接受问题是可判定的，但对于TM则不然。然而，某些涉及LBA的其他问题仍然是不可判定的。其中之一是空性问题$E_{\mathrm{LBA}}=\{\langle M\rangle \mid M$是一个LBA且$L(M)=\emptyset\}$。为了证明$E_{\mathrm{LBA}}$是不可判定的，我们给出一个使用计算历史方法的归约。

定理 5.10

$E_{\mathrm{LBA}}$是不可判定的。

证明思路 这个证明是通过从$A_{\mathrm{TM}}$进行归约。我们证明如果$E_{\mathrm{LBA}}$是可判定的，那么$A_{\text {TM }}$也将是可判定的。假设$E_{\mathrm{LBA}}$是可判定的。我们如何利用这个假设来判定$A_{\text {TM }}$？

对于一个图灵机$M$和一个输入$w$，我们可以通过构造一个特定的LBA $B$然后测试$L(B)$是否为空来确定$M$是否接受$w$。$B$识别的语言包含$M$在$w$上的所有接受计算历史。如果$M$接受$w$，这个语言包含一个字符串，因此是非空的。如果$M$不接受$w$，这个语言是空的。如果我们可以确定$B$的语言是否为空，显然我们可以确定$M$是否接受$w$。

现在我们描述如何从$M$和$w$构造$B$。请注意，我们不仅需要展示$B$的存在，还需要展示图灵机如何在给定$M$和$w$的描述的情况下获得$B$的描述。

正如我们为证明不可判定性而给出的先前的归约一样，我们构造$B$只是为了将其描述输入到假定的$E_{\mathrm{LBA}}$判决器中，而不是为了在某些输入上运行$B$。

我们构造$B$来接受其输入$x$，如果$x$是$M$在$w$上的接受计算历史。回想一下，接受计算历史是配置序列$C_{1}, C_{2}, \ldots, C_{l}$，这是$M$接受某个字符串$w$时所经历的。出于本证明的目的，我们假设接受计算历史表示为单个字符串，配置之间用#符号分隔，如图5.11所示。

图 5.11

$B$的一个可能的输入

LBA $B$ 的工作方式如下。当它接收到输入$x$时，$B$应该在$x$是$M$在$w$上的接受计算历史时接受。首先，$B$根据分隔符将$x$分解为字符串$C_{1}, C_{2}, \ldots, C_{l}$。然后$B$确定$C_{i}$们是否满足接受计算历史的三个条件。

1. $C_{1}$是$M$在$w$上的起始配置。
2. 每个$C_{i+1}$合法地跟随$C_{i}$。
3. $C_{l}$是$M$的接受配置。

$M$在$w$上的起始配置$C_{1}$是字符串$q_{0} w_{1} w_{2} \cdots w_{n}$，其中$q_{0}$是$M$在$w$上的起始状态。在这里，$B$直接内置了这个字符串，因此它能够检查第一个条件。接受配置是包含$q_{\text {accept }}$状态的配置，因此$B$可以通过扫描$C_{l}$寻找$q_{\text {accept }}$来检查第三个条件。第二个条件最难检查。对于每对相邻配置，$B$检查$C_{i+1}$是否合法地跟随$C_{i}$。此步骤涉及验证$C_{i}$和$C_{i+1}$除了磁头下方和相邻位置外是否相同。这些位置必须根据$M$的转移函数进行更新。然后$B$通过在$C_{i}$和$C_{i+1}$的相应位置之间进行之字形移动来验证更新是否正确完成。为了在之字形移动时跟踪当前位置，$B$用点标记磁带上的当前位置。最后，如果满足条件1、2和3，$B$接受其输入。

通过反转判决器的答案，我们得到$M$是否接受$w$的答案。因此我们可以判定$A_{\mathrm{TM}}$，这是一个矛盾。

证明 现在我们准备陈述$A_{\text {TM }}$到$E_{\text {LBA }}$的归约。假设图灵机$R$判定$E_{\mathrm{LBA}}$。构造图灵机$S$来判定$A_{\mathrm{TM}}$，如下所示。

$S=$"在输入$\langle M, w\rangle$上，其中$M$是图灵机，$w$是字符串：

1. 根据证明思路中的描述，从$M$和$w$构造LBA $B$。
2. 在输入$\langle B\rangle$上运行$R$。
3. 如果$R$拒绝，则接受；如果$R$接受，则拒绝。"

如果$R$接受$\langle B\rangle$，则$L(B)=\emptyset$。因此，$M$在$w$上没有接受计算历史，并且$M$不接受$w$。因此，$S$拒绝$\langle M, w\rangle$。同样，如果$R$拒绝$\langle B\rangle$，则$B$的语言是非空的。$B$唯一能接受的字符串是$M$在$w$上的接受计算历史。因此，$M$必须接受$w$。因此，$S$接受$\langle M, w\rangle$。图5.12展示了LBA $B$。

图 5.12

LBA $B$检查图灵机计算历史

我们也可以使用通过计算历史进行归约的技术来建立与上下文无关文法和下推自动机相关的某些问题的不可判定性。回想一下，在定理4.8中，我们提出了一个算法来判断上下文无关文法是否生成任何字符串——也就是说，是否$L(G)=\emptyset$。现在我们证明一个相关的问题是不可判定的。这就是判断上下文无关文法是否生成所有可能字符串的问题。证明这个问题是不可判定的，是证明上下文无关文法等价性问题不可判定的主要步骤。设

定理 5.13

$A L L_{\text {CFG }}$是不可判定的。

证明 这个证明是通过反证法进行的。为了得到矛盾，我们假设$A L L_{\text {CFG }}$是可判定的，并利用这个假设来证明$A_{\text {TM }}$是可判定的。这个证明类似于定理5.10的证明，但有一个小的额外转折：它是一个从$A_{\text {TM }}$通过计算历史进行的归约，但我们为了一个技术原因稍微修改了计算历史的表示方式，我们将在后面解释。

我们现在描述如何使用$A L L_{\text {CFG }}$的判决过程来判定$A_{\text {TM }}$。对于图灵机$M$和输入$w$，我们构造一个CFG $G$，当且仅当$M$不接受$w$时，它生成所有字符串。因此，如果$M$接受$w$，则$G$不会生成某些特定字符串。这个字符串是——你猜对了——$M$在$w$上的接受计算历史。也就是说，$G$被设计为生成所有不是$M$在$w$上的接受计算历史的字符串。

为了使CFG $G$生成所有不能成为$M$在$w$上接受计算历史的字符串，我们利用以下策略。一个字符串可能由于几个原因而不能成为接受计算历史。$M$在$w$上的接受计算历史形式为$\# C_{1} \# C_{2} \# \cdots \# C_{l} \#$，其中$C_{i}$是$M$在$w$上计算的第$i$步的配置。那么，$G$生成所有符合以下条件的字符串：

1. 不以$C_{1}$开头，
2. 不以接受配置结尾，或者
3. 某些$C_{i}$根据$M$的规则不能正确地生成$C_{i+1}$。

如果$M$不接受$w$，则不存在接受计算历史，因此所有字符串都以某种方式失败。因此，$G$将生成所有字符串，正如所期望的。

现在我们来具体构造$G$。我们不直接构造$G$，而是构造一个PDA $D$。我们知道可以使用定理2.20（第117页）中给出的构造将$D$转换为CFG。我们这样做是因为，出于我们的目的，设计一个PDA比设计一个CFG更容易。在这种情况下，$D$将首先非确定性地分支，猜测要检查前面三个条件中的哪一个。一个分支检查输入字符串的开头是否是$C_{1}$，如果不是则接受。另一个分支检查输入字符串是否以包含接受状态$q_{\text {accept }}$的配置结尾，如果不是则接受。

第三个分支应该在某个$C_{i}$不能正确生成$C_{i+1}$时接受。它通过扫描输入直到非确定性地决定它已经到达$C_{i}$来工作。接下来，它将$C_{i}$压入堆栈直到到达由#符号标记的末尾。然后$D$弹出堆栈以与$C_{i+1}$进行比较。它们应该匹配，除了磁头位置附近，那里的差异由$M$的转移函数决定。最后，如果$D$发现不匹配或不正确的更新，它就接受。

这个想法的问题在于，当$D$从堆栈弹出$C_{i}$时，它是倒序的，不适合与$C_{i+1}$进行比较。此时，证明中的转折出现了：我们以不同的方式写入接受计算历史。每隔一个配置以倒序出现。奇数位置仍然以正序写入，但偶数位置以倒序写入。因此，接受计算历史将如下图所示。

图 5.14

每隔一个配置倒序写入

在这种修改形式下，PDA能够压入一个配置，以便在弹出时，顺序适合与下一个配置进行比较。我们设计$D$来接受任何不是修改形式的接受计算历史的字符串。

在练习5.1中，您可以使用定理5.13来证明$E Q_{\mathrm{CFG}}$是不可判定的。