# Proving regular languages are closed under a form of interleaving

I've got the following definitions:

$$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$

when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means the $i$-th letter in $w$.

$$\mathrm{Interleave}\,(L_1,L_2)\ \ = \!\!\!\!\bigcup_{\substack{x\in L_1,\ y\in L_2,\\ |x|=|y|}}\!\!\!\! \mathrm{Interleave}\,(x,y)$$ when both $L_1$ and $L_2$ are languages.

I have to prove that if I know that $L_1$ and $L_2$ are both regular languages, $\mathrm{Interleave}\,(L_1,L_2)$ is a regular language as well.

I have absolutely no idea how to do it .

Hint. Because $L_1$ and $L_2$ are both regular, you know they're accepted by NFAs (or DFAs; it doesn't matter) $M_1$ and $M_2$, respectively. To show that $\mathrm{Interleave}\,(L_1,L_2)$ is regular, show that it's accepted by some NFA $M$. For each character it receives, $M$ can decide to act either like $M_1$ or like $M_2$.

Any family of language that is a trio is closed under interleaving with a regular set.

This includes of course interleaving of 2 regular sets, since regular sets form a trio.

## Proving the result (and more) only with closure properties

Note: I created the definitions below for the purpose of this question. I do not know whether there are established definitions for this, which might exist under another name.

The purpose of this approach is to avoid any complex construction of automaton. But we need at least one specific operation to account for dealing with several strings at the same time. And, as an unexpected benefit, the end result is much more general (this is actually more to be expected from proofs based on closure properties). However, the proof is centered on the question asked, and only includes remarks to show how it generalizes.

Consider two alphabets $\Sigma_i$ for $i=1,2$. We can consider their product $\Sigma_1\times\Sigma_2=\{(a_1,a_2)\mid a_1\in\Sigma_1\wedge a_2\in\Sigma_2\}$ as a new alphabet, where the symbols are pairs of symbols of $\Sigma_1$ and $\Sigma_2$.

Similarly, with 3 alphabets, we can build an alphabet of triples (instead of pairs). We ignore the trivial issue of associativity in using pairs to build triples, or $n$-tuples, here and in the rest of this answer.

Now, given two strings $x\in\Sigma^*$ and $y\in\Pi^*$ such that $|x|=|y|$ we can define the conflation of these two strings as the string $z=\mathrm{Conflate}\,(x,y)\in(\Sigma\times\Pi)^*$ with the same size, such that $\forall i\in[1,|x|], z_i=(x_i,y_i)$.

We can similarly conflate $n$ strings of equal length into a single string of $n$-tuples of symbols ... but we will not go beyond $n=3$.

Finally, given two languages $L_1\subseteq\Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$ we can define the conflation of these two languages:

$$\mathrm{Conflate}\,(L_1,L_2)=\{\mathrm{Conflate}\,(x,y)\mid |x|=|y|\wedge x\in L_1 \wedge y\in L_2\}$$

We can also conflate similarly any number of languages, to produce a language on the cross product of their alphabets.

This $\mathrm{Conflate}$ operation has many simple properties, that are rather trivial to prove.

Given two alphabets $\Sigma_1$ and $\Sigma_2$ and two languages $L_1\subseteq\Sigma_1^*$ and $L_2\subseteq\Sigma_2^*$:

• $\mathrm{Conflate}\,(L_1,L_2)\subseteq(\Sigma_1\times\Sigma_2)^*$

• $\mathrm{Conflate}\,(L_1,\Sigma_2^*)$ is regular iff $L_1$ is regular

• $\mathrm{Conflate}\,(\Sigma_1^*,L_2)$ is regular iff $L_2$ is regular
The proof uses a projection homomorphism that keep only the $L_1$ or the $L_2$ component of the conflation.

• side note: the above is also true for context-free, and more generally families of languages closed under non-erasing homomorphism and inverse homomorphism (such as trios). For example, if $\mathcal F$ is a trio, and $L$ is a language, and $\Sigma$ and alphabet (not necessarily the alphabet of $L$), then $\mathrm{Conflate}\,(L,\Sigma^*)\in\mathcal F\;$ iff $\;L\in\mathcal F$.

• $\mathrm{Conflate}\,(L_1,L_2)= \mathrm{Conflate}\,(L_1,\Sigma_2^*) \cap \mathrm{Conflate}\,(\Sigma_1^*,L_2)$

• Hence, if $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular.

Now we consider also the alphabet $B=\{0,1\}$, and the alphabet cross-product $\Sigma_1\times\Sigma_2\times B$, and we define on this alphabet the substitution $\sigma$ as follows:

$\forall (a_1,a_2,b)\in(\Sigma_1\times\Sigma_2\times B),\; \sigma((a_1,a_2,b))=\;($ if $b=0$ then $a_1$ else $a_2)$.

If $L_1$ and $L_2$ are both regular, then $\mathrm{Conflate}\,(L_1,L_2)$ is also regular, and thus $\mathrm{Conflate}\,(\mathrm{Conflate}\,(L_1,L_2),B^*)$ is regular, since $B^*$ is.

Applying the substitution $\sigma$, since regular sets are closed under substitution, we know that the language $\sigma(\mathrm{Conflate}\,(\mathrm{Conflate}\,(L_1,L_2),B^*))$ is regular.

But it can fairly easily be proved that

$$\mathrm{Interleave}\,(L_1,L_2)=\sigma(\mathrm{Conflate}\,(\mathrm{Conflate}\,(L_1,L_2),B^*))$$

Hence $\mathrm{Interleave}\,(L_1,L_2)$ is regular.

The interesting point here is that, with nearly no further work, we can prove identically that many families of languages, context-free for example, and more generally trios (hence also AFLs), are closed under $\mathrm{Interleave}$ composition with regular languages, notably because the substitution $\sigma$ is non-erasing. This essentially follows from the fact that trios are closed under inverse homomorphism, under intersection with regular sets, and under non-erasing homomorphism.

• OK! But why don't you make the connection with inverse morphisms more explicit? ${\mathrm Conflate}(L_1,L_2) = \pi_1^{-1}(L_1) \cap \pi_2^{-1}(L_2)$, where $\pi_i$ is the projection to the $i$-th component. – Hendrik Jan May 9 '15 at 23:17
• @HendrikJan The main reason is that I am probably not as experienced as you are in this type of proof, and I had to work everything from scratch. So I improved the presentation as I understood what I was doing, but at some point I had to simply write it down, for lack of time. Also, I was trying to stay with the original question, and the pure closure proof started as a collection of side remarks. I realized the importance of the projection morphism when in the end I was trying to assert the result for any trio. For regular sets, I knew I could hack it easily. But trios require better. – babou May 9 '15 at 23:59
• @HendrikJan So I agree with you that it needs rewriting, and possibly more direct definitions, but may then look even less like an answer to the question. My other problem is that I am to leave for a few days, hence my lack of time for immediate improvements. But I was hoping you would look at it, since you are likely to know what names may have been already given to the technique. I would also add that the result surprised me, as it seems a fairly drastic transformation, potentially erasing lots of information. I spent some time trying to find an error. – babou May 10 '15 at 0:01