# Closure of context-free languages under regular quotient [duplicate]

Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that $C / R = \{w| \exists x \in R: wx \in C\}$ is also a context-free language?

There is a simple proof uses PDAs. Start with a PDA for $C$. Add an $\epsilon$ transition to a copy of the PDA, multiplied by an NFA for $R$. Instead of reading characters from the input, this part guesses them and advances the NFA. The new machine accepts if both the PDA and the NFA accept. Details left to you.
Let $\mathcal{L}$ be the full trio, let $L \in \mathcal{L}$ be a language over $\Sigma$, and let $R$ be a regular language over $\Sigma$. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$. Define the homomorphism $h\colon \Sigma \cup \Sigma' \to \Sigma$ by $h(\sigma) = h(\sigma') = \sigma$, and define the homomorphism $k\colon \Sigma \cup \Sigma' \to \Sigma$ by $k(\sigma') = \sigma$, $k(\sigma) = \epsilon$. Then $$L/R = k(h^{-1}(L) \cap \Sigma^{\prime *} R).$$
• is it valid to connect a PDA to an NFA?? because first I thought that if I connect the accept state of the PDA to the start state of NFA, and change the labels on the NFA a bit(adding an epsilon indicating top of the stack (making the transitions similar to the PDA for example ($a, \varepsilon -> \varepsilon$) this will solve the problem. but I doubt about it. is it ok to do so?? Commented May 11, 2018 at 16:07