下推自动机接受

有两种不同的方法可以定义 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}的 PDA

解答

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

在这里，在这个例子中，‘0’ 和 ‘1’ 的数量必须相同。

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

• 然后在状态q₂，如果我们遇到输入 0 并且顶部为空，我们将 0 推入堆栈。这可能会迭代。如果我们遇到输入 1 并且顶部是 0，我们将弹出此 0。

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

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

示例

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

解答

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