下推自动机(PDA)

• 下推自动机是一种在设计用于正则文法的 DFA 相同的方式来实现 CFG 的方法。DFA 可以记住有限数量的信息，而 PDA 可以记住无限数量的信息。
• 下推自动机只是一个用“外部堆栈内存”增强的 NFA。堆栈的添加用于为下推自动机提供后进先出的内存管理能力。下推自动机可以在堆栈上存储无限量的信息。它可以访问堆栈上有限数量的信息。PDA 可以将一个元素推入堆栈的顶部，并从堆栈的顶部弹出一个元素。要将一个元素读入堆栈，必须弹出顶部元素并丢失。
• PDA 比 FA 更强大。任何可以被 FA 接受的语言也可以被 PDA 接受。PDA 也接受一类甚至不能被 FA 接受的语言。因此，PDA 比 FA 优越得多。

PDA 组件

输入磁带：输入磁带被分成许多单元格或符号。输入头是只读的，只能从左向右移动，一次一个符号。

有限控制：有限控制有一些指针，它指向要读取的当前符号。

堆栈：堆栈是一种结构，我们只能从中推入和删除元素。它的大小是无限的。在 PDA 中，堆栈用于临时存储元素。

PDA 的形式定义

PDA 可以定义为 7 个组件的集合

Q：有限状态集

∑：输入集

Γ：一个堆栈符号，可以从堆栈中推入和弹出

q0：初始状态

Z：一个起始符号，在 Γ 中。

F：一个最终状态集

δ：用于从当前状态移动到下一个状态的映射函数。

瞬时描述 (ID)

ID 是 PDA 如何计算输入字符串并决定该字符串被接受或拒绝的非正式表示法。

瞬时描述是一个三元组 (q, w, α)，其中

q 描述当前状态。

w 描述剩余输入。

α 描述堆栈内容，顶部在左侧。

Turnstile 符号

⊢ 符号描述 turnstile 符号并表示一个移动。

⊢* 符号描述一系列移动。

例如：

(p, b, T) ⊢ (q, w, α)

在上面的示例中，在从状态 p 转移到 q 时，输入符号 'b' 被消耗，并且堆栈的顶部 'T' 由一个新字符串 α 表示。

示例 1

为接受语言 {aⁿb²ⁿ | n>=1} 设计一个 PDA。

解决方案：在这种语言中，n 个 a 后面应该有 2n 个 b。因此，我们将应用一个非常简单的逻辑，如果读取单个 'a'，我们将两个 a 推入堆栈。一旦我们读取 'b'，那么对于每一个 'b'，只有一个 'a' 应该从堆栈中弹出。

ID 可以构造如下

现在，当我们读取 b 时，我们将状态从 q0 更改为 q1 并开始弹出相应的 'a'。因此，

因此，这种弹出 'b' 的过程将重复进行，直到读取所有符号。请注意，弹出的动作只发生在状态 q1 中。

读取所有 b 后，所有相应的 a 都应该被弹出。因此，当我们读取 ε 作为输入符号时，堆栈中应该没有任何东西。因此，移动将是

其中

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

我们可以将 ID 总结如下

现在我们将模拟此 PDA，用于输入字符串 "aaabbbbbb"。

示例 2

为接受语言 {0ⁿ1^m0ⁿ | m, n>=1} 设计一个 PDA。

解决方案：在这个 PDA 中，n 个 0 后面跟着任意数量的 1，后面是 n 个 0。因此，设计这种 PDA 的逻辑如下

在遇到第一个 0 时，将所有 0 推入堆栈。然后，如果我们读取 1，就什么都不做。然后读取 0，并且在每次读取 0 时，从堆栈中弹出一个 0。

例如

这种情况可以用 ID 形式写成

现在我们将模拟此 PDA，用于输入字符串 "0011100"。