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.