Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free.
Hi I've been struggling quite a lot with this question. There's a similar quesion already answered here (Closure of CFL against right-quotient with regular languages)
But the difference here is that we have $xw \in L$ and not $wx \in L$.
Can anyone give some ideas/help?
Thanks in advance.
The reverse of a language $L$ is the language $L^R = \{ w^R : w \in L \}$, where $w^R$ is obtained from $w$ by reversing the orders of the letters.
The reverse of a context-free language is context-free. This can be shown by starting with a grammar and reversing all production rules, that is, replacing $A \to \alpha$ by $A \to \alpha^R$. Similarly, the reverse of a regular language is regular. This can be shown in many ways: by reversing the arrows in an NFA, by reversing the production rules in a regular grammar, by reversing regular expressions, and so on.
Now define $L/R = \{ w : wx \in L \text{ for some } x \in R \}$ and $R \backslash L = \{ w : xw \in L \text{ for some } x \in R \}$, and notice that $R \backslash L = (L^R/R^R)^R$. Hence closure under regular right quotient implies closure under regular left quotient.
