下推自动机简介

我们已经讨论过了 有限自动机 .但是有限自动机只能接受常规语言。 下推自动机是一种具有额外内存的有限自动机，称为堆栈，可帮助下推自动机识别上下文无关的语言。 下推自动机（PDA）可定义为：

• Q是一组状态
• ∑是输入符号的集合
• Γ是一组下推符号（可以从堆栈中推动和弹出）
• q0是初始状态
• Z是初始下推符号（最初出现在堆栈中）
• F是最终状态的集合
• δ是映射qx{∑的过渡函数∪ ∈} xΓ变成Q xΓ*。在给定状态下，PDA将读取输入符号和堆栈符号（堆栈顶部），并移动到新状态并更改堆栈的符号。

即时描述（ID） 瞬时描述（ID）是PDA如何“计算”输入字符串并决定接受或拒绝该字符串的非正式表示法。

ID是一个三元组（q，w，α），其中： 1.q是当前状态。 2.w是剩余的输入。 3.α是堆栈内容，位于左侧顶部。 旋转栅门符号 ⊢ 该标志被称为“旋转栅门符号”，代表 一招。 ⊢* 符号代表一系列动作。 例如-（p，b，T）⊢ （q，w，α） 这意味着，当从状态p转换到状态q时，输入符号“b”被消耗，堆栈顶部的“T”被新字符串“α”替换

例子： 定义{a语言的下推自动机 ^N b ⁿ |n>0} 解决方案： M=其中Q={q0，q1}和∑={a，b}和Γ={a，Z}和δ由下式给出：

δ（q0，a，Z）={（q0，AZ）} δ（q0，a，a）={（q0，AA）} δ（q0，b，A）={（q1，∈) } δ（q1，b，A）={（q1，∈) } δ（q1，∈, Z） （q1，∈) } 让我们看看这个自动机是如何为aaabbb工作的。

说明： 最初，自动机的状态是q0，堆栈上的符号是Z，输入是aaabbb，如第1行所示。读取“a”（第2行以粗体显示）时，状态将保持q0，并将符号a推送到堆栈上。在下一个“a”（如第3行所示）上，它将在堆栈上推送另一个符号a。读取3 a后，堆栈将为AAAZ，顶部为a。读取“b”后（如第5行所示），它将弹出A并移动到状态q1，堆栈将为AAZ。当读取所有b时，状态将为q1，堆栈将为Z。在第8行，输入符号’∈’ Z在堆栈上，它将弹出Z，堆栈将为空。这种类型的验收被称为 空栈验收。 注：

• 上述下推自动机本质上是确定性的，因为输入符号和堆栈符号上的状态只有一次移动。
• 非确定性下推自动机可以在输入符号和堆栈符号上从一个状态进行多次移动。
• 将非确定性下推自动机转换为确定性下推自动机并不总是可能的。
• 非确定性PDA的表达能力比确定性PDA的表达能力更强，因为NPDA接受了一些语言，但确定性PDA不接受这些语言，这将在下一篇文章中讨论。
• 下推自动机既可以通过空堆栈使用accepetance实现，也可以通过最终状态使用accepetance实现，并且可以将其中一个转换为另一个。

问题: 以下哪一对具有不同的表达能力？

A.确定性有限自动机（DFA）和非确定性有限自动机（NFA） B.确定性下推自动机（DPDA）和非确定性下推自动机（NPDA） C.确定性单磁带图灵机和非确定性单磁带图灵机 D.单磁带图灵机和多磁带图灵机

解决方案： 每个NFA都可以转换为DFA。所以，表达能力是一样的。如上所述，每个NPDA都不能转换为DPDA。所以，NPDA和DPDA的力量是不一样的。因此，选项（B）是正确的。 本文由Sonal Tuteja撰稿。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论