回文的下推自动机

Question

所以我发现这个 PDA 可以接受语言 {0,1}* 中的回文。

但是，我不明白它怎么会接受“1”或“0”。

在B中，它可以读取1或0并将相同的符号压入堆栈，然后转到C。然而，一旦它进入 C，它就无处可去，无法到达堆栈中的 $，需要读取另一个符号。

谁能解释一下它是如何工作的？

我在想，为了接受单个符号，我们需要从 B 到 D => 1,$->ε | 0,$->ε.

我是对的吗？

谢谢:)

Answer 1

你是对的。此 PDA 不接受 0 或 1（或者，更一般地说，任何奇数长度的回文 - 你知道为什么吗？）

要解决此问题，我建议添加从 B 到 C 的这些转换：

0, ε → ε

1, ε → ε

这些转换本质上让你消耗一个字符 "for free." 如果你选择中间字符并且字符串是回文，那就太好了！那你就会接受。如果你选择了错误的字符或字符串不是回文，你将永远无法通过状态 C 和 D 而不自动机死亡。