If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free

551 Views Asked by At

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free

I have to prove or give a counterexample. I know the closures properties of CFL, however, this questions asks the converse, so I'm a little confused.

I tried to create a counterexample without success. For the proof, I was thinking about the contrapositive, but I'm stuck.

I'm sure it has something to do with the closure properties but I'm missing something very basic.

1

There are 1 best solutions below

0
On BEST ANSWER

HINT: $L=(L\setminus R)\cup(L\cap R)$. From here you can use a closure property, a simple construction with context-free grammars, or a simple construction with pushdown automata.

Extra Question: Does it actually matter that $R$ is regular?