下推自动机介绍

PDA 的基本结构

下推自动机是一种以类似我们为正则文法设计 DFA 的方式实现上下文无关文法的方法。DFA 可以记住有限数量的信息，但 PDA 可以记住无限数量的信息。

基本上，下推自动机是 -

"有限状态机" + "一个栈"

下推自动机具有三个组成部分 -

• 输入带，
• 控制单元，以及
• 一个无限大小的栈。

栈指针扫描栈顶符号。

栈执行两个操作 -

• 压栈 - 在顶部添加一个新符号。

• 出栈 - 读取并删除顶部符号。

PDA 可能会也可能不会读取输入符号，但它必须在每次转换中读取栈顶。

PDA 可以正式描述为一个 7 元组 (Q, ∑, S, δ, q₀, I, F) -

• Q 是有限数量的状态

• ∑ 是输入字母表

• S 是栈符号

• δ 是转移函数：Q × (∑ ∪ {ε}) × S × Q × S*

• q₀ 是初始状态 (q₀ ∈ Q)

• I 是初始栈顶符号 (I ∈ S)

• F 是一个接受状态集 (F ∈ Q)

下图显示了 PDA 从状态 q₁ 到状态 q₂ 的转换，标记为 a,b → c -

这意味着在状态 q₁，如果我们遇到一个输入字符串 'a' 并且栈顶符号是 'b'，那么我们弹出 'b'，将 'c' 推入栈顶并移动到状态 q₂。

与 PDA 相关的术语

瞬时描述

PDA 的瞬时描述 (ID) 由一个三元组 (q, w, s) 表示，其中

• q 是状态

• w 是未消耗的输入

• s 是栈内容

旋转门符号

“旋转门”符号用于连接表示 PDA 一次或多次移动的 ID 对。转换过程由旋转门符号“⊢”表示。

考虑一个 PDA (Q, ∑, S, δ, q₀, I, F)。转换可以用以下旋转门符号数学表示 -

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

这意味着在从状态 p 到状态 q 进行转换时，输入符号 'a' 被消耗，并且栈顶 'T' 被新字符串 'α' 替换。

注意 - 如果我们想要 PDA 的零次或多次移动，我们必须为此使用符号 (⊢*)。