确定性下推自动机与非确定性下推自动机

Question

你如何证明 a) 确定性下推自动机 (DPDA) 比有限自动机更强大而比非确定性下推自动机更弱？

Answer 1

(1) 首先，证明任何可以被有限自动机接受的语言也可以被确定性下推自动机接受。回想一下，有限自动机接受的任何语言都被确定性有限自动机接受，并且确定性下推自动机可以简单地通过对其堆栈不做任何有趣的事情来模拟确定性有限自动机。接下来，证明有一种非常规语言被 DPDA 接受。 0^n 1^n 是一个很好的候选者。使用抽取引理或 Myhill-Nerode 定理证明这种语言是非常规的，然后显示压入 0 然后切换到弹出 1 的 DPDA。

(2) 首先，请注意 NPDA 可以接受 DPDA 接受的任何语言，因为所有 DPDA 也是碰巧不使用不确定性的 NPDA。接下来，找到一种有 NPDA 但没有 DPDA 的语言。字母表 {0, 1} 上的偶数长度回文可能有效。为此有一个简单的 NPDA，它不确定地猜测输入的前半部分何时被读取并从推送切换到弹出。证明没有 DPDA 更具挑战性。也许你可以这样争论：假设有一个 DPDA。然后，在 DPDA 的任何配置中，只有一个转换是可能的。如果字符串 w 导致 DPDA 中的接受状态并清空堆栈，则 x00 可能导致接受或非接受状态（因为 x00 可能是也可能不是偶数长度回文）。但是，这是矛盾的，所以我们的 DPDA 不存在。顺便说一句，同样的论点对 NPDAs 来说是失败的，因为可以有多个路径，所以一个失败的选择没有任何意义。