2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ $o$ operation mean? $\endgroup$
    – A. H.
    Commented Jun 11, 2022 at 3:39

1 Answer 1

0
$\begingroup$

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

$\endgroup$

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.