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.


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.

  • $\begingroup$ 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? $\endgroup$ – Ella Jul 1 '20 at 20:20
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 1 '20 at 20:22
  • $\begingroup$ thank you very much. I appreciate your help!!! $\endgroup$ – Ella Jul 1 '20 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.