PDA 接受

一种语言可以通过下推自动机使用两种方法来接受

1. 通过最终状态接受： 如果 PDA 在读取整个输入后以零个或多个移动进入任何最终状态，则称 PDA 通过最终状态接受其输入。

设 P =(Q, ∑, Γ, δ, q0, Z, F) 是一个 PDA。最终状态可接受的语言可以定义为

2. 通过空栈接受： 在从某个 PDA 的初始配置读取输入字符串时，PDA 的栈变为空。

设 P =(Q, ∑, Γ, δ, q0, Z, F) 是一个 PDA。空栈可接受的语言可以定义为

通过最终状态接受和空栈接受的等价性

• 如果对于某个 PDA P1，L = N(P1)，则存在一个 PDA P2，使得 L = L(P2)。这意味着空栈 PDA 接受的语言也将被最终状态 PDA 接受。
• 如果对于某个 PDA P1，存在一种语言 L = L (P1)，则存在一个 PDA P2，使得 L = N(P2)。这意味着最终状态 PDA 接受的语言也可以被空栈 PDA 接受。

示例

构造一个 PDA，它通过空栈接受 {0, 1} 上的语言 L，该语言 L 接受所有 0 和 1 的字符串，其中 0 的数量是 1 的两倍。

解决方案

设计此 PDA 有两个部分

• 如果 1 出现在任何 0 之前
• 如果 0 出现在任何 1 之前。

我们将设计第一部分，即 1 出现在 0 之前。逻辑是读取单个 1 并将两个 1 推入栈中。此后，在读取两个 0 时，从栈中弹出两个 1。δ 可以是

现在，考虑第二部分，即如果 0 出现在 1 之前。逻辑是读取第一个 0，将其推入栈中，并将状态从 q0 更改为 q1。[请注意，状态 q1 表示已读取第一个 0，但尚未读取第二个 0]。

在 q1 中，如果遇到 1，则弹出 0。在 q1 中，如果读取 0，则只需读取第二个 0 并继续前进。δ 将是

现在，总结给定 L 的完整 PDA 是