# prove that context free languages are closed under the $\circ$ operation

Prove that if $$C$$ and $$D$$ are context-free languages, then so is $$C\circ D := \cup_{n\ge 0} C^n D C^n$$.

I know that $$\{0^n 1 0^n : n\ge 0\}$$ is context free, being the intersection of $$L(0^* 10^*)$$ and $$L(G)$$, where $$G$$ is the context free grammar with start symbol S given by $$S\mapsto S1 S | 0S | \epsilon$$. Also, I know basic properties like the fact that context free languages are closed under taking prefixes, union, and concatenation. The issue with applying this technique to the given problem is that $$C^* B C^*$$ may not be regular. How can I circumvent this issue to solve the given question?

• $o$ operation mean? Commented Jun 11, 2022 at 3:39

As you state the language $$\{0^n 1 0^n\mid n\ge 0\}$$ is context-free. (You do not need closure properties for this: $$S\to 0S0\mid 1$$ will do.)
Now continue as follows. Consider instead the language $$\{X^n Y X^n\mid n\ge 0\}$$, where $$X,Y$$ are the axioms of context-free grammars for $$C$$ and $$D$$.