下推自动机如何知道如何读取回文？

Question

例如，PDA 如何知道如何读取 L = {a, b}* 中的回文？

接受 {a,b}* 回文的 PDA :

因此，根据我绘制的 PDA：

它如何知道字符串的前半部分何时位于最后的终端（字母表中的字母），并因此知道从状态 0 到状态 1（并且进一步知道 "pop" 个字母从堆栈向后，因此创建回文)?

Answer 1

这是一个非确定性下推自动机。您的问题的答案是它 猜测 并且可以假定猜对了。非确定性自动机接受字符串 w 如果 any 可能处理 w 的路径导致 w被录取了。

如果我们将接受定义为在接受状态下有一个空堆栈，那么上述 NPDA 可以接受的唯一方法是：

• 它在状态 q0
中将一些东西放到堆栈上
• 它最终猜测它需要读取字符串的后半部分
• 它读取它压入堆栈的内容，但在 q1

NPDA 制作了三个 "guesses"：

1. 它猜测字符串是偶数长度的回文串e/e，这里用e代替lambda
2. 当它猜测一个e/e时，它猜测字符串是一个奇数长度的回文，在两半之间有一个a，其中e被用来代替lambda
3. 它在猜测be/e时猜测字符串是一个奇数长度的回文，b在两半之间e/e，其中e被用来代替lambda

以上三个猜测中的每一个也是猜测字符串的前半部分，不包括可能的中间元素，已经被看到了。

这个猜测最终对任何回文都是正确的，而且除了回文之外的任何东西都不会正确，所以 NPDA 接受 PAL。