I want to show that if $P$ is a PDA, then there exists a PDA $P_2$ with only two stack symbols, such that $L(P) = L(P_2)$.
As I want only two stack symbols for $P_2$, it seems intuitive to encode in binary the stack symbols of $P$. However, I don't know how to formalize this proof, or write the proof altogether. Can anyone help me out?
A binary coding seems to be promising, however the method of encoding needs to be precise. When you use multiple places in the stack to represent a single stack move, your automaton needs to know when one symbol ends and another begins. There are two ways that come to mind to do this. They are fixed length codes and prefix codes. Basically they ensure there is no ambiguity in your encoding.
To actually prove this:
-Assume you have an encoding for your stack alphabet(G). For example, let's say G = {a,b,c,d} and G' = {0,1}. We'll encode G as follows: a = 00, b = 01, c = 10, d = 11.
-At each node in the graph representation of P, put in two intermediary nodes. One that takes a '0' off the stack, and one that takes a '1' off the stack. From these nodes take off the correct symbol of the stack to complete the transition. The first transition should consume epsilon as input from your word. You can do a similar thing to push symbols onto the stack.
There will be wrinkles when at a node q, you'd pop if you saw an 'a', but push a c if you saw a b, but you should be able to work that out because you know the latest relevant steps you've taken. (In this case, edge that pops a 0, if it sees a 1, push a zero, push a 0, push a 1). Also some stuff will be backwards so be careful.