# Design Push Down Automata to accept palindrome by empty stack

I'm trying to make a PDA that accepts the language w001(rev w) | w = {0,1}* by empty stack, where rev w means the reverse of w. (Stack symbol = #)

I've come up with this so far, but I don't know how to handle the 001 in the middle of w and rev w. Any suggestions?

1. Initial Start: Push 0,1 onto stack

(q0,0,#) -> (q0,0#), (q0,1,#) -> (q0, 1#)

2. Continue to push 0,1 onto stack

(q0,0,0) -> (q0,00), (q0,0,1) -> (q0, 01), (q0,1,0) -> (q0,10), (q0,1,1) -> (q0, 11)

3. Handle 001 and transition to q1

Don't know how to do this

4. Pop 0,1 off stack

(q1,0,0) -> (q1,E), (q1,1,1) -> (q1,E)

If stack is empty after this point, than accept language.

-

Hint: Non-deterministically guess where the middle 001 is, and don't push or pop anything when reading this substring. (If you guess wrong, just make sure the stack doesn't empty at the end of the computation.)
What if you have a string like 0011011100 which should not be accepted by the PDA because the middle substring is 01 instead of 001. If you epsilon transition right before 01, read 0 and 1 without pushing or popping, and then transition to my 4th step, wouldn't that string be accepted by the PDA? –  Takkun Oct 3 '12 at 19:36
@Takkun: When I say "guess where the middle 001 is" I mean that the PDA non-deterministically enters a subroutine of two parts: the first expects that the next three symbols read off the tape are 001, and the second expects that whatever comes after this 001 is the reverse of whatever occurred before it. If either of these conditions fails (for whatever reason) you need to do something to ensure that the stack is not empty at the end of the computation. If both conditions are satisfied, the stack should naturally empty at the end of the computation. –  Arthur Fischer Oct 3 '12 at 19:55