隊列自動機可以模擬任何下推自動機？

Question

我正在研究理論任務，這個問題真的讓我思考。問題是：顯示任何push-down自動機都可以用隊列自動機來模擬。現在，最初我認爲這將是直截了當的，但後來我想到了L = {WW^R | W = {a，b} *}（W^R是W的倒數）這很容易在下推自動機的一般形式中創建，但我不能想到以任何方式來完成它的一般形式一個隊列自動機。我不認爲我們可以爲此設計一個（有限的）一般情況。我可能也在想它，因爲我可能會誤解什麼是模擬手段。無論如何，我比問題更可能是錯誤的，但對於我提到的情況，它是如何工作的？

感謝您提供的任何幫助！

Answer 1

有一個把戲做到這一點倒也乾脆：

1）表明，隊列can simulate a full Turing Machine。簡而言之，將Turing膠帶放在隊列中，用磁帶末端和讀取頭的特殊標記纏繞。 （如果從那裏不清楚，請看維基鏈接或留下評論）

2）請注意，圖靈機比PDA更強大，所以它必須能夠模擬PDA。