下推自动机接受

---

有两种不同的方法来定义 PDA 可接受性。

最终状态可接受性

在最终状态可接受性中，当读取整个字符串后，PDA 处于最终状态时，PDA 接受该字符串。从起始状态开始，我们可以进行移动，最终以任何堆栈值进入最终状态。只要我们最终处于最终状态，堆栈值就无关紧要。

对于 PDA (Q, Σ, S, δ, q ₀ , I, F)，最终状态 F 集接受的语言是 -

L(PDA) = {w | (q ₀ , w, I) ⊢* (q, ε, x), q ∈ F}

对于任何输入堆栈字符串x。

空栈可接受性

这里，当 PDA 读取整个字符串后清空其堆栈时，PDA 接受一个字符串。

对于 PDA (Q, Σ, S, δ, q ₀ , I, F)，空堆栈接受的语言是 -

L(PDA) = {w | (q ₀ , w, I) ⊢* (q, ε, ε), q ∈ Q}

例子

构造一个接受L = {0 ⁿ 1 ⁿ | n≥0}

解决方案

该语言接受 L = {ε, 01, 0011, 000111, ................................... }

这里，在此示例中， “a”和“b”的数量必须相同。

• 最初，我们将一个特殊符号“$”放入空堆栈中。

• 然后在状态q ₂，如果我们遇到输入 0 并且 top 为 Null，我们将 0 压入堆栈。这可能会迭代。如果我们遇到输入 1 并且 top 是 0，我们就会弹出这个 0。

• 然后在状态q ₃，如果我们遇到输入 1 并且 top 是 0，我们弹出这个 0。这也可能会迭代。如果我们遇到输入 1 并且 top 为 0，我们就会弹出顶部元素。

• 如果在栈顶遇到特殊符号“$”，则将其弹出并最终进入接受状态 q ₄。

例子

构造一个接受 L = { ww ^R | w = (a+b)* }

解决方案

最初，我们将一个特殊符号“$”放入空堆栈中。在状态q ₂，正在读取w 。在状态q ₃中，当与输入匹配时，每个 0 或 1 都会被弹出。如果给出任何其他输入，PDA 将进入死机状态。当我们到达特殊符号“$”时，我们进入接受状态q ₄。