Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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?
