Automata Theory 简明教程

在最终状态可接受性中，当读取完整个字符串后，如果 PDA 处于最终状态，则 PDA 接受一个字符串。从开始状态，我们可以采取最终停留在最终状态的步骤，而无论栈值是什么。只要我们最终处于最终状态，那么栈值就无关紧要。

对于 PDA (Q, ∑, S, δ, q0, I, F)，结束状态 F 集合接受的语言为 −

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

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

此处 PDA 在读取完整个字符串后，如果 PDA 清空了栈，则接受一个字符串。

对于 PDA (Q, ∑, S, δ, q0, I, F)，空栈接受的语言为 −

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