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
$\begingroup$
$\endgroup$
3
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.
answered Jul 1, 2020 at 20:09
-
$\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$– EllaJul 1, 2020 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$ Jul 1, 2020 at 20:22
-
$\begingroup$ thank you very much. I appreciate your help!!! $\endgroup$– EllaJul 1, 2020 at 20:24