2_上下文无关语言2.2.ZH解释

本段是下推自动机（Pushdown Automaton, PDA）的引言，旨在建立一个初步的概念。它将新概念与我们已经了解的有限自动机进行对比，并点出其核心区别与能力提升。

1. “一种新型的计算模型，称为下推自动机”:
   • 计算模型是一个数学上的抽象概念，它描述了计算机如何解决问题。我们之前学习的有限自动机（FA）就是一种简单的计算模型。图灵机是更强大的计算模型。这里的下推自动机是介于两者之间的一种模型。它定义了一套规则和组件，用来精确地描述一类计算过程。
2. “这些自动机类似于非确定性有限自动机”:
   • 这句话是在告诉我们，下推自动机不是一个全新的、凭空出现的概念，而是建立在非确定性有限自动机（Nondeterministic Finite Automaton, NFA）基础之上的。
   • 相似之处在于：它们都有状态（States）、状态转移（Transitions）、一个输入带（Input Tape）和一个读头（Read Head）。它们都是从一个开始状态出发，根据当前状态和读取到的输入符号来决定下一步要进入哪个状态。非确定性意味着在某个状态下，对于同一个输入，可能有多条路径可以选择。
3. “但它们有一个额外的组件，称为栈”:
   • 这是下推自动机与有限自动机最根本、最重要的区别。栈（Stack）是一种数据结构，你可以把它想象成一个只能在一端操作的容器（比如一个桶或一叠盘子）。
   • 这个栈为自动机提供了一种内存。
4. “栈提供了超越控制中可用有限内存的额外内存”:
   • 有限自动机的“内存”仅仅是它的状态。因为状态的数量是有限的，所以它的记忆能力也是有限的。它只能记住有限种模式或信息。例如，一个有5个状态的FA，最多只能区分5种不同的情况。
   • 下推自动机的栈是无限深的。这意味着它理论上可以存储无限多的信息。这就克服了有限自动机的根本局限性。“超越控制中可用有限内存”指的就是超越了由有限状态所提供的内存。
5. “栈允许下推自动机识别某些非正则语言”:
   • 这是引入栈这个额外组件的直接结果和最终目的。我们知道，有限自动机只能识别正则语言。对于像 $L = \{0^n1^n \mid n \ge 0\}$ 这样的语言（0的个数必须和1的个数相等），有限自动机是无能为力的，因为它需要“计数”，而它的有限状态无法记录任意大的数量 $n$。
   • 下推自动机因为有了无限栈，就可以解决这个问题。它可以把所有读到的0都“压入”栈中，然后每读到一个1，就从栈中“弹出”一个0。最后检查栈是否为空，就能判断0和1的数量是否相等。因此，下-推自动机能识别的语言集合（即上下文无关语言）比正则语言更大。

这一段揭示了本章一个核心的理论结果，即下推自动机（PDA）和上下文无关文法（Context-Free Grammar, CFG）之间的深刻联系。

1. “下推自动机在能力上与上下文无关文法等价”:
   • 这是一个非常强有力的声明，是计算理论中的一个基石性定理。
   • “能力上等价”意味着：对于任何一个可以用上下文无关文法描述的语言（即上下文无关语言），都存在一个下推自动机能够识别它。反之，对于任何一个可以被下推自动机识别的语言，也都存在一个上下文无关文法能够生成它。
   • 它们是描述同一类语言集合（上下文无关语言集）的两种不同工具。一个是生成式的（CFG），一个是识别式的（PDA）。
2. “这种等价性非常有用，因为它为我们证明一种语言是上下文无关的提供了两种选择”:
   • 这解释了上述理论等价性的实践意义。当我们想证明一个语言 $L$ 属于上下文无关语言这个类别时，我们不必局限于一种方法。
   • 选择1：构造一个CFG。我们要设计一套产生式规则，这套规则能且只能生成语言 $L$ 中的所有字符串。
   • 选择2：构造一个PDA。我们要设计一个下推自动机，这个自动机能且只能接受语言 $L$ 中的所有字符串。
   • 拥有两种工具就像一个木匠既有锤子又有螺丝刀，可以根据具体情况选择最称手的工具。
3. “某些语言更容易用生成器来描述，而另一些则更容易用识别器来描述”:
   • 这里给出了为什么拥有两种选择是件好事。
   • 生成器（CFG）的优势: 对于具有递归、嵌套结构的语言，使用文法来描述通常非常自然和直观。比如编程语言的表达式、if-else 结构等。
   • 识别器（PDA）的优势: 对于需要“匹配”或“计数”的语言，使用自动机的思路来描述通常更直接。比如前面提到的 $\{0^n1^n\}$，用PDA的“压栈-弹栈”模型来描述就非常清晰。

这一部分通过一张图示，回顾了有限自动机（FA）的基本构造，为接下来引出下推自动机的示意图做铺垫。

1. “下图是有限自动机示意图”: 这明确了图像的内容，是一个高度抽象的、表示有限自动机工作方式的框图。
2. “控制表示状态和转移函数”:
   • 图中的 "FINITE CONTROL"（有限控制）是自动机的大脑。
   • 它内部包含了自动机的所有状态（比如 $q_0, q_1, \dots, q_n$）。因为状态数量是有限的，所以这个控制单元被称为“有限控制”。
   • 它还包含了转移函数 $\delta$。转移函数是一套规则，它规定了在某个状态下，当输入磁头读取到某个符号时，自动机应该转移到哪个新状态。例如，$\delta(q_i, a) = q_j$。
3. “纸带包含输入字符串”:
   • 图中的 "INPUT TAPE"（输入带）是用来存放待处理的字符串的。
   • 这个纸带被划分成一个个的小格子，每个格子里存放一个输入符号。例如，如果输入是 "aba"，那么纸带上就是 a | b | a。
   • 通常我们假设纸带是只读的，并且磁头只能从左向右移动，不能后退。
4. “箭头表示输入磁头，指向要读取的下一个输入符号”:
   • 图中的向下箭头就是 "INPUT HEAD"（输入磁头）。
   • 它的作用是在任意时刻指向输入带上的一个格子，表示这是自动机当前正要处理的符号。
   • 每当自动机完成一次状态转移，磁头通常会向右移动一格，准备读取下一个符号。

这张图和前一张图（图2.11）形成了鲜明的对比，直观地展示了下推自动机（PDA）相比于有限自动机（FA）的核心增量。

1. “通过添加栈组件”: 这句话点明了从 FA 到 PDA 的演化路径：PDA = FA + Stack。
2. 分析图示:
   • 保留部分: 和图2.11一样，图2.12中依然有 "FINITE CONTROL"（有限控制）、"INPUT TAPE"（输入带）和 "INPUT HEAD"（输入磁头）。这说明 PDA 继承了 FA 的基本框架。
   • 新增部分: 图的左侧显著增加了一个名为 "STACK"（栈）的垂直组件。这个栈与有限控制单元相连。
   • 交互: 有限控制单元现在不仅连接着输入磁头，还连接着栈。图示中的双向箭头表明，有限控制既可以向栈写入信息（压栈，Push），也可以从栈读取信息（弹栈，Pop）。
3. 工作流程的变化:
   • 在 FA 中，转移函数 $\delta$ 的决策依据仅仅是：当前状态 和 当前输入符号。即 (currentState, inputSymbol) -> nextState。
   • 在 PDA 中，转移函数 $\delta$ 的决策依据变成了三个：当前状态、当前输入符号 和 栈顶符号。即 (currentState, inputSymbol, stackTopSymbol) -> (nextState, newStackTop)。
   • PDA 的每一步动作，不仅可以改变状态，还可以改变栈的内容。这使得自动机的行为变得更加丰富和强大。

这一段详细解释了下推自动机核心组件——栈（Stack）的工作原理和特性。

1. “可以在栈上写入符号，并在稍后读回它们”:
   • 这定义了栈的基本功能：存储和检索。PDA的控制单元可以把一些信息（以符号的形式）存入栈，以便在未来的某个时刻使用这些信息。
2. “写入一个符号会‘向下推’栈上的所有其他符号”:
   • 这是对压栈（Push）操作的形象描述。想象一摞盘子，当你放一个新盘子在最上面时，原来所有的盘子都被“向下推”了一点位置。在数据结构中，这意味着新元素被放置在了集合的“顶部”。
3. “在任何时候，都可以读取并移除栈顶的符号。然后，剩余的符号会向上移动”:
   • 这是对弹栈（Pop）操作的描述。你只能拿走最上面的那个盘子。一旦你拿走了它，它下面的那个盘子就成了新的最顶部的盘子，仿佛“向上移动”了。
   • “读取并移除”是一个原子操作。你看一眼栈顶符号是什么，然后这个符号就从栈中消失了。
4. “在栈上写入符号通常被称为压栈（pushing the symbol），而移除符号则被称为弹栈（popping it）”:
   • 这里给出了这两个基本操作的标准术语：Push 和 Pop。
5. “请注意，对栈的所有访问，无论是读取还是写入，都只能在顶部进行”:
   • 这是栈最根本的约束。你不能“伸手”到栈的中间或底部去拿或放一个符号。所有的操作都严格限制在栈的唯一一个访问点——栈顶（Top of the Stack）。
6. “换句话说，栈是一种‘后进先出’的存储设备”:
   • “后进先出” (Last-In, First-Out, LIFO) 是对栈行为的高度概括。
   • 后进 (Last-In): 最晚被压入栈的元素，位于栈的最顶部。
   • 先出 (First-Out): 当执行弹栈操作时，这个最晚被放进去的元素，总是第一个被取出来。
7. “如果某些信息被写入栈，然后又写入了额外的信息，那么较早的信息在较晚的信息被移除之前是不可访问的”:
   • 这是 LIFO 原则的直接推论。你把笔记A放进箱子，再把笔记B放在A上面。在你拿出笔记B之前，你是绝对拿不到笔记A的。这强调了栈内信息的访问顺序是严格受限的。

这一段用一个非常生动和常见的现实生活例子——自助餐厅的盘子分发器——来进一步巩固对栈（Stack）工作原理的理解。

1. “自助餐厅餐具柜上的盘子说明了栈”:
   • 直接点明类比物。作者认为这个例子能极好地阐释栈的LIFO（后进先出）特性。
