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'被接受。