Let be an operation recursively 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
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.