state-machine - 堆栈大小受限的 PDA 接受哪些类型的语言？

Question

PDA 接受什么类型的语言其中堆栈大小限制为，比如说 20 个项目？

在我看来它仍然应该是 CFL ，因为有临时内存要存储。

Answer 1

一个堆栈限制为包含 20 个项目的 PDA 相当于一个 DFA。这是证据。

拿任何 PDA-20，你都可以把它变成一个等效的 DFA。假设堆栈字母 S，其中 |S| = N。你还有栈底符号Z。我们想象一个额外的符号，-，我们也可以在栈上有，它代表“未使用”。堆栈现在等价于 x = -* S* Z 形式的字符串，其中 |x| = 20，在所有情况下。压入堆栈包括替换出现的 -，而弹出包括以 LIFO 方式用 - 替换其他符号。对于任何 PDA-20，现在有 (N+2)^20 种可能的堆栈配置。要构建 DFA，只需通过这个因子复制 DFA 的每个状态，并让 DFA 状态的转换反射(reflect)堆栈的新配置。这样，包含在 PDA-20 中堆栈配置中的信息包含在 DFA 的当前状态中。

使用任何 DFA，您都可以将其制成等效的 PDA-20。只需不要使用堆栈，您就有一个 PDA-20，它接受与 DFA 相同的语言。

为了说明证明的第一部分，请考虑具有状态 A、B、C、...、Z 和许多转换的 PDA-5。假设输入字母表是 {0, 1}。然后有 2^5 = 32 种不同的堆栈配置。与此 PDA-5 等效的 DFA 可能具有状态 A1, B1, ..., Z1, A2, B2, ..., Z2, ..., A32, B32, ..., Z32，尽管它将具有与原始转换次数相同。如果原始 PDA-5 中的转换会将堆栈从状态 R 的配置 #2 带到配置 #17，并将机器带到状态 F，则 DFA 将从状态 R2 转到状态 F17。