{a^nb^m | 的 PDA n<=m<=2n}

Question

有人可以帮我设计 PDA 吗？n<=m<=2n}。你能设计一个并附上解释吗？

Answer 1

这里的想法是这样的：读取每个 a 并将每个 a 的符号压入堆栈。然后，当您开始读取 b 时，在每一步中，不确定地选择是读取单个 b 并弹出一个堆栈符号，还是读取两个 b 并弹出一个堆栈符号。然后，如果输入耗尽且堆栈为空，则让 PDA 接受。

• 如果你总是选择为每个 b 读取弹出一个堆栈符号，那么你会得到 m = n
• 如果你总是选择为每对 b 读取弹出一个堆栈符号，那么你会得到 m = 2n
• 如果你有时选择读一个 b，有时读两个，那么你最终会得到 n < m < 2n；n < m 因为有时你读到的 b 比你拥有的堆栈符号还要多， m < 2n 因为有时你只读了一个 b 并从堆栈中弹出

如果至少一条路径最终接受，则 NPDA 接受；因此，只要某种猜测模式为每个堆栈符号读取一个或两个 b 获得正确的 m 值，该字符串就会被接受。应该清楚的是，对于任何满足 n <= m <= 2n 的 m 值，线性系统都有一个解：

x + 2y = m
x + y = n

这里，x 是 NPDA 应该猜测它读取一个 b 的次数，y 是 NPDA 应该猜测它读取两个 b 的次数。我们可以从第一个减去第二个：

y = m - n

因为 y 必须非负，所以我们得到第一个条件，n <= m。将其代入第二个起源方程得出：

    x + m - n = n
<=> x = 2n - m

同样，因为 x 必须是非负数，所以这给出了我们的第二个条件，m <= 2n。