# Pushdown automaton with binary stack

I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language as P. I've tried to codify the stack alphabet of P in binary, using the same ammount of symbols for each representation so I know where the codification of one symbol starts and ends, but I don't know how to simulate P with P'.

• What have you tried? Where did you get stuck? Please detail your attempts, and what you don't understand, and we'll help from there. This site does not accept homework dumps. May 26 at 18:11

You're on a good path! Keep at it. Remember that a pushdown can have a finite-state control, and you can remember up to a finite amount of information in the finite-state control. Also, it can have $$\epsilon$$-transitions (so the read head doesn't consume any of the input). Those might be helpful.