# Operation on two CFLs which results in a non-CFL

Suppose we have two context-free Languages $L_{1}$ and $L_{2}$, and we form a new language $L_{3}=L_{1} \circ L_{2} = \{\alpha\beta | \alpha \in L_{1},\beta \in L_{2},|\alpha|=|\beta|\}$. Is it possible that $L_{3}$ is not context-free?

• What did you try? Where did you get stuck? We're happy to help with conceptual questions but just solving homework-style exercises for you is unlikely to really help. Jun 3 '17 at 12:39

## 1 Answer

Let's denote your operation by $\diamond$, so the question is, if $L_1$ and $L_2$ are CFLs, is $L_1\diamond L_2$ always a CFL? The answer is no.

Let $L_1=L_2=\{0^n1^n\mid n\ge 0\}$. This is, of course, a CFL. However, $$L_1\diamond L_2=\{0^n1^n0^n1^n\mid n\ge 0\}$$ and it's not too hard to show that this language is not context-free.