# Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are?

In class, it was alluded to that a language: \begin{equation*} \{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \} \end{equation*} would be context free, if $L_1$ and $L_2$ are context free.

Intuitively, that doesn't make sense to me. I tried doing my own research and attempted a proof using the pumping lemma, but didn't get anywhere. Maybe I misunderstood? If that is correct, how could I prove it (or convince myself).

Class is right.

The pumping Lemma is not very helpful in this setting. It is usually used to show a given language non-context-free.

As for your language, first try to understand the special case, where $L_s = \{A\}$ for a special symbol $A$, that is try to prove that the language $\{ s_1As_2 \mid s_1s_2\in L_1 \}$ is context-free whenever $L_1$ is context-free.

In the comments below, Yuval gives a hint how to perform the construction with a PDA, for the general case. Start an automaton for $L_1$. At any nondeterministic moment (once during the computation) interrupt the $L_1$ computation and push a new bottom-of-stack symbol. Then use that as a marker to simulate a PDA for $L_2$ which stops when we accept by empty stack. Remove the marker, and happily resume the computation on the second part of $L_1$.

A simple construction using CF grammars is given by Yuval in his answer.

• I'm sorry, I'm still confused. How would you know where that special symbol begins/ends if $L_1$ and $L_2$ are over the same alphabet? I tried thinking about it as a PDA, and it seems like you would have to non-deterministically branch on every symbol, assuming is is the first in $w$. Commented Oct 13, 2013 at 22:52
• Luckily PDAs can be non-deterministic. Commented Oct 14, 2013 at 2:12

Hint: Consider (for simplicity) a grammar for $L_1$ in Chomsky normal form. For each original non-terminal $A$, add another non-terminal $A'$; the starting symbol is the marked version $S'$ of the original starting symbol $S$. For each production $A \to BC$, add the additional productions $A' \to B'C$ and $A' \to BC'$. For each production $A \to a$, add the addition productions $A' \to S_{L_2} a$ and $A' \to a S_{L_2}$, where $S_{L_2}$ is the starting symbol of $L_2$.

• Very clear explanation, it makes a lot more sense now. Thank you. Commented Oct 14, 2013 at 4:48