# closure of Context free grammer to homomorphism using PDA

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.

## 1 Answer

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.

• So basically the idea is the same as the concept of proof that regular languages are closed under homomorphism? And a little question, Do we add states between p and q and basically "force" the transition between the new states we add to be made only for the input letters that the homomorphism defines? And in the transitions between p and q we only read from the input, without push / pop from the stack right? – Ella Jul 1 '20 at 20:20
• Yes, the idea is very similar. There are some implementation details, which are better to work out on one's own; they depend to some extent on the exact PDA model, and also there are several different possible implementations. – Yuval Filmus Jul 1 '20 at 20:22
• thank you very much. I appreciate your help!!! – Ella Jul 1 '20 at 20:24