1

2 堆栈 PDA 和多磁带图灵机的优点是什么？

2 堆栈：可以像图灵机一样工作，使用一个堆栈作为左侧磁带，一个作为右侧磁带可以获取上下文感知数据

2 Tape：分离输入和计算

还有吗？

4

2 回答 2

2

一个 2 栈的 PDA 不仅可以像图灵机一样工作，它在功能上也等同于图灵机。这个关于 CS 堆栈交换的答案更详细。

这篇维基百科文章解释说，多带图灵机始终可以由单个带图灵机表示，因此无法计算单个带图灵机无法计算的任何内容。拥有多个磁带的优势在于多磁带机器会更快。

于 2013-05-14T14:30:46.250 回答
0

配对这个答案，

首先，图灵机承认的语言类别不是上下文敏感的，它是递归可枚举的（上下文敏感是您从直接制作的自动机中获得的语​​言类别）。

第二部分，考虑到我们调整了问题，是的，双栈 PDA 与 TM 一样强大。相信我们正在使用的 TM 模型稍微简单一些，该模型具有仅在一个方向上不间断的磁带（尽管两个方向并不难，并且等效）。

要查看相等性，只需将第一个堆栈视为流行位置左侧的磁带内容，将第二个视为右侧的内容。首先在两个堆栈上压入正常的“堆栈底部”标记，然后我们可以通过从右侧堆栈弹出并向左压入来向右移动，反之亦然向左移动来模拟 TM。如果我们击中左侧堆栈的底部，我们会做出相应的行为（暂停并拒绝，或留在原地，取决于模型），如果我们击中右侧堆栈的底部，我们只需将一个空白符号压入左侧。

另一种方式的关系应该更加明显，即我们可以模拟一个带有 TM 的两栈 PDA。

你可以这么说，Turing machine tape is infinite in one direction, extending indefinitely to the right. We use one stack to represent the tape content on the finite portion of the tape to the left of the head and another to represent the content of the finite non-blank portion of the tape to the right of the head. The two-stack PDA resembles a move of the TM by suitably pushing and leaping the two stacks。

于 2017-12-10T12:54:26.473 回答