context-free-grammar - Palindrones 的下推自动机

Question

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

但是，我无法理解它如何接受“1”或“0”。

在B其中可以读取 1 或 0 并将相同的符号推入堆栈，然后转到C. 但是，一旦它进入C，它就无处可去，因为要到达堆栈中的 $ 另一个符号需要被读取。

有人可以解释它是如何工作的吗？

我在想，为了接受单个符号，我们需要从Bto D=>转换1,$->ε | 0,$->ε。

我会是正确的吗？

谢谢 ：）

Answer 1

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

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

0, ε → ε

1, ε → ε

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