# if $RA$ is context-free, is $A$ context-free?

If $$RA$$ is context-free for a regular language R, is $$A$$ context-free?

I think this statement is true. Let G be the CFG given by the rules $$S_0\mapsto LA_1, S\mapsto LA_1, A_1\mapsto SA_2 | RS | 1, A_2\mapsto RS | 1, L\mapsto 0, R\mapsto 1$$, where $$S_0$$ is the start symbol. How would one modify G to get a CFG that generates the same grammar but with $$0$$ removed from the front of every string? Clearly the only way a derivation in G could generate a string starting with 0 is if it contains one of the nonterminals $$L,S,A_1$$. So one should probably mark these nonterminals somehow and then modify the rules containing these nonterminals on the RHS.

Note that $$\Sigma^*A=\Sigma^*$$ is a regular language, where $$A$$ is any language that contains the empty string. So, given language $$A$$, the existence of an regular language $$R$$ such that $$RA$$ is regular (and hence also context-free) does not imply $$A$$ is context-free. Nor does it does imply $$A$$ is context-sensitive, etc.
If $$R$$ is meant to be any regular language, then letting $$R=\{\epsilon\}$$, we see the condition implies $$A=\{\epsilon\}A$$ is a regular language (and hence also context-free).
• Thanks. I think there's a notion of a "left quotient though." For instance, I think that if R is regular and $A$ is context free, then $\{a : \exists r, ra\in A\}$ is context free. Commented Jul 31, 2022 at 1:06