2. “这叠盘子放在一个弹簧上，因此当一个新盘子放在栈顶时，下面的盘子会向下移动”:
   • 这描述了压栈（Push）操作。
   • 新盘子: 对应要压入栈的新符号。
   • 放在栈顶: 对应压栈操作，新元素成为栈顶。
   • 弹簧: 这是这个类比的精髓。它确保了盘子堆的顶部永远保持在同一个高度，方便取用。在数据结构中，这意味着我们总是有个固定的指针或引用指向栈顶，而不需要关心栈当前有多深。
   • 下面的盘子向下移动: 对应栈中已有的元素在逻辑上被“推”得更深了。
3. “下推自动机上的栈就像一叠盘子，每个盘子上都写有一个符号”:
   • 这里将类比物与我们的主题下推自动机直接关联起来。
   • 一叠盘子: 对应PDA中的栈。
   • 每个盘子: 对应栈中的一个存储单元。
   • 盘子上写的符号: 对应栈中存储的栈字母表中的符号（例如 '0', 'A', '$' 等）。PDA通过这些符号来记录信息。

本段阐明了栈的核心价值所在——无限内存，并用一个经典的例子 $\{0^n1^n\}$ 来具体说明这个价值是如何体现在语言识别能力上的。

1. “栈之所以有价值，是因为它可以存储无限量的信息”:
   • 这是对栈作用的根本性论断。在计算理论中，一个模型的“能力”很大程度上取决于其“内存”的类型和大小。
   • 无限量是关键。与有限自动机的有限状态（有限内存）形成鲜明对比。
2. “回想一下，有限自动机无法识别语言 $\left\{0^{n} 1^{n} \mid n \geq 0\right\}$，因为它无法在其有限内存中存储非常大的数字”:
   • 这是一个重要的回顾，用一个我们熟悉的失败案例来反衬PDA的成功。
   • 为什么FA无法识别? 要验证一个字符串是否属于 $\{0^n1^n\}$，机器必须确保'0'的数量和'1'的数量完全相等。这意味着机器在读完所有的'0'之后，必须“记住”到底读了多少个'0'。如果 $n$ 可以是任意大的非负整数（例如 $n=10^{100}$），那么需要记忆的状态也需要是无限的。但有限自动机的状态数是有限的（比如 $k$ 个），它最多只能精确地区分 $k$ 种不同的计数值。一旦 $n > k$，FA就会“混淆”，无法区分是 $n$ 个'0'还是 $n+1$ 个'0'。这就是著名的“泵引理”所揭示的根本局限。
3. “PDA能够识别这种语言，因为它可以使用其栈来存储它所看到的 0 的数量”:
   • 这里给出了PDA成功的秘诀。PDA不需要用有限的状态去“硬记”数字 $n$。
   • 它采用了一种更聪明的方式：映射。它将看到的'0'的数量，映射为栈中存储的符号的数量。来一个'0'，我就往栈里放一个标记物。
   • 因为栈是无限的，所以无论 $n$ 有多大，栈都有足够的空间来存放 $n$ 个标记物。
4. “因此，栈的无限性允许 PDA 存储无限大的数字”:
   • 这是对上一句的总结和升华。PDA通过将数字（计数）转换为栈的深度，间接地实现了存储无限大数字的能力。
5. “下面的非正式描述展示了这种语言的自动机是如何工作的”:
   • 预告了接下来将要给出的、不涉及形式化定义的、易于理解的算法描述。

这是对识别语言 $L = \{0^n1^n \mid n \ge 0\}$ 的PDA工作算法的非正式描述。它把整个过程分解为几个清晰的步骤。

1. “从输入中读取符号”: 这是自动机的基本动作，输入磁头从左到右扫描字符串。
2. “每读取一个 0，就将其压栈”:
   • 这是算法的第一阶段，处理字符串的前半部分（0的部分）。
   • “将其压栈”是一种简略说法，实际上是压入一个代表'0'的栈符号。这个栈符号可以是 '0' 本身，也可以是任何我们指定的特殊符号，比如 '$' 或者 'X'。
   • 这个阶段，PDA像一个计数器，把看到的'0'累积在栈里。
3. “一旦看到 1，每读取一个 1 就从栈中弹栈一个 0”:
   • 这是算法的第二阶段，处理字符串的后半部分（1的部分）。
   • “一旦看到 1” 标志着阶段的转换。PDA从“只读0”模式切换到“只读1”模式。
   • “弹栈一个 0”：这里的 '0' 指的是第一阶段压入的那个代表'0'的栈符号。这个操作是在消耗之前累积的计数。
4. “如果输入读取完成时栈恰好清空了 0，则接受输入”:
   • 这是“成功”的条件。
   • 输入读取完成: 输入磁头已经移过了最后一个符号。
   • 栈恰好清空: 栈里不再有代表'0'的那些符号了。（可能还有一个特殊的栈底标记，后面会讲到）。
   • 这个条件同时满足，意味着压栈的次数（'0'的数量）和弹栈的次数（'1'的数量）完全相等。因此，字符串的形式是 $0^n1^n$。
5. “如果栈在 1 仍然存在时清空，或者 1 读取完成时栈仍然包含 0，或者在 1 之后输入中出现任何 0，则拒绝输入”:
   • 这里列举了三种“失败”的条件。
   • a) “栈在 1 仍然存在时清空”: 这意味着'0'的数量少于'1'的数量。比如输入 "011"。我们压栈一个'0'，然后弹栈一个'0'，此时栈空了，但输入带上还有一个'1'没读。这说明 $n < m$ in $0^n1^m$。拒绝。
   • b) “1 读取完成时栈仍然包含 0”: 这意味着'0'的数量多于'1'的数量。比如输入 "001"。我们压栈两个'0'，然后读一个'1'并弹栈一个'0'。此时输入结束了，但栈里还剩一个'0'。这说明 $n > m$ in $0^n1^m$。拒绝。
   • c) “在 1 之后输入中出现任何 0”: 这破坏了 $0^n1^n$ 的格式要求（所有的0必须在所有的1之前）。比如输入 "010"。PDA在读到第二个'0'时，因为它已经进入了“读1”的模式，所以没有合法的转移路径。计算卡住，拒绝。

这一小段揭示了下推自动机（PDA）与其前辈有限自动机（FA）之间一个至关重要的理论差异。

1. “如前所述，下推自动机可能具有非确定性”:
   • 这句话重申了PDA模型的一个基本特性。像NFA一样，PDA的转移函数在某个情况下可以有多个选择。
   • 一个非确定性的PDA（Nondeterministic Pushdown Automaton, NPDA）在面对 (当前状态, 当前输入, 栈顶符号) 的组合时，可能有多种合法的下一步动作，比如：
   • 选择转移到状态 A 并压栈 X。
   • 或者选择转移到状态 B 并弹栈 Y。
   • 或者选择停在当前状态，不读输入，只操作栈。
   • NPDA的计算可以看作是一棵计算树，只要其中有一条路径能够成功到达接受状态，输入的字符串就被接受。
2. “确定性下推自动机和非确定性下推自动机在能力上并不等价”:
   • 这是本段的核心，也是计算理论中一个非常重要的结论。
   • 确定性下推自动机（Deterministic Pushdown Automaton, DPDA）在任何时候都只有一个唯一的、确定的下一步动作。它的转移函数对于任何合法的 (状态, 输入, 栈顶) 组合，最多只能映射到一个 (新状态, 新栈操作)。
   • “能力上并不等价”意味着存在一些语言，它们可以被NPDA识别，但是不可能被任何DPDA识别。
   • 这与有限自动机的情况形成了鲜明对比。我们知道，对于任何一个NFA，都存在一个等价的DFA。DFA和NFA在语言识别能力上是等价的，它们都只能识别正则语言。
   • 但在下推自动机的世界里，非确定性赋予了模型更强的计算能力。

本段是对前一段观点的进一步阐述和总结，并为后续内容的安排提供了路线图。

1. “非确定性下推自动机识别某些语言，这是任何确定性下推自动机都无法识别的，我们将在 2.4 节中看到”:
   • 再次强调了NPDA比DPDA更强大。
   • 并给出了一个明确的“预告”：关于这个主题的正式讨论和证明将在2.4节出现。这有助于管理读者的预期。
   • 上下文无关语言的集合可以被划分为两部分：一部分是确定性上下文无关语言（可以被DPDA识别），另一部分是纯粹的非确定性上下文无关语言（只能被NPDA识别）。
2. “我们在示例 2.16 和 2.18 中给出了需要非确定性的语言”:
   • 这里再次预告，即将到来的两个例子（2.16和2.18）将会是展示非确定性必要性的具体案例。这让读者带着问题意识去阅读接下来的例子。
3. “回想一下，确定性和非确定性有限自动机确实识别同一类语言，因此下推自动机的情况是不同的”:
   • 通过再次与有限自动机进行对比，加深读者对PDA特殊性的印象。这种反复的对比是一种有效的教学方法。
   • FA的世界：DFA 能力 = NFA 能力
   • PDA的世界：DPDA 能力 < NPDA 能力
4. “我们关注非确定性下推自动机，因为这些自动机在能力上与上下文无关文法等价”:
   • 这解释了为什么本书（以及大多数计算理论教材）将重点放在NPDA上。
   • 那个核心的、优美的等价定理（PDA 能力 = CFG 能力）是建立在非确定性模型之上的。DPDA只能对应上下文无关文法的一个子集（即确定性上下文无关文法），无法与整个CFG家族等价。
   • 为了捕获所有上下文无关语言，我们必须使用非确定性的PDA。

本段开始进入下推自动机（PDA）的形式化定义部分，首先介绍了定义中新增的元素。

1. “下推自动机的形式定义类似于有限自动机，除了栈”:
   • 再次使用类比法。PDA的定义是一个六元组，而FA的定义是一个五元组。大部分组件是共享的或类似。
   • FA: $(Q, \Sigma, \delta, q_0, F)$
   • PDA将会增加与栈相关的组件。
2. “栈是一种包含从某个字母表中提取的符号的设备”:
   • 这定义了栈的内容。栈里面存放的不是任意的东西，而是一些预先定义好的符号。
   • 这就引出了一个新的“字母表”概念，专门用于栈。
3. “机器可以使用不同的字母表作为其输入字母表和栈字母表”:
   • 这是一个重要的区分。
   • 输入字母表 ($\Sigma$): 这是语言本身的符号集，是输入带上可能出现的符号。例如，对于 $\{0^n1^n\}$，$\Sigma = \{0, 1\}$。
   • 栈字母表 ($\Gamma$): 这是可以存放在栈里的符号集。
   • 这两个字母表可以是相同的，也可以是不同的，甚至可以有交集。通常，为了方便，我们会让 $\Sigma \subseteq \Gamma$，但这不是必须的。
