Question

在这一章中，我们见到了两个新的计算能力的级别：DPDA 比DFA 和NFA 更强大，而NPDA 要比DPDA 更强大。能访问栈之后，看起来下推自动机比有限自动机要强大和复杂一些。

拥有栈的主要结果就是能识别某些有限自动机不能识别的语言了，如回文和平衡括号字符串。栈提供的无限存储使PDA 能在计算中记住任意数量的信息并在随后再次使用它。

与有限自动机不同，PDA 可以在没有任何输入的情况下无限循环，这虽然不是很有用，但是比较少见。DFA 只能通过处理输入字符来改变状态，而NFA 尽管可以自发地通过自由移动改变状态，但它只能在回到起点之前进行有限次数的自由移动。另一方面，PDA 可以保持在一个状态并不断地把字符推入栈中，永远也不会重复同样的配置。

在某种程度上，下推自动机还能控制自己。在规则和栈之间有一个反馈环——栈的内容影响机器应该遵守的规则，而按照某个规则执行也会影响栈的内容——这允许PDA 在栈中存储一些信息，这些信息可以影响它将来的执行。有限自动机依赖于类似的规则和当前状态之间的反馈，但这个反馈作用要小一些，因为当前状态在改变之后就完全被遗忘了，而把字符推入栈中可以把老的内容保存起来供以后使用。

因此PDA 确实是要强大一些，但它的限制是什么呢？即使我们只对看到的模式匹配应用感兴趣，下推自动机仍然严重受限于栈的工作方式。在栈顶字符之下的内容没有办法随机访问，因此如果机器想要读取埋在栈中间的一个字符，就得弹出这个字符上面所有的东西。一旦字符被弹出，就永远消失了。我们设计了一台PDA 以识别由等量的 a 和 b 组成的字符串，但没法修改它以识别由等量的三种字符组成的字符串（'abc'、'aabbcc'、'aaabbbccc'……），因为关于a 的数量的信息在对b 计数的过程中被破坏了。

撇开能用的向栈中推送字符的次数，栈的后进先出属性也会引起信息存储和获取的问题。PDA 能识别回文，但它不能识别'abab' 和'baaabaaa' 这样“双倍”的字符串，因为一旦信息被推入到栈中，就只能以相反的顺序处理了。

如果我们抛开识别字符串的特定问题，而把这些机器看成通用目的的计算机，就可以看到DFA、NFA 和PDA 还远远不够有用。首先，它们都没有像样的输出机制：它们通过进入接受状态表达成功，但不能输出哪怕一个字符（更不用说由字符组成的字符串了）来表示详细的结果。无法将信息发送回世界意味着它们连把两个数相加这样的简单算法都实现不了。而像有限自动机一样，PDA 有一个固定的程序；没有明显的方法构建出一台PDA 能以某种方式从输入读取一个程序然后运行。

所有这些缺点意味着我们需要一个更好的计算模型，去真正地研究计算机能干什么，而这正是下一章的内容。