# Show that language is context-free

Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such words over alphabet $\Sigma$, for which there exists some run of automata $A$, such as in every step symbols on the stack belongs to the regular language $R$.

Show that language $L_R(A)$ is context-free.

• I would try to solve this using a sort-of product construction between $A$ and $R$. I'm not sure if it will suffices, but it's worth a try, I think. (Also, you should show some effort by posting your attempt.) – chi Jun 15 '18 at 10:20

Let $$Q$$ be the set of states in a DFA $$D$$ for $$R$$. We replace $$\Gamma$$ with $$\Gamma \times Q$$, and update the PDA so that the stack contains, apart from the original stack symbols, also the state that $$D$$ is in after reading the current word on the stack. The PDA only allows transitions if the element at the top of the stack corresponds to an accepting state of $$D$$, and also checks this condition at the very end.