closure of Context free grammer to homomorphism using PDA

Question

I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG. I'm not looking for a full and formal proof, I just want to understand the general idea.

Answer 1

The idea is to replace a single transition by a sequence of transitions.

Suppose for example that $h(\sigma) = \tau_1 \ldots \tau_\ell$, and consider a transition at state $p$ which replaces the symbol $A$ on the stack with the string $\alpha$, and moves to state $q$.

We replace this transition by a sequence of transitions $p \to s_1 \to \cdots \to s_{\ell-1} \to q$, which read the letters $\tau_1,\ldots,\ell$ in sequence; the states $s_1,\ldots,s_{\ell-1}$ are unique for handling this transition. The first transition $p \to s_1$ replaces $A$ with $\alpha$, and the rest don't change the stack.