什么是瞬时描述和转向台符号？

下推自动机 (PDA) 的瞬时描述 (ID) 由三元组 (q, w, s) 表示。

其中：

• q 是状态。
• w 是未使用的输入。
• s 是堆栈内容。

ID 是 PDA 如何比较输入字符串并做出接受或拒绝该字符串的决定的非正式表示。

转向台符号

它用于连接表示 PDA 一次或多次移动的 ID 对。

转换过程用转向台符号“⊢”表示。

⊢ 表示一次移动。

⊢ 符号描述一系列移动。

示例

(P, b, T) ⊢ (q, w, a)

在从 P 到 q 进行转换时，消耗输入符号 'b'，并表示堆栈顶部 'T'。

考虑另一个示例，以了解更多关于 ID 和转向台符号的信息

问题：找出 PDA 输入字符串 w = "aaabb" 的 ID，并检查字符串是否被 PDA 接受？

解决方案：让我们看看字符串 w = "aaabb" 的瞬时描述

(q₀, aaabb, Z₀) |- (q₀, aabb, aZ₀) {基于转换规则 1}

|- (q₀, abb, aaZ₀) {基于转换规则 2}

|- (q₀, bb, aaaZ₀) {基于转换规则 2}

|- (q₁, b, aaZ₀) {基于转换规则 3}

|- (q₁, λ, aZ₀) {基于转换规则 3}

|- 没有定义移动。

因此，下推自动机最终在此移动处停止，并且字符串不被接受，因为输入字符串 w 已完成或输入带为空，但 PDA 堆栈不为空。

所以字符串 'w' 没有被接受。

Bhanu Priya

更新于：2021年6月16日

1K+ 次查看

启动您的 职业生涯

完成课程获得认证

开始