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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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