A Push Down Automata that produces the flip and reverse of a string

Question

The alphabet: 0, 1

Consider a flip, to flip each character: 0 -> 1; 1 -> 0 So if w = 0011 then w-flip = 1100

Consider a reverse to be the characters in reversed order So if w = 01101 then w-reverse = 10110

Now I am trying to produce a PDA which takes the string w, and then prints w, prints (w-flip-reversed)

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

So this would print: "011001"

Consider # to be a blank character. So a string would start #011#

Transition table looks something like this:

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

And so on

Any ideas?

Answer 1

Printing out the string is simple (I hope). Printing out the flip is as easy as printing out 0 when you read a 1 and vice-versa.

A rough sketch to get you going on the reversal:

• You need a place to put the string piece by piece that lends itself to reversal, so first-in-last-out storage is ideal (What might this be in a PDA?).
• Then you need to watch for the end of the string so you know when to switch from storing the string for easy reversal to output.
• then you need to retrieve each piece of the string in the correct reverse order (which if stored FILO is trivial) and output it, stopping when you reach the end of the string.

In your case, you'll need to put the flipped string in storage for reversal.