产生字符串翻转和反转的下推自动机

Question

字母表：0, 1

考虑翻转，翻转每个字符：0 -> 1; 1-> 0 因此，如果 w = 0011 则 w-flip = 1100

将反转视为反转顺序的字符 因此，如果 w = 01101 那么 w-reverse = 10110

现在我正在尝试生成一个 PDA，它接受字符串 w，然后打印 w，打印 (w-flip-reversed)

w = 011
w-flip = 100
w-flip-reverse = 001

所以这将打印：“011001”

考虑 # 为一个空白字符。所以一个字符串会开始 #011#

转换表看起来像这样：

State:    Symbol Read:    Next State:    Head Instruction:
start     #               r1             L

等等

有什么想法吗？

Answer 1

打印出字符串很简单（我希望）。打印翻转就像在读取 1 时打印 0 一样简单，反之亦然。

一个让您继续反转的粗略草图：

• 您需要一个地方来将字符串一块一块地放置，以便于反转，因此先进后出存储是理想的（这在 PDA 中可能是什么？）。
• 然后，您需要观察字符串的末尾，以便知道何时从存储字符串（以便轻松反转）切换到输出。
• 那么你需要以正确的相反顺序检索字符串的每个部分（如果存储的 FILO 是微不足道的）并输出它，当到达字符串末尾时停止。

在您的情况下，您需要将翻转的字符串放入存储中以进行反转。