具有两个堆栈的PDA可以接受RE语言吗？

Question

所以，我很难弄清楚图灵机不会停止的字符串的确切含义。我读过某处图灵机等效于具有2个堆栈的确定性自动机。但是具有2个堆栈的确定性自动机将如何接受一个不会停止的字符串，而对于任何有限的字符串来说，它都被确定要停止...我错过了什么吗？

Answer 1

具有两个堆栈的PDA等效于图灵机。为了显示TM至少与两层PDA一样强大，我们可以使用一个事实，即TM与两带TM一样强大。在两带TM中，我们可以限制磁带的使用以模拟它们的堆栈。因此，TM当然可以执行两栈PDA可以执行的操作。

[显示具有两个堆栈的PDA至少与两个堆栈的TM一样强大，但要复杂一点，但基本上，您的想法是，您可以使用两个堆栈模拟一个磁带，如下所示：

1. 调用一个堆栈L，另一个调用R
2. L的内容代表磁带头左侧的所有内容（包括当前符号）
3. R的内容代表磁带头右边的所有内容
4. 要覆盖当前符号：从L弹出并推到L
5. 要在磁带中向左移动：从L弹出并推到R
6. 要在磁带中向右移动：从R弹出并推到L

因此，我们可以左右移动并覆盖符号。这使我们可以模拟磁带，这是TM可以做的所有工作。