Regular languages are closed under interleaving

February 08, 2020

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

ϵϵ=ϵxayb=(xy)ab\begin{aligned} \epsilon \otimes \epsilon &= \epsilon\\ xa \otimes yb &= (x \otimes y)ab \end{aligned}

so that the action of \otimes on two strings "interleaves" the two strings. For example, ab12=a1b2ab \otimes 12 = a1b2.

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

AB={xy:xA,yB,x=y}A \otimes B = \{ x \otimes y : x \in A, y \in B, |x|=|y|\}

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 ABA \otimes B is uniquely defined by its operands.

Proposition: If AA and BB are regular, then ABA \otimes B is regular.

Proof. As AA and BB are regular, let MA=(QA,Σ,δA,sA,FA)M_A = (Q_A, \Sigma, \delta_A, s_A, F_A) and MB=(Qb,Σ,δB,sB,FB)M_B = (Q_b, \Sigma, \delta_B, s_B, F_B) be DFAs such that L(MA)=AL(M_A)=A and L(MB)=BL(M_B)=B. Define the DFA

N=(QA×QB×{L,R},Σ,δN,(sA,sB,L),FA×FB×{L})N=(Q_A \times Q_B \times \{L, R\}, \Sigma, \delta_N, (s_A, s_B, L), F_A \times F_B \times \{L\})

where δN\delta_N is defined as follows:

δN((qA,qB,L),a)=(δA(qA,a),qB,R)δN((qA,qB,R),a)=(qA,δA(qB,a),L)\begin{aligned} \delta_N((q_A, q_B, L), a) &= (\delta_A(q_A, a), q_B, R)\\ \delta_N((q_A, q_B, R), a) &= (q_A, \delta_A(q_B, a), L) \end{aligned}

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

δN^((sA,sB,L),xy)=(δA^(sA,x),δB^(sB,y),L)\hat{\delta_N}((s_A, s_B, L), x \otimes y) = (\hat{\delta_A}(s_A, x), \hat{\delta_B}(s_B, y), L)

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

Basis. We have

δN^((qA,qB,L),ϵ)=(qA,qB,L)=(δA^(qA,ϵ),δB^(qB,ϵ),L),\hat{\delta_N}((q_A,q_B,L), \epsilon) = (q_A,q_B,L) = (\hat{\delta_A}(q_A, \epsilon), \hat{\delta_B}(q_B, \epsilon), L),

so the induction hypothesis holds for ϵ\epsilon.

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

δN^((qA,qB,L),xayb)=δN^((qA,qB,L),(xy)ab)(def of )=δN^(δN^((qA,qB,L),xy),ab)(def of δN^)=δN^((δA^(sA,x),δB^(sB,y),L),ab)(I.H.)=δN(δN((δA^(sA,x),δB^(sB,y),L),a),b)(def of δN^)=δN((δA(δA^(sA,x),a),δB^(sB,y),R),b)(def of δN)=δN((δA^(sA,xa),δB^(sB,y),R),b)(def of δN^)=(δA^(sA,xa),δB(δB^(sB,y),b),L)(def of δN)=(δA^(sA,xa),δB^(sB,yb),L)(def of δN^),\begin{aligned} \hat{\delta_N}((q_A,q_B,L), xa \otimes yb) &= \hat{\delta_N}((q_A,q_B,L), (x \otimes y)ab) & (\text{def of } \otimes)\\ &= \hat{\delta_N}( \hat{\delta_N}((q_A,q_B,L), x \otimes y), ab) & (\text{def of } \hat{\delta_N})\\ &= \hat{\delta_N}( (\hat{\delta_A}(s_A, x), \hat{\delta_B}(s_B, y), L), ab) & \text{(I.H.)}\\ &= \delta_N(\delta_N((\hat{\delta_A}(s_A, x), \hat{\delta_B}(s_B, y), L), a), b) & (\text{def of } \hat{\delta_N}) \\ &= \delta_N((\delta_A(\hat{\delta_A}(s_A, x), a), \hat{\delta_B}(s_B, y), R), b) & (\text{def of } \delta_N)\\ &= \delta_N((\hat{\delta_A}(s_A, xa), \hat{\delta_B}(s_B, y), R), b) & (\text{def of } \hat{\delta_N}) \\ &= (\hat{\delta_A}(s_A, xa), \delta_B(\hat{\delta_B}(s_B, y), b), L) & (\text{def of } \delta_N) \\ &= (\hat{\delta_A}(s_A, xa), \hat{\delta_B}(s_B, yb), L) & (\text{def of } \hat{\delta_N}), \\ \end{aligned}

so the I.H. for xx and yy implies the I.H. for xaxa and ybyb.

From the lemma, we have

xyAB    xyL(MA)L(MB)    xA and yB    δA^(sA,x)FA and δB^(sB,y)FB    (δA^(sA,x),δB^(sB,y),L)FA×FB×{L}    δN^((sA,sB,L),xy)FA×FB×{L}    xyL(N)\begin{aligned} x \otimes y \in A \otimes B &\iff x \otimes y \in L(M_A) \otimes L(M_B) \\ &\iff x \in A \text{ and } y \in B \\ &\iff \hat{\delta_A}(s_A, x) \in F_A \text{ and } \hat{\delta_B}(s_B, y) \in F_B\\ &\iff (\hat{\delta_A}(s_A, x), \hat{\delta_B}(s_B, y), L) \in F_A \times F_B \times \{L\} \\ &\iff \hat{\delta_N}((s_A, s_B, L), x \otimes y) \in F_A \times F_B \times \{L\} \\ &\iff x \otimes y \in L(N) \end{aligned}

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