Automata Theory 简明教程

Pushdown Automata Acceptance

可以用两种不同的方式定义 PDA 可接受性。

There are two different ways to define PDA acceptability.

Final State Acceptability

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

In final state acceptability, a PDA accepts a string when, after reading the entire string, the PDA is in a final state. From the starting state, we can make moves that end up in a final state with any stack values. The stack values are irrelevant as long as we end up in a final state.

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

For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the set of final states F is −

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

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

for any input stack string x.

Empty Stack Acceptability

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

Here a PDA accepts a string when, after reading the entire string, the PDA has emptied its stack.

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

For a PDA (Q, ∑, S, δ, q0, I, F), the language accepted by the empty stack is −

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

Example

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

Construct a PDA that accepts L = {0n 1n | n ≥ 0}

Solution

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

This language accepts L = {ε, 01, 0011, 000111, ……………………….. }

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

Here, in this example, the number of ‘a’ and ‘b’ have to be same.

Initially we put a special symbol ‘$’ into the empty stack.
Then at state q2, if we encounter input 0 and top is Null, we push 0 into stack. This may iterate. And if we encounter input 1 and top is 0, we pop this 0.
Then at state q3, if we encounter input 1 and top is 0, we pop this 0. This may also iterate. And if we encounter input 1 and top is 0, we pop the top element.
If the special symbol ‘$’ is encountered at top of the stack, it is popped out and it finally goes to the accepting state q4.

Example

构造一个 PDA 接受 L = { wwR | w = (a+b)* }

Construct a PDA that accepts L = { wwR | w = (a+b)* }

Solution

最初我们在空栈中添加一个特殊符号“$”。在状态 q2 中，正在读取 w 。在状态 w 中，每个 0 或 1 在与输入匹配时弹出。如果给出了任何其他输入，则 PDA 将进入死状态。当我们到达该特殊符号“$”时，我们进入接受状态 q3 。

Initially we put a special symbol ‘$’ into the empty stack. At state q2, the w is being read. In state q3, each 0 or 1 is popped when it matches the input. If any other input is given, the PDA will go to a dead state. When we reach that special symbol ‘$’, we go to the accepting state q4.