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?

Improve this question
$\endgroup$
1
  • $\begingroup$ $o$ operation mean? $\endgroup$ Commented Jun 11, 2022 at 3:39

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.