context-free-grammar - 这个下推自动机 (PDA) 接受什么语言？

Question

明天考试，教授让我们知道一个问题:)。

在此图的上下文中，L 是 epsilon(空字符串)，Z0 是堆栈空符号。

我在确定有关语言生成的单词的一些规则方面取得了一些进展，但无法确定整个语言。

谢谢!

Answer 1

该 PDA 几乎不像乍一看那样具有不确定性……请考虑以下情况。

假设输入以 ab 开头.然后我们用空栈进入状态2，所以“L”规则不匹配，所以我们只处于状态2。

假设输入以 (a^n)b 开头对于 n > 1。然后我们使用 a^(n-1) 进入状态 2在堆栈上，“L”规则触发带我们回到状态 1 a^(n-2)在堆栈上。但是由于状态 2 中的堆栈是 a^(n-1) (并且 n>1)，状态 2 上的环回箭头无法匹配......所以再次，我们(实际上)仅处于一种状态:状态 1。

假设输入以 ba 开头.然后我们再次进入状态 2，堆栈为空，与情况 (1) 一样，“L”规则不匹配，因此我们仅处于状态 2。

最后，假设输入以 (b^n)a 开头对于 n > 1。然后我们使用 b^n 进入状态 2在堆栈上，所以“L”规则不会触发，我们只处于状态 2。

换句话说，任何时候“L”规则将 PDA 的“ fork ”创建为状态 1，它只会这样做，因为“a”在堆栈顶部......这意味着保持状态 2 的 fork 必须死在下一个输入符号上。因此，实际上这里没有不确定性，您可以对这个 PDA 进行建模，就好像它总是处于一种状态一样。

有了这个观察，我认为很容易看出@Nayuki 是正确的:这个 PDA 接受 a 是 b 两倍的任何字符串。

首先，证明当 PDA 处于状态 1 时，堆栈总是完全由 a 或完全由 b 组成(或为空)。当 PDA 处于状态 2 时，堆栈完全由 b 组成(或为空)。这是一个类似于上述四种情况的简单案例分析；例如“状态 1，堆栈 = a^n，下一个字符 b => 状态 1，堆栈 = a^(n-2)”。 (注意 n=0 或 n=1 的情况。)

想想每个 b作为“想要与 2 a s 合作”。状态 1，堆栈 = a^n表示 n a s正在等待合作伙伴。状态 1，堆栈 = b^n表示 n b s正在等待合作伙伴。状态 2，堆栈 = b^n表示一个 b与一位合伙人 a和 n b s还在等待合作伙伴。

证明我刚才写的是真的，结果如下。