好资源导航 » 文章资讯 » 什么是瞬时描述和旋转门符号？

什么是瞬时描述和旋转门符号？

2023-06-07 16:15:02 523

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

在哪里，

q是状态。

w是未消耗的输入。

s是堆栈内容。

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

旋转门符号

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

转换过程用转门符号“⊢”表示

⊢代表一招。

⊢符号描述了一系列移动。

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

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

问题：找出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'不被接受。