下推自动机简介

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 移动，我们必须使用符号 (⊢*)。