Showing a language is context-free with closures

Question

Let $L_1$ a regular language and $L_2$ a context-free one.

I need to show that $$L = \{w \mid w = x_1y_1x_2y_2\dots x_ny_n \mbox{ where } x_1x_2\dots x_n \in L_1 \mbox{ and } y_1y_2\dots y_n \in L_2\}$$ is context-free (or not) ($x_i$ and $y_i$ are letters under the alphabet $\{a, b\}$)

As far as I know, if $L_1$ and $L_2$ were both regular, this language would also be regular, so my guess is that this one is context-free. I need to prove this properly using only closures under homomorphisms and under intersection of a regular lang. with a context-free lang.

Help would be greatly appreciated.

Thanks

Answer 1

Hopefully your are also allowed to use closure under inverse homomorphisms (for both regular and context-free languages)?

As this is homework, I will first give a hint only. When you need more explicit help let us know.

Let us fix the alphabets: $L_i\subseteq \Sigma_i^*$, for $i=1,2$.

The operation (sometimes called fair shuffle) alternates letters from both languages. It is a first step to "combine" both languages by using a "parallel alphabet" $\Sigma_1\times \Sigma_2$, intersection and inverse morphism. This intermediate alphabet has pairs of letters, but is an alphabet as it is of finite cardinality.

E.g., $\{a,b\}\times \{0,1,2\} = \{ (a,0), (b,0), (a,1), (b,1), (a,2), (b,2) \}$. For $abba\in L_1$ and $1120 \in L_2$ we code both strings as $(a,1)(b,1)(b,2)(a,0)$.

Answer 2

On request I will make the answer more explicit. The best way, I now realize, is to use another approach. Hence my new answer.

Consider the more general operation of shuffle. Starting with two strings we interleave the letters from both strings, but not necessarily fair and alternating. The result is a set of words. So with $w_1 = ababab$ and $w_2 = aaabbb$ we get for example $aabaaabbabbb$ (fair), $abababaaabbb$ (first complete $w_1$) or $aaabaabbabbb$ (more randomly?) and many other strings. How do we test whether a string is in the shuffle? By marking the letters: $a_1a_2b_1a_2a_1a_2b_1b_2a_1b_2b_1b_2$, $a_1b_1a_1b_1a_1b_1a_2a_2a_2b_2b_2b_2$, or $a_2a_1a_2b_1a_1a_2b_2b_1a_1b_2b_2b_1$. If the projections to $1$-letters and $2$-letters form $w_1$ and $w_2$ we have done ok.

The projections can be formalized as morphisms. Let $\Sigma_i=\{a_i,b_i\}$ and $\pi_1:(\Sigma_1\cup\Sigma_2)^* \to \Sigma^*$ is the morphism that maps $a_1,b_1$ to $a,b$ and $a_2,b_2$ both to $\epsilon$. Similarly $\pi_2$ deletes $a_1,b_1$ and maps $a_2,b_2$ to $a,b$. If $w\in(\Sigma_1\cup\Sigma_2)^*$ it is a marked shuffle of $w_1$ and $w_2$ if $\pi_1(w) = w_1$ and $\pi_2(w) = w_2$.

This can also be done with languages, shuffling all strings of them. E.g., $L_1 = (ab)^*$ and $L_2 = \{ a^nb^n \mid n\ge 0\}$ fit the string example above. We recognize a marked shuffle $w$ of strings in $L_1$ and $L_2$ by applying morphisms $\pi_i(w) \in L_i$, $i=1,2$. In other words, by definition of inverse operation, $w\in \pi_i^{-1}(L_i)$, $i=1,2$.
Thus the set of all marked shuffles equals $\pi_1^{-1}(L_1) \cap \pi_2^{-1}(L_2)$.

How do we additionally check for marked fair shuffles: by allowing only shuffles where the two alphabets alternate: $(\Sigma_1\Sigma_2)^* \cap \pi_1^{-1}(L_1) \cap \pi_2^{-1}(L_2)$.

Finally we retrieve the shuflles, without the markings, by applying the morphism $h:(\Sigma_1\cup\Sigma_2)^* \to \Sigma^*$ that maps $a_i,b_i$ to $a,b$, $i=1,2$.

Thus $L = h(\,(\Sigma_1\Sigma_2)^* \cap \pi_1^{-1}(L_1) \cap \pi_2^{-1}(L_2)\,)$.

If $L_i$ is regular/context-free, then so is $\pi_1^{-1}(L_i)$. If (at most) one of them is context-free, then the result is context-free. If both are regular, then so is the resulting fair shuffle.