解释图灵机变体双栈下推自动机？

双栈下推自动机 (PDA) 包括以下因素：

  • 图灵机可以接受任何单栈 PDA 都无法接受的语言。

  • 通过添加额外的栈来增强下推自动机的功能。

  • 具有两个栈的 PDA 与图灵机具有相同的计算能力。

双栈 PDA 是一种计算模型，它基于下推自动机 (PDA) 和非确定性双栈 PDA 的泛化，而确定性双栈 PDA 等价于非确定性双栈 PDA。

双栈 PDA 的移动基于以下内容：

  • 有限控制的状态。

  • 读取的输入符号。

  • 每个栈的栈顶符号。

图灵机 (TM) 和双栈下推自动机 (双栈 PDA) 机的一些特性如下：

图灵机双栈 PDA 机
更改状态。更改状态。
在扫描的单元格中写入磁带符号。读取的输入符号。
将磁头向左或向右移动。用零个或多个栈符号的字符串替换每个栈的符号。

下图是 TM 变体双栈 PDA 机。

磁带的右半部分保存在一个栈上，左半部分保存在另一个栈上。

随着我们移动，我们从一个栈弹出字符并将它们压入另一个栈。

更新于：2021年6月16日

14K+ 浏览量

开启你的职业生涯

完成课程获得认证

开始学习
广告