automata - 为 L={a^mb^n 其中 n<=m<=2n} 构造一个下推自动机？

Question

我想了解下推自动机的构造L={a^nb^m where n<=m<=2n}？我在堆栈上发现了这个问题。

这是我理解的答案所说的：

策略如下：我们可以很容易地制作一个接受 a^nb^n 的 PDA，我们也可以很容易地制作一个接受 a^nb^2n 的 PDA。我们的语言是这些语言的超集，它也接受 n 到 2n 之间的任何 b 数。我们可以利用非确定性来实现这一点，如下所示：对于我们放入堆栈的每个 a，我们可以在弹出 a 之前不确定地决定是消耗一个还是两个 b。如果我们的 NPDA 选择每次消耗一个，我们得到 a^nb^n。如果它选择每次消耗两个，我们得到 a^nb^2n。如果它选择两者中的一些，我们会在这些极端之间得到一些 b。只有当我们用空堆栈耗尽输入时，我们才会接受。

现在，我稍微改变了问题（交换了 a 和 b 的幂）。现在的语言是L={a^m b^n where n<=m<=2n}？如果权力互换，这种策略现在将如何变化？

标签： automatacomputation-theorypushdown-automaton

Answer 1

我们可以利用非确定性来实现这一点，如下所示：对于我们放入堆栈的每个 a，我们可以在弹出 a 之前不确定地决定是消耗一个还是两个 b。

只需在这句话中交换a和b，您就应该得到答案。

提示：不是将a放入堆栈，而是放入b，然后在弹出之前“消耗”一两个a 。