考虑到非确定性 PDA，根据定义，状态叠加是可能的。但是，非确定性 PDA 只有一个堆栈，无法同时处于多个状态。这怎么可能呢？

by 蒂埃里·梅斯 / 周二，07 2025一月 / 发表于网络安全, EITC/IS/CCTF 计算复杂性理论基础, 下推自动机, CFG和PDA的等效性

为了解决有关非确定性下推自动机 (PDA) 的问题以及单个堆栈状态叠加的明显悖论，必须考虑非确定性的基本原理和 PDA 的操作机制。

下推自动机是一种计算模型，它通过合并称为堆栈的辅助存储介质来扩展有限自动机的功能。该堆栈为自动机提供了存储无限量信息的能力，尽管是后进先出 (LIFO) 的方式，这对于识别上下文无关语言非常重要。非确定性下推自动机 (NPDA) 尤其增强了此模型，它允许给定状态和输入符号有多种可能的转换，类似于有限自动机中的非确定性概念。

PDA 中的非确定性概念与量子力学的叠加概念没有直接关系。相反，它指的是自动机同时探索多条计算路径的能力。这是通过允许自动机在可用转换中做出任意选择来实现的。当 NPDA 遇到选择点时，它可以“分支”成多条计算路径，每条路径代表不同的状态转换和堆栈操作序列。

然而，堆栈在每个计算路径中仍然是一个单一的实体。它不会同时存在于这些路径上的多个状态中。相反，每个计算分支都维护自己独立的堆栈版本。这种独立性对于 NPDA 正确地同时模拟多个潜在计算非常重要。当可视化 NPDA 的操作时，可以将其视为维护一个树状的计算结构，其中每个节点代表状态、输入位置和堆栈内容的唯一配置。

考虑一个旨在识别平衡括号语言的 NPDA。假设自动机处于已读取左括号的状态，必须决定是将其推送到堆栈还是在不推送的情况下转换到其他状态。以非确定性的方式，NPDA 可以同时“选择”两个选项，从而有效地创建两个计算分支。在一个分支中，堆栈包含左括号，而在另一个分支中则不包含。每个分支根据其初始选择独立进行，堆栈内容根据该分支中的特定操作顺序演变。

这种分支功能使 NPDA 能够并行探索有关输入字符串结构的多个假设。如果至少一个计算分支导致具有空堆栈的接受状态，则 NPDA 接受输入。这种非确定性分支是一个强大的功能，它使 NPDA 能够识别比确定性 PDA 更广泛的语言类别，特别是所有上下文无关语言。

通过检查非确定性下推自动机的正式定义，可以进一步阐明 PDA 中的非确定性概念。NPDA 通常定义为 7 元组：

$（Q，\Sigma，\Gamma，\delta，q_0，Z_0，F）$

其中：
– $Q$ 是一组有限的状态。
– $\西格玛$ 是输入字母。
– $\伽玛$ 是堆栈字母表。
– $\三角洲$ 是转换函数，它映射 $Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma$ 的有限子集 $Q \times \Gamma^*$ .
– $q_0$ 是初始状态。
– $Z_0$ 是初始堆栈符号。
– $F$ 是接受状态的集合。

过渡函数 $\三角洲$ 是 PDA 中非确定性的核心。它允许给定状态、输入符号和堆栈顶部符号的多种可能转换。这些转换可能涉及移动到新状态、使用输入符号以及通过推送或弹出符号来修改堆栈。 $\epsilon$ -转换（不消耗输入符号的转换）进一步增强了 NPDA 的灵活性，允许它们在不读取输入的情况下改变状态和操作堆栈。

为了说明这一点，请考虑一个旨在识别语言的简单 NPDA $L = \{a^nb^n|n\geq 0\}$ 。该语言由具有相等数量的 $a$ 随后是 $b$ NPDA 的运作方式如下：
1. 从初始状态开始 $q_0$ 带有初始堆栈符号 $Z_0$ .
2.对于每个 $a$ 从输入读取，它会推送一个 $X$ 进入堆栈，转换为状态 $q_1$ .
3. 遇到 $b$ ，它会弹出一个 $X$ 从堆栈中转换到状态 $q_2$ .
4. 如果在处理整个输入之后，NPDA 达到接受状态并且堆栈为空，则表示接受。