4. “因此现在我们指定输入字母表 $\Sigma$ 和栈字母表 $\Gamma$”:
   • 在PDA的定义元组中，我们将需要明确地列出这两个字母表。
   • $\Sigma$ (Sigma): 代表输入字母表。
   • $\Gamma$ (Gamma): 代表栈字母表。

这一段聚焦于PDA形式定义中最复杂、最核心的部分——转移函数 $\delta$，详细解释了它的输入（定义域）。

1. “任何自动机的形式定义的核心是转移函数，它描述了其行为”:
   • 强调了转移函数 $\delta$ 的中心地位。它就是自动机的“程序”或“规则手册”，规定了自动机在所有可能情况下的所有合法动作。
2. “回想一下，$\Sigma_{\varepsilon}=\Sigma \cup\{\varepsilon\}$ 和 $\Gamma_{\varepsilon}=\Gamma \cup\{\varepsilon\}$”:
   • 这里引入了 $\varepsilon$-notation（epsilon notation）作为简写。
   • $\Sigma_{\varepsilon}$: 表示输入字母表 $\Sigma$ 加上空字符串 $\varepsilon$。这意味着PDA的一次转移可以“不消耗”任何输入符号，即输入磁头不移动。这被称为 $\varepsilon$-转移。
   • $\Gamma_{\varepsilon}$: 表示栈字母表 $\Gamma$ 加上 $\varepsilon$。这在转移函数的定义域和值域中都有特殊含义。
   • 在定义域中（作为输入），栈顶符号 = ε 表示我们不关心栈顶是什么，或者说，这个转移不依赖于栈顶符号（在某些定义中，这可能意味着栈是空的）。更常见的解释是，这个转移不需要从栈中弹出任何符号。
   • 在值域中（作为输出），压栈符号 = ε 意味着弹栈后不压入任何新符号，这实际上就是一个纯粹的弹栈（pop）操作。
3. “转移函数的域是 $Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon}$”:
   • 这句话用数学语言精确定义了PDA做决策所需要的所有信息。域（Domain）就是函数的输入。
   • $Q$: 当前所在的状态。
   • $\Sigma_{\varepsilon}$: 当前输入磁头指向的符号，或者是 $\varepsilon$（表示不读输入）。
   • $\Gamma_{\varepsilon}$: 当前栈顶的符号，或者是 $\varepsilon$（表示不关心/不消耗栈顶符号）。
   • 这个三元组 (state, input, stack_top) 完整地描述了PDA在任一时刻的“局面”（configuration）。
4. “因此，当前状态、读取的下一个输入符号和栈顶符号决定了下推自动机的下一个动作”:
   • 这是对上一句数学定义的自然语言翻译，清晰明了。
5. “任一符号都可以是 $\varepsilon$，导致机器在不读取输入符号或不读取栈符号的情况下移动”:
   • 强调了 $\varepsilon$ 的作用，它为PDA提供了巨大的灵活性。
   • 不读取输入符号 ($\varepsilon$-move on input): 允许PDA在“原地”思考，只改变自己的状态和栈内容，而输入磁头不前进。这对于处理内部逻辑和准备后续步骤非常重要。
   • 不读取栈符号 ($\varepsilon$-move on stack): 允许PDA在不消耗栈顶元素的情况下进行状态转移和压栈。这相当于一个纯粹的压栈操作，因为它没有弹出任何东西。

这一段接着上一段，定义了PDA转移函数 $\delta$ 的输出（值域或范围），并正式引入了非确定性。

1. “对于转移函数的范围，我们需要考虑当自动机处于特定情况时允许它做什么”:
   • 范围 (Range) 或 值域 (Codomain) 指的是函数的输出集合。上一段定义了输入 (状态, 输入, 栈顶)，这一段定义了输出是什么。
   • 自动机的动作包括两个方面：改变状态和改变栈。
2. “它可能会进入某个新状态，并可能在栈顶写入一个符号”:
   • 进入某个新状态: 输出的一部分是 $Q$ 中的一个元素，即下一个状态。
   • 在栈顶写入一个符号: 输出的另一部分是 $\Gamma$ 中的一个元素，即要压入栈的符号。
   • “可能” 这个词很重要。如果写入的是 $\varepsilon$ 呢？那就意味着不写入任何符号，这对应于一个纯粹的弹栈操作。所以输出的栈符号来自 $\Gamma_{\varepsilon} = \Gamma \cup \{\varepsilon\}$。
3. “函数 $\delta$ 可以通过返回 $Q$ 的一个成员和 $\Gamma_{\varepsilon}$ 的一个成员来指示此操作，即 $Q \times \Gamma_{\varepsilon}$ 的一个成员”:
   • 这给出了一个确定性动作的输出形式：一个序对 (next_state, symbol_to_push)。
   • 这个序对属于笛卡尔积 $Q \times \Gamma_{\varepsilon}$。
4. “因为我们允许此模型中的非确定性，所以一种情况可能有几个合法的下一步动作”:
   • 这是关键的一步，引入了非确定性。
   • 对于同一个输入三元组 (q, a, x)，PDA 可能有多个选择。比如，既可以转移到 (q1, Y)，也可以转移到 (q2, Z)。
5. “转移函数以通常的方式结合了非确定性，通过返回 $Q \times \Gamma_{\varepsilon}$ 的成员集，即 $\mathcal{P}\left(Q \times \Gamma_{\varepsilon}\right)$ 的成员”:
   • 这里解释了如何在数学上表示非确定性。我们不返回单个序对，而是返回一个包含所有可能序对的集合。
   • $\mathcal{P}(S)$ 是集合 $S$ 的幂集（Power Set），代表 $S$ 的所有子集构成的集合。
   • 因此，$\delta$ 的输出是 $\mathcal{P}\left(Q \times \Gamma_{\varepsilon}\right)$ 中的一个元素，也就是一个形如 {(q1, Y), (q2, Z), ...} 的集合。
   • 如果某个转移是确定性的，那么这个返回的集合里就只有一个元素。如果某个转移是不允许的，就返回空集 $\emptyset$。
6. “总而言之，我们的转移函数 $\delta$ 的形式为 $\delta: Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon} \longrightarrow \mathcal{P}\left(Q \times \Gamma_{\varepsilon}\right)$”:
   • 这是对PDA转移函数的最终、完整的形式化定义。
   • $\delta$: 转移函数的名称。
   • :: 读作 "maps from" (从...映射)。
   • $Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon}$: 定义域（输入），一个三元组 (当前状态, 当前输入或ε, 栈顶符号或ε)。
   • $\longrightarrow$: 映射箭头。
   • $\mathcal{P}\left(Q \times \Gamma_{\varepsilon}\right)$: 值域（输出），一个可能的新 (状态, 压栈符号或ε) 序对的集合。

这是下推自动机（PDA）的完整、形式化的定义。它将PDA定义为一个包含六个部分的数学对象（一个6元组）。

1. “下推自动机是一个 6 元组 (...)”:
   • 元组 (Tuple) 是一种包含了固定数量元素的数学结构。说PDA是6元组，意味着要完整地描述一个PDA，我们必须且只需指定这六个组件。
   • 对比：有限自动机（DFA/NFA）是5元组 $(Q, \Sigma, \delta, q_0, F)$。PDA多了一个组件 $\Gamma$（栈字母表），并且转移函数 $\delta$ 的形式也更复杂。
2. “$Q, \Sigma, \Gamma$ 和 $F$ 都是有限集”:
   • 这是一个重要的约束。
   • $Q$ (状态集) 是有限的，这使得控制部分是“有限控制”。
   • $\Sigma$ (输入字母表) 是有限的。
   • $\Gamma$ (栈字母表) 也是有限的。虽然栈的深度是无限的，但可以往里面放的符号种类是有限的。
   • $F$ (接受状态集) 是有限的，它是 $Q$ 的一个子集。
3. 逐项解释六元组:
   • 1. $Q$ 是状态集:
   • 和FA一样，代表自动机所有可能的内部状态。例如，{q_start, q_reading_zeros, q_reading_ones, q_accept}。
   • 2. $\Sigma$ 是输入字母表:
   • 定义了哪些符号可以出现在输入带上。例如，{0, 1}。
   • 3. $\Gamma$ 是栈字母表:
   • 这是PDA新增的组件。定义了哪些符号可以被压入栈中。例如，{Z, $}`，其中 Z 用来计数，`$ 用作栈底标记。
   • 4. $\delta: Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon} \longrightarrow \mathcal{P}\left(Q \times \Gamma_{\varepsilon}\right)$ 是转移函数:
   • 这是PDA的“大脑”，定义了它的全部行为，正如前文所详细解释的。它根据 (当前状态, 输入符号, 栈顶符号) 决定一个或多个 (新状态, 压栈符号) 的动作。
   • 5. $q_{0} \in Q$ 是开始状态:
   • 和FA一样，这是自动机启动时所处的唯一状态。计算总是从 $q_0$ 开始。
   • 6. $F \subseteq Q$ 是接受状态集:
   • 和FA一样，这是一个状态的子集。如果自动机在读取完所有输入后，它的某条计算路径停在了 $F$ 中的某个状态，那么该输入字符串就被接受。

在定义了PDA的静态结构之后，这一段开始定义它的动态行为——计算过程，以及什么是“接受”一个输入字符串。

1. “下推自动机 M 的计算方式如下”:
   • 这部分定义了PDA如何处理一个输入字符串 $w$。
2. “如果 $w$ 可以写成 $w=w_{1} w_{2} \cdots w_{m}$，其中每个 $w_{i} \in \Sigma_{\varepsilon}$”:
   • 这里对输入字符串 $w$ 进行了分解。重要的是，$w_i$ 可以是 $\Sigma$ 中的一个符号，也可以是空字符串 $\varepsilon$。
   • 这意味着PDA的计算过程被看作是一系列离散的“步骤”，总共 $m$ 步。在每一步 $i$，PDA消耗输入 $w_i$。如果 $w_i = \varepsilon$，则这一步是 $\varepsilon$-转移，输入磁头不移动。
