2
$\begingroup$

Given $L_1$ and $L_2$ over some alphabet:

$L_1@L_2 = \{uv \mid u \in L_1 \land v \in L_2 \land |u|=|v|\}$

The question is: if $L_1$ is regular and $L_2$ is context-free, is $L_1@L_2$ context free?

I've been trying to disprove this but to no avail. So I've been thinking to prove this by buiding a PDA but I can't seem to figure this out.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael♦ May 20 '17 at 5:13
3
$\begingroup$

There is no guarantee that your resulting language will be context free.

Here is a hint for creating a more formal proof. Try the languages $L_1 = c^*$ and $L_2 = a^nb^n$. The resulting language, given your additional requirement of $|u| = |v|$ would be $c^{2n}a^nb^n$.

Using the pumping lemma for context free languages, are there two substrings that you can pump indefinitely that will match this language?

|cite|improve this answer
$\endgroup$

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.