下推自动机接受

有两种不同的方法来定义 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 ≥ 的 PDA 0

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

在此示例中，'a' 和 'b' 的数量必须相同。

最初，我们将特殊符号 '$' 放入空堆栈中。
然后在状态 q₂ 下，如果我们遇到输入 0 且顶部为 Null，我们将 0 推送到堆栈中。这可能会迭代。如果我们遇到输入 1 并且顶部为 0，我们将弹出这个 0。
然后在状态 q₃，如果我们遇到输入 1 并且顶部为 0，我们将弹出这个 0。这也可能迭代。如果我们遇到输入 1 并且顶部为 0，我们将弹出顶部元素。
如果在堆栈顶部遇到特殊符号"$"，则将其弹出并最终进入接受状态 q₄。

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

解决方案

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