3. “并且存在状态序列 $r_{0}, r_{1}, \ldots, r_{m} \in Q$ 和字符串 $s_{0}, s_{1}, \ldots, s_{m} \in \Gamma^{*}$”:
   • 这里引入了两个与计算步骤相对应的序列：
   • 状态序列 $r_0, r_1, \dots, r_m$: $r_i$ 是PDA在第 $i$ 步计算之后达到的状态。
   • 栈内容序列 $s_0, s_1, \dots, s_m$: $s_i$ 是一个字符串，代表PDA在第 $i$ 步计算之后，整个栈的内容（从栈顶到栈底）。$\Gamma^*$ 表示由栈字母表中的符号组成的所有可能字符串。
4. “满足以下三个条件，则它接受输入 $w$”:
   • “接受”的定义是：必须能找到这样一组序列（$w_i, r_i, s_i$），它们如同一个合法的计算日志，记录了从开始到结束的全过程，并满足下面三个条件。由于非确定性，可能存在很多不同的计算日志，只要其中至少有一条满足条件，就算接受。
5. “字符串 $s_{i}$ 表示 $M$ 在计算的接受分支上具有的栈内容序列”:
   • 这句话 уточняет, что мы ищем одну конкретную, "успешную" ветку вычислений среди всех возможных, порожденных недетерминизмом.

这是PDA接受一个字符串所需满足的三个核心条件，它们定义了什么是“合法的计算历史”。

条件1: $r_{0}=q_{0}$ 且 $s_{0}=\varepsilon$。

• $r_0 = q_0$: 计算序列的第一个状态 $r_0$ 必须是PDA定义的开始状态 $q_0$。这意味着计算必须从指定的起点开始。
• $s_0 = \varepsilon$: 计算序列的第一个栈内容 $s_0$ 必须是空字符串 $\varepsilon$。这意味着计算开始时，栈必须是空的。
• “此条件表示 M 以开始状态和空栈正确启动”: 这是对条件的清晰解释。它定义了计算的“初始配置”。

条件2: $\left(r_{i+1}, b\right) \in \delta\left(r_{i}, w_{i+1}, a\right)$，其中 $s_{i}=a t$ 和 $s_{i+1}=b t$ ...

• 这是最核心、最复杂的条件，它定义了计算的“转移合法性”。它描述了PDA如何从第 $i$ 步的配置 (r_i, s_i) 移动到第 $i+1$ 步的配置 (r_{i+1}, s_{i+1})。
• $s_i = at$:
• $s_i$ 是第 $i$ 步的栈内容。
• $a \in \Gamma_{\varepsilon}$ 是当时的栈顶符号。如果 $a=\varepsilon$，意味着我们不从栈中弹出任何东西。
• $t \in \Gamma^*$ 是栈中余下的部分（t for tail）。
• $s_{i+1} = bt$:
• $s_{i+1}$ 是第 $i+1$ 步的新栈内容。
• $b \in \Gamma_{\varepsilon}$ 是转移后新压入的符号。如果 $b=\varepsilon$，意味着我们不压入任何新东西。
• 关键: t 部分保持不变！这精确地模拟了栈操作：只在栈顶进行，栈的深层部分 t 不受影响。
• a 被 b 替换了。
• push Y: $a=\varepsilon, b=Y$。$s_i = t, s_{i+1} = Yt$。
• pop X: $a=X, b=\varepsilon$。$s_i = Xt, s_{i+1} = t$。
• replace X with Y: $a=X, b=Y$。$s_i = Xt, s_{i+1} = Yt$。
• $(r_{i+1}, b) \in \delta(r_i, w_{i+1}, a)$:
• 这句是说，我们观察到的状态变化（从 $r_i$ 到 $r_{i+1}$）和栈顶变化（从 $a$ 变为 $b$），必须是转移函数 $\delta$ 在给定当前状态 $r_i$ 和输入 $w_{i+1}$ 的情况下，所允许的一个合法操作。
• “此条件表示 M 根据状态、栈和下一个输入符号正确移动”: 这是对条件的完美总结。它保证了计算的每一步都遵循了PDA的规则手册 $\delta$。

条件3: $r_{m} \in F$。

• $r_m$: 这是计算序列的最后一个状态，也就是在处理完所有输入（包括所有$\varepsilon$-转移）后，PDA所处的状态。
• $F$: 接受状态集。
• $r_m \in F$: 最后一个状态必须是接受状态之一。
• “此条件表示在输入结束时出现接受状态”: 这是计算成功的最终判定标准。

这个例子给出了识别经典非正则语言 $\{0^n1^n \mid n \ge 0\}$ 的一个具体的、形式化的PDA定义。

1. 六元组的定义:
   • $Q=\left\{q_{1}, q_{2}, q_{3}, q_{4}\right\}$: 状态集包含四个状态。我们可以非正式地理解它们的作用：
   • $q_1$: 开始状态，准备开始处理字符串。
   • $q_2$: 正在读取和压栈 '0' 的阶段。
   • $q_3$: 正在读取和弹栈 '1' 的阶段。
   • $q_4$: 完成匹配，到达最终接受状态。
   • $\Sigma=\{0,1\}$: 输入字母表，很标准。
   • $\Gamma=\{0, \$\}$**: **栈字母表**。这里作者选择用**输入符号** '0' 直接作为**栈符号**来计数。'$' 是一个特殊的栈底**标记。
   • $q_1$: 开始状态被指定为 $q_1$。
   • $F=\left\{q_{1}, q_{4}\right\}$: 接受状态集包含两个状态。
   • $q_1 \in F$: 意味着如果输入是空字符串 $\varepsilon$ ($n=0$ 的情况)，自动机会停留在 $q_1$ 并直接接受。
   • $q_4 \in F$: 意味着对于 $n>0$ 的情况，成功匹配后会到达 $q_4$ 并接受。
2. $\delta$ (转移函数) 表格的解读:
   • 表格结构:
   • 行: 代表当前状态 ($q_1, q_2, q_3, q_4$)。
   • 列: 代表输入符号 (0, 1, $\varepsilon$) 和栈顶符号 (0, $, \varepsilon$) 的组合。这是一个二维化的表示，更易读。例如，第一大列 "0" 下面有三小列，分别对应栈顶是 '0', '$', '$\varepsilon$' 的情况。
   • 解读每一个非空条目:
   • **$\delta(q_1, \varepsilon, \varepsilon) = \{(q_2, \$)\}$** (原文表格中 $q_1$行, $\varepsilon$输入, $\varepsilon$栈顶列):
   • 含义: 在开始状态 $q_1$，不读任何输入，也不看栈顶（因为栈是空的），自动机可以进行一次 $\varepsilon$-转移。
   • 动作: 转移到状态 $q_2$，并压入 '$' 符号。
   • 目的: 这是初始化步骤。在开始处理0和1之前，先把栈底标记 '$' 放入**栈**中。然后进入处理0的**状态** $q_2$。
   • 注意: 表格的q1行, 0输入, ε栈顶是 `{(q2, $)}`。这是原文的笔误或一种不寻常的表示法。从逻辑上看，这应该是 $\delta(q_1, 0, \varepsilon)$ 或者 $\delta(q_1, \varepsilon, \varepsilon)$。从后面的状态图来看，它应该是 $\varepsilon, \varepsilon \to \
     $$ 之后再处理0。让我们按照逻辑来分析，假设在进入 $q_2$ 之后才开始读 '0'。更合理的解释是，表格第一行 `q1` 下的 `{(q2, $)}` 实际上是 $\delta(q_1, 0, \varepsilon)$，意味着读第一个0的时候顺便把栈底符号压进去。但通常是先压栈底。我们先按表格字面意思理解，但后面会看到状态图给出了更清晰的逻辑。**更正一下**，仔细看表格的列标题，第一大列是输入0，下面三小列是栈顶0, $, ε。所以q1行那个条目是 $\delta(q_1, 0, \varepsilon) = \{(q_2, 0\$)\}$，但它只写了 `{(q2, $)}`，可能省略了0。而状态图画的是 $\varepsilon,\varepsilon\to\ $$
     ，这与表格不完全对应。我们以表格为准，并对其进行最合理的解释。让我们重新审视表格，它可能是一种简写：
   • $\delta(q_1, \varepsilon, \varepsilon) = \{(q_2, \$)\}$: 这似乎是 (q1, ε, ε) 处的转移。
   • 但表格把它放在了 (q1, 0, ε) 下面。这很奇怪。让我们参考后面的状态图和常规做法：PDA通常会先做一个 $\varepsilon$-转移把 '$' **压栈**，然后进入一个新**状态**。或者在读第一个0的时候一起**压**。我们假设表格的意图是 `$\delta(q_1, \varepsilon, \varepsilon) = \{(q_2, \$)\}$。但是如果严格按照表格， $\delta(q_1, 0, \varepsilon) = \{(q_2, \$)\}$`，这表示读第一个0，然后把$压栈，这个0本身没有被压栈，这逻辑不通。所以我们采纳更合理的解释：有一个从 $q_1$ 到 $q_2$ 的 $\varepsilon, \varepsilon \to \$$ 转移，或者表格的 $q_2$ 行的 $\delta(q_2, 0, 0)$ 应该在 $q_1$ 状态就开始。
   • 让我们采用一个更符合逻辑的解读，这个PDA的设计可能如下: $q_1$是接受空字符串的。要处理非空字符串，它先`ε,ε -> $`转移到另一个状态（比如$q_{start'}$），然后从$q_{start'}$开始读0。这个表格可能简化了这个过程。
   • 最可能的解释: 表格的q1行 ε列下是空的， 0列ε栈顶下是 `{(q2, $)}`。这可能是指 $\delta(q_1, 0, \varepsilon)$，但是这样的话第一个0没有被计数。这与算法描述不符。
   • 让我们看 $q_2$ 的转移，这更清晰:
   • $\delta(q_2, 0, 0) = \{(q_2, 00)\}$: 这是笔误。应该是 {(q2, 0)}，即压入一个0。逻辑是：在 $q_2$ 状态（读0阶段），如果输入是'0'，栈顶也是'0'，那么就再压入一个'0'。这样栈就变成 00...。
   • $\delta(q_2, 0, \$) = \{(q_2, 0\$)\}$: 如果在 $q_2$ 状态，输入'0'，此时栈顶是栈底符号 $ (意味着这是第一个'0')，那么压入'0'。
   • 上面两条可以合并为 $\delta(q_2, 0, \text{any}) = \{(q_2, 0\text{any})\}$，即只要输入是0，就压栈0。表格的 {(q2, 0)} 应该是 push 0 的简写，即用0替换栈顶，再压一个0。s_i = at, s_{i+1} = bt。δ(q, in, a) = (p,b)。如果 a=0, b=00，那就是 s_i=0t, s_{i+1}=00t。这表示压入一个0。
   • $\delta(q_2, 1, 0) = \{(q_3, \varepsilon)\}$: 在 $q_2$ 状态，如果第一次看到输入 '1'，并且栈顶有一个 '0'，那么就弹栈 '0'（通过压入 $\varepsilon$ 实现），并转移到 $q_3$ 状态（读1阶段）。
   • $\delta(q_3, 1, 0) = \{(q_3, \varepsilon)\}$: 在 $q_3$ 状态（读1阶段），如果继续看到输入 '1'，并且栈顶有一个 '0'，那么就继续弹栈 '0'，并保持在 $q_3$。
   • $\delta(q_3, \varepsilon, \$) = \{(q_4, \varepsilon)\}$**: 在 $q_3$ **状态**，如果输入已经读完（通过 $\varepsilon$ **转移**判断），并且**栈**顶是**栈底**符号 `$（意味着所有的'0'都被'1'抵消了），那么就弹栈** $`，并转移到最终的**接受状态** $q_4$。
   • $q_4$: 这是一个“终点”状态，没有任何出边。

