Regular languages are closed under interleaving

February 08, 2020

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

so that the action of on two strings “interleaves” the two strings. For example, .

Similarly, for languages , let

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

Proposition: If and are regular, then is regular.

Proof. As and are regular, let and be DFAs such that and . Define the DFA

where is defined as follows:

We want to show that . First, we prove the lemma

for all such that by induction.

Basis. We have

so the induction hypothesis holds for .

Induction step. Suppose the induction hypothesis (I.H.) holds for some with . For , we have

so the I.H. for and implies the I.H. for and .

From the lemma, we have

Hence, , so is regular.