PDA的瞬时描述是什么？
瞬时描述被称为非正式符号，它解释了下推自动机(PDA)如何计算给定的输入字符串并决定接受或拒绝给定的字符串。
PDA涉及堆栈的状态和内容。
堆栈往往是PDA的重要组成部分之一。
因此，我们为描述用于字符串处理的PDA的连续配置做了一个方便的符号。
三重（q，w，γ）的PDA符号因子为
q是当前状态。
w是剩余的输入字母表。
γ是PDA堆栈的当前内容。
通常，最左边的符号表示堆栈γ的顶部和右端的底部。这种类型的三重符号称为下推自动机的瞬时描述或ID。
从一个瞬时描述到另一个瞬时描述的移动用符号“⊢”表示
所以，
(q0, aw, z0) ⊢ (q1, w, yz0)
是可能的当且仅当
δ(q0, a, z0) ϵ (q1, yz0).
示例
考虑下面给出的示例-
显示输入字符串w=“aabb”的PDA的ID或移动，其中，
M=({q0,q1,q2},{a,b},{a,b,Z0},δ,q0,Z0,{q2}),
其中δ定义如下-
δ(q0, a, Z0) = {(q0, aZ0)} Rule (1)
δ(q0, a, a) = {(q0, aa)} Rule (2)
δ(q0, b, a) = {(q1, λ)} Rule (3)
δ(q1, b, a) = {(q1, λ)} Rule (4)
δ(q1, λ, Z0) = {(q2, λ)} Rule (5)
δ(q0, λ, Z0) = {(q2, λ)} Rule (6)并且我们需要查明字符串w是否被PDA接受。
解决方案
字符串w=“aabb”的瞬时描述。解释如下-
(q0, aabb, Z0) |- (q0, abb, aZ0) based on Rule (1) |- (q0, bb, aaZ0) based on Rule (2) |- (q1, b, aZ0 based on Rule (3) |- (q1, λ, Z0) based on Rule (3) |- (q2, λ, λ) based on Rule (5)
因此，PDA达到了(q2,λ,λ)的配置，即PDA堆栈是空的，它已经达到了最终状态。所以字符串'w'被接受。