turing-machines - DPDA到图灵机？

Question

有没有办法将确定性下推自动机转换为图灵机？我想把堆栈放在磁带上输入之后，在它们之间加上“#”。但要正式证明它似乎是不可能的。

你有什么建议吗？有人已经这样做了吗？

谢谢

Answer 1

下推自动机只在一个方向上工作。那就是它不能回溯它的步骤或保持计数。
例如，如果你想要一种正式的语言：

L = {1^n+0^m | n>m, m>0}  

这里没有。的 1 大于否。的零。DPDA和图灵机
都可以解决这个问题。

但是，如果我们添加另一个条件，例如：

L = {1^n.0^m.1^n | n>m, m>0}

假设您知道如何在图灵机中解决上述问题，您就会明白如果不回溯输入磁带就无法解决。
因此，您无法使 PDA 像图灵机一样强大。
这是 Wiki 的链接，供您进一步了解：https ://en.wikipedia.org/wiki/Chomsky_hierarchy