这一段介绍了PDA的另一种描述方法——状态图，它比形式化的六元组或表格更直观。

1. “我们还可以使用状态图来描述 PDA”:
   • 状态图（State Diagram）是一种图形化表示方法，在有限自动机中已经广泛使用。对于PDA，我们只需要对状态图的转移标签进行扩展即可。
2. “类似于用于描述有限自动机的状态图，并进行了修改以显示 PDA 在状态之间转换时如何使用其栈”:
   • 相似之处: 仍然用圆圈表示状态，用箭头表示转移，用一个指向开始状态的无源箭头表示起点，用双层圆圈表示接受状态。
   • 修改之处: 转移箭头上标记的不再仅仅是输入符号，而是一个更复杂的三元组，用来表示栈的操作。
3. “我们写‘$a, b \rightarrow c$’表示...”:
   • 这里定义了PDA状态图中转移标签的语法。
   • $a \in \Sigma_{\varepsilon}$: 输入。要消耗的输入符号（或者是 $\varepsilon$）。
   • $b \in \Gamma_{\varepsilon}$: 弹栈。转移前必须匹配的栈顶符号（或者是 $\varepsilon$）。
   • $c \in \Gamma_{\varepsilon}$: 压栈。转移后要压入栈顶的新符号（或者是 $\varepsilon$）。
   • 整个含义: 读入 $a$，看到栈顶是 $b$，就把它弹出，然后压入 $c$。这精确对应了条件2中的 $s_i=bt, s_{i+1}=ct$（这里原文用 $a,b,c$，我们用 $b,c$ 对应之前的 $a,b$ 来避免混淆）。如果 $s_i = B T$, $s_{i+1} = C T$，那么标签就是 input, B -> C。
4. “$a, b$ 和 $c$ 中的任何一个都可以是 $\varepsilon$”:
   • $a = \varepsilon$: $\varepsilon$-转移，不读输入，输入磁头不动。
   • $b = \varepsilon$: 纯压栈操作。不要求栈顶有特定符号，也不弹出任何东西，直接压入 $c$。标签: $a, \varepsilon \to c$。
   • $c = \varepsilon$: 纯弹栈操作。读入 $a$，匹配并弹出 $b$，不压入任何新东西。标签: $a, b \to \varepsilon$。
5. 分析图 2.15:
   • $q_1$: 开始状态，并且是接受状态（双圈）。这直接处理了 $n=0$ 的情况（输入 $\varepsilon$）。
   • $q_1 \to q_2$ 的转移 $\varepsilon, \varepsilon \to \$$:
   • 输入 $a=\varepsilon$: 不读输入。
   • 弹栈 $b=\varepsilon$: 不看栈顶，也不弹出。
   • 压栈 $c=\$$: 压入 栈底符号 '$'。
   • 含义: 这是初始化步骤，从 $q_1$ 无条件地、在不读任何输入的情况下，压入 '$' 并进入**状态** $q_2$。
   • $q_2$ 的自环 0, $\varepsilon \to 0$:
   • 输入 $a=0$: 读一个 '0'。
   • 弹栈 $b=\varepsilon$: 不弹出任何东西。
   • 压栈 $c=0$: 压入一个 '0'。
   • 含义: 每读到一个 '0'，就往栈里压入一个 '0'。这是计数阶段。
   • $q_2 \to q_3$ 的转移 1, $0 \to \varepsilon$:
   • 输入 $a=1$: 读一个 '1'。
   • 弹栈 $b=0$: 栈顶必须是 '0'，然后将其弹出。
   • 压栈 $c=\varepsilon$: 不压入任何东西。
   • 含义: 第一次读到 '1' 时，开始消耗栈里的 '0'，并进入匹配 '1' 的状态 $q_3$。
   • $q_3$ 的自环 1, $0 \to \varepsilon$:
   • 含义: 在 $q_3$ 状态，每继续读到一个 '1'，就继续消耗一个栈里的 '0'。
   • $q_3 \to q_4$ 的转移 $\varepsilon, \$ \to \varepsilon$:
   • 输入 $a=\varepsilon$: 不读输入（意味着所有 '1' 都读完了）。
   • 弹栈 $b=\$$: 栈顶必须是栈底符号 '$'（意味着所有 '0' 都被抵消了）。
   • 压栈 $c=\varepsilon$: 不压入任何东西。
   • 含义: 匹配成功后，清理栈，进入最终的接受状态 $q_4$。
   • $q_4$: 是接受状态（双圈）。

这一段解释了一个在PDA设计中非常常用且重要的技巧：如何模拟“测试栈是否为空”。

1. “PDA 的形式定义没有明确的机制允许 PDA 测试空栈”:
   • 回顾转移函数 $\delta(q, a, x)$。它的第三个输入参数 $x$ 是栈顶符号。如果栈是空的，那么就没有“栈顶符号”了。形式定义中没有一个特殊的输入来代表“栈为空”。
   • 我们只能匹配 $\Gamma$ 中的符号，或者用 $\varepsilon$ 来表示“不消耗栈顶符号”，但这不等于“测试到栈是空的”。
2. “这个 PDA 能够通过最初在栈上放置一个特殊符号 \$ 来达到同样的效果”:
   • 这里给出了解决方案：引入一个哨兵（Sentinel）或标记（Marker）。
   • $**$: 这个符号被选为栈底标记。它必须是栈字母表** $\Gamma$ 的一个成员。
   • 最初放置: 在PDA开始处理实际输入之前，第一步就是将 $` **压入**空**栈**。在图2.15中，这就是从 $q_1$ 到 $q_2$ 的 `$\varepsilon, \varepsilon \to \$$ 转移所做的事情。
3. “然后，如果它再次看到 \$，它就知道栈实际上是空的”:
   • 这里的“空”是指“除了我们的特殊标记$之外，其他所有工作符号都已经被弹出了”。
   • 在计算过程中，$ 会一直静静地待在栈底。我们会把其他符号（如'0'）压在它的上面。
   • 当我们弹出了所有工作符号后，$ 就会重新暴露在栈顶。
   • 因此，“栈顶是$”这个可检测的条件，就等价于“工作栈已空”这个我们想要知道的状态。
   • 在图2.15中，$q_3 \to q_4$ 的转移 $\varepsilon, \$ \to \varepsilon$` 就是一个典型的例子。这个**转移**只有在所有的'0'都被'1'抵消后，`$ 重新成为栈顶时才能触发。
4. “随后，当我们非正式地描述 PDA 时提及测试空栈，我们以相同的方式实现该过程”:
   • 这是一个约定。作者告诉我们，以后为了方便，可能会直接说“...然后测试栈是否为空...”。当我们看到这种非正式描述时，我们应该在脑海里自动将其翻译成“...通过检查栈顶是否为栈底标记$来实现...”。

这一段解释了PDA如何隐式地“测试输入是否结束”，与上一段解释如何“测试栈是否为空”相对应。

1. “类似地，PDA 无法明确测试是否已到达输入字符串的末尾”:
   • PDA的转移函数 $\delta(q, a, x)$ 中的输入符号 $a$ 只能是 $\Sigma$ 中的一个符号，或者是 $\varepsilon$。没有一个特殊的输入符号来代表“END OF INPUT”（输入结束）。
   • 自动机是“目光短浅”的，它在任何时候只能看到磁头下的那一个符号，它不知道后面还有多长。
2. “这个 PDA 能够达到这种效果，因为接受状态仅在机器位于输入末尾时才生效”:
   • 这里揭示了实现方法。这不是通过一个特殊的转移操作，而是通过“接受”的定义本身来实现的。
   • 回顾计算和接受的定义：一个字符串 $w$ 被接受，当且仅当存在一个计算序列 $w=w_1w_2...w_m$，使得在消耗完所有 $w_i$ 后，自动机到达一个接受状态 $r_m \in F$。
   • “消耗完所有 $w_i$” 就意味着“位于输入末尾”。
   • 所以，接受状态的检查这个动作，本身就发生在计算的终点，也就是输入结束的时刻。
3. “因此，从现在开始，我们假设 PDA 可以测试输入的末尾，并且我们知道我们可以以相同的方式实现它”:
   • 这又是一个约定，为了方便后续的非正式描述。
   • 当我们说“...直到输入末尾...”或者“...如果输入结束...”，我们不是指PDA有一个神奇的预知能力。
   • 我们的意思是，相关的转移（特别是那些导向最终接受状态的转移）应该被设计成在消耗完所有有意义的输入后，通过一系列 $\varepsilon$-转移来触发，而最终的接受检查是在整个计算序列的末端进行的。

这一段引入了一个更复杂的语言，并点出了识别这个语言的关键难点和所需要的核心技术——非确定性。

