0
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 3 '17 at 12:39
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.