Take the 2-minute tour ×

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.


share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
Judging by the OP’s comments to my answer to this question, the OP either is not allowed to use closure under inverse homomorphisms or would very much prefer not to do so. –  Brian M. Scott Dec 29 '12 at 19:58
@BrianM.Scott Yes, you are right: that is why I asked. It seems one definitely needs some nondeterminism on how to code and combine, and I can do that only with inverse morphisms. –  Hendrik Jan Dec 29 '12 at 20:09
Or directly with pushdown automata. –  Brian M. Scott Dec 29 '12 at 20:11
@HendrikJan Thanks alot for the hint! As Mr. Brian said, I can't use (and don't know how to use) inverse homomorphisms, only homomorphisms. Any idea for that? –  DanielY Dec 29 '12 at 21:35
Sorry, no, I only know solutions that use inverse morphisms. (Or techniques that directly use grammars, automata...) –  Hendrik Jan Dec 29 '12 at 23:06
show 1 more comment

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.

share|improve this answer
add comment

Your Answer


