queue - 队列自动机可以模拟任何下推自动机吗？

Question

我正在做一个理论作业，这个问题真的让我思考。问题是：证明任何下推自动机都可以由队列自动机模拟。现在，最初我认为这很简单，但后来我想到了 L = {WW^R | W = {a, b}*} （W^R 是 W 的倒数）这很容易以下推自动机的一般形式创建，但我想不出任何方法以一般形式队列自动机。我不认为我们可以为此设计一个（有限的）一般情况。我可能也想多了，因为我可能只是误解了模拟的含义。无论如何，我比问题更可能是错误的，但是对于我提到的情况，它是如何工作的？

感谢您提供的任何帮助！

Answer 1

有一个非常简单的技巧：

1）证明一个队列可以模拟一个完整的图灵机。简而言之，将图灵磁带放在队列上，用特殊标记缠绕在磁带的末端以及读取头上。（如果从那里不清楚，请查看 wiki 链接或发表评论）

2) 请注意，图灵机严格来说比 PDA 更强大，因此它必须能够模拟 PDA。