3
$\begingroup$

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).

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Craig Spurr Oct 13 '13 at 22:52
  • 3
    $\begingroup$ Luckily PDAs can be non-deterministic. $\endgroup$ – Yuval Filmus Oct 14 '13 at 2:12
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Very clear explanation, it makes a lot more sense now. Thank you. $\endgroup$ – Craig Spurr Oct 14 '13 at 4:48

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.