regex - 下推自动机，可产生字符串的翻转和反转

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

打印出字符串很简单（我希望如此）。打印出翻页就像0在阅读 a 时打印出一样容易，1反之亦然。

一个粗略的草图，让你继续逆转：

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

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