1. 语言定义:
   • $\left\{\mathrm{a}^{i} \mathrm{~b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0 \text { 且 } i=j \text { 或 } i=k\right\}$:
   • 字符串结构: 由三部分组成，一串'a'，跟着一串'b'，再跟着一串'c'。顺序是固定的 a...ab...bc...c。
   • $i, j, k \ge 0$: 'a', 'b', 'c' 的数量都可以是0。
   • 核心条件: $i=j$ 或 $i=k$: 'a'的数量必须等于'b'的数量，或者等于'c'的数量。两者满足其一即可。
2. 语言中的字符串示例:
   • aabc (i=2, j=1, k=1) -> 不属于，因为 $2 \ne 1$。
   • aabbc (i=2, j=2, k=1) -> 属于，因为 $i=j$。
   • aacc (i=2, j=0, k=2) -> 属于，因为 $i=k$。
   • abbc (i=1, j=2, k=1) -> 属于，因为 $i=k$。
   • abc (i=1, j=1, k=1) -> 属于，因为 $i=j$ (也满足 $i=k$)。
   • b (i=0, j=1, k=0) -> 属于，因为 $i=j=0$ (0个a和0个b是相等的)。严格来说，$i=0, j=1$不满足$i=j$。但如果$i=0$，那么 $i=k=0$ (假设k=0)或 $i=j=0$ (假设j=0) 是满足的。例如 $i=0, j=0, k=5$ 的 "ccccc" 是合法的。$i=0, j=1, k=0$ 的 "b" 不合法。$i=1,j=0,k=0$ 的 "a" 也不合法。
3. 非正式描述PDA策略:
   • 第一步: “首先读取并压栈 a”: 这和识别 $\{0^n1^n\}$ 类似。PDA需要将'a'的数量记录下来，而栈是完美的工具。每读一个'a'，就往栈里压入一个符号。
   • 第二步: “当 a 结束时...将它们与 b 或 c 匹配”: 当PDA开始看到'b'或'c'时，它需要用栈里存的'a'的数量来进行比较。每读一个'b'或'c'，就弹出一个之前存的'a'。
4. 难点: “机器事先不知道是与 b 还是与 c 匹配 a”:
   • 这是这个问题的核心。当PDA读完所有的'a'，栈里装满了代表'a'的符号，然后它看到了第一个非'a'符号。
   • 如果这个符号是'b'，PDA应该开始用'b'来消耗栈里的计数。
   • 如果这个符号是'c'（可能因为 $j=0$），PDA应该忽略所有的'b'，等待'c'出现，然后用'c'来消耗栈。
   • 问题在于，当它开始读'b'的时候，它无法预知后面的'c'的数量是否也和'a'相等。它必须做一个选择：是现在就开始用'b'匹配，还是跳过'b'，等待用'c'来匹配？
   • 一个确定性的PDA在此时会陷入困境，因为它必须做出一个唯一的选择，而它没有足够的信息来保证这个选择是正确的。
5. 解决方案: “非确定性在这里派上了用场”:
   • 非确定性允许PDA“两边下注”。当读完'a'之后，PDA可以非确定性地分裂成两条计算路径：
   • 路径1 (赌 $i=j$): 这条路径会假设'a'要和'b'匹配。它会开始用'b'来弹栈。如果'a'和'b'成功匹配完（栈空），它就高兴地忽略掉后面所有的'c'，然后接受。如果匹配失败，这条路就死亡。
   • 路径2 (赌 $i=k$): 这条路径会假设'a'要和'c'匹配。它会选择忽略掉所有'b'（不进行任何栈操作），然后等待'c'的出现。一旦看到'c'，它就开始用'c'来弹栈。如果'a'和'c'成功匹配完，就接受。如果匹配失败，这条路也死亡。
   • 只要输入的字符串满足 $i=j$ 或 $i=k$ 中的任何一个条件，那么对应的路径1或路径2中就至少会有一条能够成功走到接受状态。根据非确定性的接受定义，整个PDA就接受这个字符串。

这一段结合一个状态图，具体展示了如何利用非确定性来构建识别上一个例子中语言的PDA。

1. “PDA 利用其非确定性，可以猜测是与 b 还是与 c 匹配 a”: 再次强调核心策略。
2. “可以把机器想象成它的非确定性有两个分支...”: 提供了理解非确定性计算过程的心智模型：分支或并行宇宙。
3. 分析图 2.17 ($M_2$):
   • 初始部分 ($q_1 \to q_2$):
   • $q_1$: 开始状态，也是接受状态（处理i=j=k=0的空串，以及i=0的情况）。
   • $q_1 \to q_2$ 的 $\varepsilon, \varepsilon \to \$$ : 初始化，压入 栈底符号 $。
   • 读取 'a' 的部分 ($q_2$ 的自环):
   • $q_2$ 上的 a, $\varepsilon \to a$ : 每读一个'a'，就压入一个'a'到栈中。这是计数阶段。
   • 非确定性分裂点 ($q_2$ 的出边):
   • 当在状态 $q_2$ 读完所有'a'后，输入将是'b'或'c'。PDA通过两条从 $q_2$ 出发的 $\varepsilon$-转移来实现“猜测”。
   • $q_2 \to q_3$ 的转移 $\varepsilon, \varepsilon \to \varepsilon$: 这是通往“匹配b”分支的路径。
   • $q_2 \to q_5$ 的转移 $\varepsilon, \varepsilon \to \varepsilon$: 这是通往“匹配c”分支的路径。
   • 当PDA处于 $q_2$ 并且下一个输入不是'a'时，它可以在不消耗任何输入的情况下，非确定性地选择进入 $q_3$ 或 $q_5$。
   • 分支1: 匹配 a 和 b ($q_3, q_4$):
   • $q_3$ 上的 b, $a \to \varepsilon$ : 每读一个'b'，就消耗栈里的一个'a'。
   • $q_3 \to q_4$ 的 $\varepsilon, \$ \to \varepsilon$` : 当'b'读完，如果**栈**里只剩**栈底** `$ (说明 a, b 数量相等)，就进入 $q_4$。
   • $q_4$ 上的 c, $\varepsilon \to \varepsilon$ : 在 $q_4$ 状态，意味着 a 和 b 已经匹配成功。此时可以忽略后面所有的 'c'。
   • $q_4$ 是接受状态。所以如果能到达这里，说明 $i=j$ 满足。
   • 分支2: 匹配 a 和 c ($q_5, q_6, q_7$):
   • $q_5$ 上的 b, $\varepsilon \to \varepsilon$ : 这条路径的目标是匹配 a 和 c，所以它会忽略掉所有的 'b'。
   • $q_5 \to q_6$ 的 $\varepsilon, \varepsilon \to \varepsilon$ : 忽略完所有'b'之后，通过一个 $\varepsilon$-转移进入准备匹配'c'的状态 $q_6$。
   • $q_6$ 上的 c, $a \to \varepsilon$ : 每读一个'c'，就消耗栈里的一个'a'。
   • $q_6 \to q_7$ 的 $\varepsilon, \$ \to \varepsilon$` : 当'c'读完，如果**栈**里只剩**栈底** `$ (说明 a, c 数量相等)，就进入 $q_7$。
   • $q_7$ 是接受状态。所以如果能到达这里，说明 $i=k$ 满足。
4. “问题 2.27 要求您证明...”: 这是一个课后习题的提示，暗示这个语言是非确定性上下文无关语言的经典例子。

这个例子介绍了另一个经典的、需要非确定性的语言——偶数长度的回文串，并给出了其PDA的设计。

1. 语言定义:
   • $\left\{w w^{\mathcal{R}} \mid w \in\{0,1\}^{*}\right\}$:
   • $w \in \{0,1\}^*$: $w$ 是由 '0' 和 '1' 组成的任意字符串（包括空串）。
   • $w^R$: $w$ 的反转。如果 $w = w_1w_2...w_k$，那么 $w^R = w_k...w_2w_1$。
   • $ww^R$: 整个字符串由前半部分 $w$ 和后半部分 $w$ 的反转构成。这一定义确保了整个字符串是一个偶数长度的回文串。
   • 示例:
   • $w=011$, $w^R=110$ -> 字符串 "011110" 属于该语言。
   • $w=10$, $w^R=01$ -> 字符串 "1001" 属于该语言。
   • $w=\varepsilon$ -> 字符串 "$\varepsilon$" 属于该语言。
   • "101" 不属于，因为它是奇数长度。
   • "1011" 不属于，因为它不是回文。
2. 非正式描述PDA策略:
   • “首先将读取的符号压栈”: 这是前半部分 $w$ 的处理。PDA把 $w$ 的内容忠实地记录在栈上。因为栈是 LIFO 的，如果 $w=w_1w_2...w_k$ 被压栈，栈顶将是 $w_k$，然后是 $w_{k-1}$，以此类推。栈里的内容从上到下正好是 $w$ 的反转 $w^R$。
   • “在每一点，非确定性地猜测已到达字符串的中间”: 这是问题的核心难点和解决方案。字符串中没有像 # 这样的中点标记。因此，DPDA无法知道何时 $w$ 结束，$w^R$ 开始。NPDA则可以在读取每一个符号后都进行“猜测”。
   • “然后切换到每读取一个符号就弹栈，检查它们是否相同”: 这是后半部分 $w^R$ 的处理。PDA进入匹配模式。对于 $w^R$ 的第一个符号（即$w_k$），它应该和栈顶（也是$w_k$）匹配。对于 $w^R$ 的第二个符号（即$w_{k-1}$），它应该和新的栈顶（也是$w_{k-1}$）匹配，以此类推。
   • “如果它们总是相同的符号，并且栈在输入完成时同时清空，则接受”: 这是接受条件。所有符号都匹配，并且 $w$ 和 $w^R$ 的长度也一样（由栈是否清空来保证）。
3. 分析图 2.19 ($M_3$):
   • $q_1$: 开始状态和接受状态。接受空字符串 $\varepsilon$。
   • $q_1 \to q_2$ 的 $\varepsilon, \varepsilon \to \$$: 初始化，压入 栈底符号。
   • $q_2$ 的自环: 0, $\varepsilon \to 0$ 和 1, $\varepsilon \to 1$。
   • 含义: 在 $q_2$ 状态，不断读取 '0' 或 '1'，并将其压入栈中。这是在处理前半部分 $w$。
   • $q_2 \to q_3$ 的 $\varepsilon, \varepsilon \to \varepsilon$:
   • 含义: 这是非确定性的“猜测中点”转移。在 $q_2$ 的任何时候（读完一个符号后），PDA都可以选择不读输入，不操作栈，直接跳转到“匹配模式”状态 $q_3$。
   • $q_3$ 的自环: 0, $0 \to \varepsilon$ 和 1, $1 \to \varepsilon$。
   • 含义: 在 $q_3$ 状态，开始匹配后半部分 $w^R$。如果输入是'0'，栈顶也必须是'0'，匹配后弹栈。对'1'同理。如果输入和栈顶不匹配，则该计算路径死亡。
   • $q_3 \to q_4$ 的 $\varepsilon, \$ \to \varepsilon$:
   • 含义: 如果在 $q_3$ 状态，输入已经读完，并且栈中只剩栈底符号 $`，说明 $w$ 和 $w^R$ 完美匹配。此时**弹出** `$，进入最终的接受状态 $q_4$。
   • $q_4$: 接受状态。

这是一个结论性的陈述，并指引读者去思考相关的证明。

1. “问题 2.28 表明这种语言需要一个非确定性 PDA”:
   • 这明确地告诉我们，语言 $L = \{ww^R \mid w \in \{0,1\}^*\}$ 是一个非确定性上下文无关语言的实例。
   • “需要”意味着不存在任何一个确定性下推自动机（DPDA）能够识别这个语言。
   • 证明的思路（非正式）: 假设存在一个DPDA可以识别 $L$。那么对于形如 $0^n110^n$ 的字符串，DPDA在读取到某个 $0^k$ 时，必须确定性地决定是继续压栈还是开始弹栈。但是，无论它如何决策，我们总能构造出另一个字符串（比如 $0^{n+m}110^{n+m}$ 或改变后半部分），使得这个DPDA的确定性决策出错。它无法仅根据已看到的前缀来唯一确定中点的位置。
2. “$\square$”:
   • 这个符号通常在教科书和数学文献中表示“证明结束”或“示例结束”。这里它标记了例子2.18的结束。

这是“等价性”这一核心章节的开篇，它设定了本节的目标和路线图。

1. “在本节中，我们展示了上下文无关文法和下推自动机在能力上是等价的”:
   • 明确本节的核心主题：证明 CFG ~ PDA (在能力上等价)。
   • 这是计算理论中一个里程碑式的定理，它将两种看起来截然不同的模型——一个基于规则的生成模型（CFG）和一个基于机器的识别模型（PDA）——紧密地联系在了一起。
2. “两者都能够描述上下文无关语言的类”:
   • 这是对“能力等价”的另一种表述。上下文无关语言（CFL）这个大家族，既可以用CFG作为其“户口本”（生成所有成员），也可以用PDA作为其“门卫”（识别所有成员）。
3. “我们展示了如何将任何上下文无关文法转换为识别相同语言的下推自动机，反之亦然”:
   • 这揭示了证明等价性的方法：构造性证明。
   • 我们将要学习两个算法（或称“程序”）：
   • 算法1 (CFG -> PDA): 输入一个任意的CFG，输出一个等价的PDA。
   • 算法2 (PDA -> CFG): 输入一个任意的PDA，输出一个等价的CFG。
   • 因为我们可以进行双向的转换，所以证明了两者是等价的。
4. “回想一下，我们将上下文无关语言定义为可以用上下文无关文法描述的任何语言”:
   • 这是一个重要的定义回顾。CFL的“出生证明”是由CFG给出的。
   • 现在，我们要证明PDA也能为CFL提供一个完全等价的“身份证明”。
5. “我们的目标是以下定理”:
   • 预告了本节最终要证明的那个核心定理。

这是本节要证明的核心定理，以简洁的数学语言陈述出来。

1. “一种语言是上下文无关语言”:
   • 根据定义，这句话等价于“存在一个上下文无关文法（CFG）可以生成该语言”。
2. “当且仅当”:
   • 这是逻辑上的“等价”关系，英文是 "if and only if" (iff)。
   • 它意味着左右两个命题是互为充要条件的。
   • 命题A 当且仅当 命题B 等价于：
   • 如果A，则B (A是B的充分条件)
   • 如果B，则A (A是B的必要条件)
3. “某些下推自动机识别它”:
   • “某些”指的是“至少存在一个”。我们不需要所有的PDA都识别它，只要能找到一个就行。
   • 这句话是第二个命题。
4. 定理的两个证明方向:
   • 方向一 ("如果"部分, =>): 如果一个语言是上下文无关的，那么存在一个下推自动机识别它。
   • 已知: 存在一个CFG $G$ 生成语言 $L$。
   • 求证: 存在一个PDA $P$ 识别语言 $L$。
   • 方法: 我们需要一个通用的算法，能把任意CFG $G$ 转换为等价的PDA $P$。
   • 方向二 ("仅当"部分, <=): 如果存在一个下推自动机识别一个语言，那么该语言是上下文无关的。
   • 已知: 存在一个PDA $P$ 识别语言 $L$。
   • 求证: 存在一个CFG $G$ 生成语言 $L$。
   • 方法: 我们需要一个通用的算法，能把任意PDA $P$ 转换为等价的CFG $G$。

这一部分开始着手证明定理2.20的第一个方向。

1. “像往常一样，对于‘当且仅当’定理，我们需要证明两个方向”:
   • 再次强调证明策略，确保读者跟上逻辑。
2. “在这个定理中，两个方向都很有趣”:
   • 暗示两个方向的证明都有其精妙之处和教学价值，值得关注。
3. “首先，我们做更容易的前向”:
   • 作者选择从相对简单的一半开始，即证明 CFG => PDA。
   • 为什么这个方向“更容易”？因为用一个机器模型（PDA）去模拟一个基于规则的推导过程（CFG），在思路上比较直观。我们可以设计PDA的状态和栈操作来一步步地模拟文法的推导。反过来，用文法规则去描述一个机器（可能包含复杂循环和状态跳转）的所有行为，通常要困难得多。
4. “引理 2.21: 如果一种语言是上下文无关语言，那么某些下推自动机识别它。”:
   • 将要证明的第一个方向，被表述为一个引理（Lemma）。
   • 引理通常是一个“辅助定理”，它本身是一个需要被证明的命题，但其主要目的是作为证明一个更大定理（如此处的定理2.20）的垫脚石。
   • 这个引理陈述的正是“前向”的证明任务。

这一段是引理2.21的“证明思路”（Proof Idea）部分，它在给出严格的形式化构造之前，先用自然语言描述了核心的算法思想。

1. “设 A 为一个 CFL... 有一个生成它的 CFG, G。我们展示如何将 G 转换为等价的 PDA, P”:
   • 设定了证明的起点和目标。
   • 起点: 一个任意给定的上下文无关文法 $G$。
   • 目标: 构造一个下推自动机 $P$。
   • 要求: $P$ 接受的语言必须和 $G$ 生成的语言完全相同，即 $L(P) = L(G)$。
2. “PDA P 将通过...确定是否存在 w 的推导”:
   • 揭示了核心策略：让PDA $P$ 模拟文法 $G$ 的推导过程。
   • 推导 (Derivation): 从文法的开始变量 $S$ 开始，通过反复应用产生式规则，将变量替换为变量和终结符的字符串，直到最终得到一个只包含终结符的字符串。这个过程就是推导。
   • PDA的任务: 对于一个给定的输入字符串 $w$，PDA $P$ 需要做的就是，想办法看看是否存在一条从 $S$ 出发的推导路径，其最终结果恰好是 $w$。如果能找到这样一条路径，就接受 $w$。
3. “推导的每一步都产生一个变量和终结符的中间字符串”:
   • 例如: $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$。这里的 $S, aSb, aaSbb, aabb$ 都是（中间）字符串。
4. “我们设计 P 来确定...一系列替换是否可以从开始变量导向 w”:
   • PDA $P$ 要做的，本质上是一个“搜索”问题：在所有可能的推导路径中，搜索是否存在一条路径的终点是 $w$。
5. “困难之一是确定要进行哪些替换”:
   • 指出了模拟推导的难点。一个变量 A 可能有多条产生式规则，比如 $A \to \alpha | \beta$。在推导的某一步，如果遇到了变量 A，我们应该用 $\alpha$ 替换它，还是用 $\beta$ 替换它呢？我们没有足够的信息来做出确定性的选择。
6. “PDA 的非确定性允许它猜测正确替换的序列”:
   • 给出了解决方案。这又一次体现了非确定性的威力。
   • 当PDA需要替换一个变量 A 时，它不需要做出唯一的选择。相反，它会非确定性地“分裂”成多个分支，每个分支对应一条产生式规则。
   • 例如，如果 $A \to \alpha$ 和 $A \to \beta$ 都是合法的规则，PDA会分裂：
   • 分支1: 假设选择了 $A \to \alpha$，然后继续计算。
   • 分支2: 假设选择了 $A \to \beta$，然后继续计算。
   • 只要其中任何一个分支最终成功地推导出输入字符串 $w$，整个计算就算成功。

这一段解决了上文提出的技术难题：如何在只能访问栈顶的PDA上，存储和操作可能含有内部变量的中间推导字符串。

1. “在 PDA 上实现此策略需要一个额外的想法”: 点明需要一个巧妙的设计。
2. “简单地使用栈来存储每个中间字符串很诱人。然而，这不太奏效”:
   • 诱人的想法: 假设中间字符串是 aAbB。一个天真的想法是把 B, b, A, a 依次压入栈，这样栈从上到下就是 a, A, b, B。
   • 为什么不奏效: 如果我们要替换最左边的变量 A，我们需要先弹出 a，然后才能访问到 A。弹出 a 之后，我们还需要一个机制把它存到别处，等替换完 A 再把它放回去。这非常复杂，PDA没有这样的临时存储空间。PDA只能访问栈顶。
3. “PDA 只能访问栈顶部的符号，而这可能是一个终结符而不是一个变量”:
   • 以前面的例子 aAbB 为例，栈顶是 a（一个终结符）。PDA无法“跳过”a去处理下面的A。
4. “解决此问题的方法是只将中间字符串的一部分保留在栈上：从中间字符串中第一个变量开始的符号”:
   • 这是本节最核心、最精妙的设计思想。
   • PDA的栈里，永远不存放已经匹配过的终结符，也不存放在第一个变量之前的任何终结符。
   • 栈的内容 = 从推导出的中间字符串的“最左变量”开始，到字符串末尾的全部内容。
5. “在第一个变量之前出现的任何终结符都会立即与输入字符串中的符号匹配”:
   • 这是对上述思想的补充。如果推导出 aAbB，而最左变量是 A，那么 A 前面的 a 怎么办？
   • 答案是：不把它放进栈里。而是立刻用它去和输入字符串 $w$ 的当前符号进行匹配。如果匹配成功，就消耗掉这个输入符号，然后继续处理 AbB。如果匹配失败，这条计算路径就死亡。
6. 分析图 2.22:
   • 图示:
   • 输入带 (Input): 01...
   • PDA的栈 (Stack): 从上到下是 A, 1, A, 0, $。
   • 表示的中间字符串: 01A1A0。
   • 如何对应:
   • 输入带的指针已经越过了 "01"。这说明 "01" 已经被PDA处理并与推导出的终结符成功匹配了。
   • 中间字符串 01A1A0 中，最左边的变量是 A。
   • 根据规则，PDA的栈里应该存放从这个A开始到末尾的字符串，即 A1A0。
   • 为了方便压栈，通常是反过来压，所以栈从底向上是 $, 0, A, 1, A。栈顶是 A。
   • PDA的下一步操作:
   • PDA看到栈顶是变量 A。
   • 它会非确定性地选择一个 A 的产生式规则，比如 A -> t1 t2。
   • 然后它会弹出 A，并把 t1 t2 的反转 t2 t1 压入栈中。
   • 这样，新的栈顶就是 t1，正好是新推导出的字符串片段的第一个符号，PDA可以继续处理它了。

这一段将前面提出的CFG到PDA转换策略，总结成一个清晰的、三步走的非正式算法。

1. “1. 将标记符号 \$ 和开始变量放在栈上”:
   • 这是PDA的初始化步骤。
   • $: 栈底标记，用于判断栈何时被清空。
   • 开始变量 (通常是 S): 这是推导的起点。PDA的初始“待办事项”就是处理开始变量 S。
   • 栈内容将是 [S, $]（S在栈顶）。
2. “2. 永远重复以下步骤”:
   • 这是一个主循环，PDA会一直执行，直到接受或所有路径都拒绝。
3. “a. 如果栈顶是变量符号 A ...”:
   • 这是处理变量的规则。
   • 触发条件: 栈顶是一个变量。
   • 动作:
4. 非确定性选择: 查看文法 $G$ 中所有以 $A$ 为左侧的产生式规则，例如 $A \to \alpha_1, A \to \alpha_2, \dots$。
5. 替换: 对于每个规则 $A \to \alpha_i$，PDA都可能分裂出一个分支。在该分支中，它首先弹出 A，然后将 $\alpha_i$ 的反转形式压入栈中。例如，如果规则是 $A \to XYZ$，它就压入 Z，再压入 Y，再压入 X。
   • 这完全模拟了最左推导中的一步。
6. “b. 如果栈顶是终结符 a ...”:
   • 这是处理终结符的规则。
   • 触发条件: 栈顶是一个终结符。
   • 动作:
7. 读取输入: 查看输入带上磁头当前指向的符号。
8. 比较: 将输入符号与栈顶终结符 $a$ 进行比较。
9. 如果匹配: 太好了！弹出 $a$，并将输入磁头向右移动一格。循环继续。
10. 如果不匹配: 这条计算路径是错误的。PDA在该分支上失败并终止（拒绝）。
11. “c. 如果栈顶是符号 \$ ...”:
    • 这是计算成功的判断规则。
    • 触发条件: 栈顶是栈底标记 $。
    • 这意味着: 所有从开始变量 $S$ 推导出来的、需要匹配的符号（无论是变量还是终结符）都已经被成功处理掉了。
    • 动作:
12. 进入接受状态: PDA转移到一个特殊的接受状态。
13. 检查输入: 接受的最终条件是，此时此刻，输入字符串也必须被完全读取。如果输入带上还有剩余符号，那么即使栈空了，也意味着推导出的字符串比输入短，匹配失败，拒绝。如果输入和栈同时“清空”，则接受。

这一部分进入了引理2.21的正式证明，首先通过引入一个方便的“简写表示法”来简化后续的构造描述。

1. “我们现在给出...形式细节”: 表明从高层思路转向底层实现。
2. “为了使构造更清晰，我们使用转移函数的简写表示法”:
   • 标准的PDA每一步只能压入一个栈符号（或$\varepsilon$）。
   • 但在模拟CFG时，我们需要压入一个产生式右侧的整个字符串，比如 XYZ。
   • 为了方便描述，我们想有一个“宏指令”，能让我们说“一次性把 XYZ 压栈”。这个简写表示法就是这个宏指令。
3. “我们可以通过引入额外的状态来模拟此操作”:
   • 这里解释了这个“宏指令”如何用标准的PDA操作来实现。它不是PDA的新功能，只是一个语法糖。
   • 思想: 将一次性的多符号 压栈，分解成连续的、多次的单符号 压栈。
   • 如何实现:
   • 假设要压入 u = u1 u2 ... ul。
   • 第一步：执行原始的输入读取和弹栈，然后压入 ul (字符串的最后一个符号)，并进入一个临时的中间状态 $q_1$。
   • 第二步：从 $q_1$ 出发，进行一次 $\varepsilon$-转移，不读输入，不弹栈，只压入 u(l-1)，并进入下一个临时状态 $q_2$。
   • ...
   • 第 $l$ 步：从 $q_{l-1}$ 出发，进行 $\varepsilon$-转移，压入 u1 (字符串的第一个符号)，并进入最终的目标状态 $r$。
   • 这样，通过 $l-1$ 个中间状态和 $l$ 步转移，就实现了将整个字符串 u（以反转的顺序）压入栈中，并确保最终 u1 在栈顶。
4. 形式化描述和图2.23:
   • 公式: 精确地给出了上述 $l$ 步的转移函数设置。
   • $\delta(q, a, s)$ 包含 $(q_1, u_l)$: 这是第一步，处理输入 $a$ 和原栈顶 $s$，压入 u 的最后一个符号 u_l。
   • $\delta(q_{i}, \varepsilon, \varepsilon) = ...$: 后续的所有步骤都是 $\varepsilon$-转移，不看输入也不看栈，只是顺序地压入 u 的剩余部分。
   • 图2.23: 直观地画出了这个过程。对于简写 a, s -> xyz，它被分解成三步：
5. 从 q 到 q1: a, s -> z
6. 从 q1 到 q2: ε, ε -> y
7. 从 q2 到 r: ε, ε -> x
   • 最终，x 在栈顶，这正是我们想要的。
8. “我们使用符号 $(r, u) \in \delta(q, a, s)$ 来表示...”:
   • 正式定义了这个简写。以后我们看到 `$(r, u)` 出现在**转移函数**的输出**集合**中，就理解为“转移到**状态** $r$，并将整个**字符串** $u$ 压入栈中”。我们心里清楚，这背后是一连串的单符号 压栈操作。

这一部分给出了将CFG转换为PDA的正式构造算法。这个构造的PDA $P$ 只有三个主要状态，逻辑非常清晰。

1. 定义 $P$ 的组件:
   • 状态集 $Q$:
   • $
   • $q_{\text{loop}}$: 一个核心的“主循环”状态。所有的推导和匹配工作都在这个状态的自环上完成。
   • $q_{\text{accept}}$: 唯一的接受状态。
   • $E$: 一个附加的状态集合，用于实现上一段提到的“压入整个字符串”的简写。这些是幕后英雄，在我们的高层逻辑中是透明的。
   • 开始状态: $q_{\text{start}}$。
   • 接受状态集 F: $\{q_{\text{accept}}\}$。
2. 定义转移函数 $\delta$:
   • 初始化: $\delta\left(q_{\text {start }}, \boldsymbol{\varepsilon}, \boldsymbol{\varepsilon}\right)=\left\{\left(q_{\text {loop }}, S \$\right)\right\}$
   • 触发: 在开始状态 $q_{\text{start}}$，无条件地（输入$\varepsilon$，栈顶$\varepsilon$）。
   • 动作: 转移到主循环状态 $q_{\text{loop}}$，并（使用简写）将开始变量 $S$ 和栈底标记 $` **压入栈**中。由于是简写，实际是先**压**`$，再压S，所以栈变为 [S, $]。
   • 目的: 完美实现了非正式描述的步骤1。

• 主循环 - 情况 (a) 栈顶是变量:
• $\delta\left(q_{\text {loop }}, \boldsymbol{\varepsilon}, A\right)=\left\{\left(q_{\text {loop }}, w\right) \mid \text { 其中 } A \rightarrow w \text { 是 } G \text { 中的一条**规则** }\right\}$
• 触发: 在 $q_{\text{loop}}$ 状态，不读输入（$\varepsilon$），当栈顶是任何一个变量 $A$ 时。
• 动作: 非确定性地，对于每一条关于 $A$ 的产生式规则 $A \to w$，都存在一个转移：保持在 $q_{\text{loop}}$ 状态，弹出 $A$，并（使用简写）将字符串 $w$ 压入栈中。
• 目的: 实现了非正式描述的步骤2.a，即模拟推导。

• 主循环 - 情况 (b) 栈顶是终结符:
• $\delta\left(q_{\text {loop }}, a, a\right)=\left\{\left(q_{\text {loop }}, \varepsilon\right)\right\}$
• 触发: 在 $q_{\text{loop}}$ 状态，当输入符号 $a$ 和栈顶符号 $a$ 相同时。
• 动作: 保持在 $q_{\text{loop}}$ 状态，弹出 $a$（通过压入$\varepsilon$实现），输入磁头前进一格。
• 目的: 实现了非正式描述的步骤2.b，即匹配终结符。

• 主循环 - 情况 (c) 栈顶是栈底标记:
• $\delta\left(q_{\text {loop }}, \boldsymbol{\varepsilon}, \$\right)=\left\{\left(q_{\text {accept }}, \boldsymbol{\varepsilon}\right)\right\}$
• 触发: 在 $q_{\text{loop}}$ 状态，不读输入，当栈顶是栈底标记 $ 时。
• 动作: 转移到唯一的接受状态 $q_{\text{accept}}$，并弹出 $。
• 目的: 实现了非正式描述的步骤2.c，即成功结束计算。

1. 分析图 2.24:
   • 这个状态图完美地可视化了上述构造。
   • $q_{\text{start}} \to q_{\text{loop}}$: 初始化的 $\varepsilon, \varepsilon \to S\$` 转移。
   • $q_{\text{loop}}$ 的自环:
   • $\varepsilon, A \to w$ (for each rule A->w): 这是情况(a)，模拟推导。
   • $a, a \to \varepsilon$ (for each terminal a): 这是情况(b)，匹配终结符。
   • $q_{\text{loop}} \to q_{\text{accept}}$: 结束的 $\varepsilon, \$ \to \varepsilon$ 转移。