1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 31, 2022 at 1:06

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.