## Regular languages are closed under interleaving

#### February 08, 2020

Let $\otimes$ be an operation recursivley defined on strings of the same length such that

so that the action of $\otimes$ on two strings “interleaves” the two strings. For example, $ab \otimes 12 = a1b2$.

Similarly, for languages $A, B \subseteq \Sigma^*$, let

be the set of all string obtained from interleaving a string in A with a string in B. Note that $\otimes$ is bijective, so each string in $A \otimes B$ is uniquely defined by its operands.

### Proposition: If $A$ and $B$ are regular, then $A \otimes B$ is regular.

Proof. As $A$ and $B$ are regular, let $M_A = (Q_A, \Sigma, \delta_A, s_A, F_A)$ and $M_B = (Q_b, \Sigma, \delta_B, s_B, F_B)$ be DFAs such that $L(M_A)=A$ and $L(M_B)=B$. Define the DFA

where $\delta_N$ is defined as follows:

We want to show that $L(N)=A \otimes B$. First, we prove the lemma

for all $x,y \in \Sigma^*$ such that $|x| = |y|$ by induction.

Basis. We have

so the induction hypothesis holds for $\epsilon$.

Induction step. Suppose the induction hypothesis (I.H.) holds for some $x, y \in \Sigma^*$ with $|x|=|y|$. For $a, b \in \Sigma$, we have

so the I.H. for $x$ and $y$ implies the I.H. for $xa$ and $yb$.

From the lemma, we have

Hence, $A \otimes B = L(N)$, so $A \otimes B$ is regular.