0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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