下推自动机接受



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

最终状态可接受性

在最终状态可接受性中,当 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}

示例

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

解答

PDA for L

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

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

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

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

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

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

示例

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

解答

PDA for L1

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

广告