patternMinor
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?
Viewed 0 times
l_1s_0freeareands_1s_0s_1l_2context
Problem
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).
\{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).
Solution
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.
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.
Context
StackExchange Computer Science Q#16048, answer score: 4
Revisions (0)
No revisions yet.