4

PDA接受哪些类型的语言，其中堆栈大小限制为 20 个项目？

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

4

1 回答 1

8

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

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

  2. 拿任何一个DFA，你都可以把它变成一个等效的PDA-20。只需不使用堆栈，您就有了一个接受与 DFA 相同语言的 PDA-20。

为了说明证明的第一部分，考虑一个具有状态 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。

于 2012-01-13T18:10:30.980 回答