# Closure of context-free languages under “removal of a regular language from the right”

I have a homework that I can't solve can somebody help me?

If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \{\alpha\in\Sigma^*\mid \alpha\beta\in L\text{ for some }\beta\in R\}$$ context-free?

Let me prove that if $L$ is regular then so is $P$. The proof in your case is similar. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$ be a copy of the alphabet $\Sigma$. Let $s$ be the $\Sigma$-substitution $s(\sigma) = \{\sigma,\sigma'\}$, let $t$ be the $\Sigma$-homomorphism $t(\sigma) = \sigma'$, and let $d$ be the $\Sigma \cup \Sigma'$-homomorphism $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Then $$P = d(s(L) \cap \Sigma^* t(R)).$$

As an aside, the class of languages obtained by dividing a context-free language by a context-free language consists of all r.e. languages. See for example The family of one-counter languages is closed under quotient by Latteux, Leguy and Ratoandromanana.