Palindrones下推自動機

Question

所以，我發現這個PDA接受語言{0,1} * palindromes。

不過，我不理解它如何能接受 '1' 或 '0'。

在B它可以讀取1或0並將相同的符號推入堆棧，然後轉至C。然而，一旦它出現在C中，它無處可去，需要讀取另一個符號才能在堆棧中達到$。

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

我在想，爲了接受一個符號，我們需要從B到D =>1,$->ε | 0,$->ε的轉換。

我是否正確？

謝謝:)

Answer 1

你說得對。這PDA不會接受0或1（或者更一般地說，任何奇數長度迴文 - 你知道爲什麼嗎？）

爲了解決這個問題，我建議將這些轉變從B到C：

0，＆epsilon; ＆右箭頭; ＆小量;

1，＆epsilon; ＆右箭頭; ＆小量;

這些轉換基本上讓你消費一個字符「免費」。如果你選擇中間字符並且字符串是迴文，那太棒了！然後你會接受。如果你選錯了字符或者字符串不是迴文，你將永遠不會通過狀態C和D而不會自動死機。